lib/VMCore/TypesContext.h

   1 //===-- TypesContext.h - Types-related Context Internals ------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file defines various helper methods and classes used by
  11 // LLVMContextImpl for creating and managing types.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_TYPESCONTEXT_H
  16 #define LLVM_TYPESCONTEXT_H
  17
  18 #include "llvm/ADT/STLExtras.h"
  19 #include <map>
  20
  21
  22 //===----------------------------------------------------------------------===//
  23 //                       Derived Type Factory Functions
  24 //===----------------------------------------------------------------------===//
  25 namespace llvm {
  26
  27 /// getSubElementHash - Generate a hash value for all of the SubType's of this
  28 /// type.  The hash value is guaranteed to be zero if any of the subtypes are
  29 /// an opaque type.  Otherwise we try to mix them in as well as possible, but do
  30 /// not look at the subtype's subtype's.
  31 static unsigned getSubElementHash(const Type *Ty) {
  32   unsigned HashVal = 0;
  33   for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
  34        I != E; ++I) {
  35     HashVal *= 32;
  36     const Type *SubTy = I->get();
  37     HashVal += SubTy->getTypeID();
  38     switch (SubTy->getTypeID()) {
  39     default: break;
  40     case Type::OpaqueTyID: return 0;    // Opaque -> hash = 0 no matter what.
  41     case Type::IntegerTyID:
  42       HashVal ^= (cast<IntegerType>(SubTy)->getBitWidth() << 3);
  43       break;
  44     case Type::FunctionTyID:
  45       HashVal ^= cast<FunctionType>(SubTy)->getNumParams()*2 +
  46                  cast<FunctionType>(SubTy)->isVarArg();
  47       break;
  48     case Type::ArrayTyID:
  49       HashVal ^= cast<ArrayType>(SubTy)->getNumElements();
  50       break;
  51     case Type::VectorTyID:
  52       HashVal ^= cast<VectorType>(SubTy)->getNumElements();
  53       break;
  54     case Type::StructTyID:
  55       HashVal ^= cast<StructType>(SubTy)->getNumElements();
  56       break;
  57     case Type::PointerTyID:
  58       HashVal ^= cast<PointerType>(SubTy)->getAddressSpace();
  59       break;
  60     }
  61   }
  62   return HashVal ? HashVal : 1;  // Do not return zero unless opaque subty.
  63 }
  64
  65 //===----------------------------------------------------------------------===//
  66 // Integer Type Factory...
  67 //
  68 class IntegerValType {
  69   uint32_t bits;
  70 public:
  71   IntegerValType(uint32_t numbits) : bits(numbits) {}
  72
  73   static IntegerValType get(const IntegerType *Ty) {
  74     return IntegerValType(Ty->getBitWidth());
  75   }
  76
  77   static unsigned hashTypeStructure(const IntegerType *Ty) {
  78     return (unsigned)Ty->getBitWidth();
  79   }
  80
  81   inline bool operator<(const IntegerValType &IVT) const {
  82     return bits < IVT.bits;
  83   }
  84 };
  85
  86 // PointerValType - Define a class to hold the key that goes into the TypeMap
  87 //
  88 class PointerValType {
  89   const Type *ValTy;
  90   unsigned AddressSpace;
  91 public:
  92   PointerValType(const Type *val, unsigned as) : ValTy(val), AddressSpace(as) {}
  93
  94   static PointerValType get(const PointerType *PT) {
  95     return PointerValType(PT->getElementType(), PT->getAddressSpace());
  96   }
  97
  98   static unsigned hashTypeStructure(const PointerType *PT) {
  99     return getSubElementHash(PT);
 100   }
 101
 102   bool operator<(const PointerValType &MTV) const {
 103     if (AddressSpace < MTV.AddressSpace) return true;
 104     return AddressSpace == MTV.AddressSpace && ValTy < MTV.ValTy;
 105   }
 106 };
 107
 108 //===----------------------------------------------------------------------===//
 109 // Array Type Factory...
 110 //
 111 class ArrayValType {
 112   const Type *ValTy;
 113   uint64_t Size;
 114 public:
 115   ArrayValType(const Type *val, uint64_t sz) : ValTy(val), Size(sz) {}
 116
 117   static ArrayValType get(const ArrayType *AT) {
 118     return ArrayValType(AT->getElementType(), AT->getNumElements());
 119   }
 120
 121   static unsigned hashTypeStructure(const ArrayType *AT) {
 122     return (unsigned)AT->getNumElements();
 123   }
 124
 125   inline bool operator<(const ArrayValType &MTV) const {
 126     if (Size < MTV.Size) return true;
 127     return Size == MTV.Size && ValTy < MTV.ValTy;
 128   }
 129 };
 130
 131 //===----------------------------------------------------------------------===//
 132 // Vector Type Factory...
 133 //
 134 class VectorValType {
 135   const Type *ValTy;
 136   unsigned Size;
 137 public:
 138   VectorValType(const Type *val, int sz) : ValTy(val), Size(sz) {}
 139
 140   static VectorValType get(const VectorType *PT) {
 141     return VectorValType(PT->getElementType(), PT->getNumElements());
 142   }
 143
 144   static unsigned hashTypeStructure(const VectorType *PT) {
 145     return PT->getNumElements();
 146   }
 147
 148   inline bool operator<(const VectorValType &MTV) const {
 149     if (Size < MTV.Size) return true;
 150     return Size == MTV.Size && ValTy < MTV.ValTy;
 151   }
 152 };
 153
 154 // StructValType - Define a class to hold the key that goes into the TypeMap
 155 //
 156 class StructValType {
 157   std::vector<const Type*> ElTypes;
 158   bool packed;
 159 public:
 160   StructValType(const std::vector<const Type*> &args, bool isPacked)
 161     : ElTypes(args), packed(isPacked) {}
 162
 163   static StructValType get(const StructType *ST) {
 164     std::vector<const Type *> ElTypes;
 165     ElTypes.reserve(ST->getNumElements());
 166     for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i)
 167       ElTypes.push_back(ST->getElementType(i));
 168
 169     return StructValType(ElTypes, ST->isPacked());
 170   }
 171
 172   static unsigned hashTypeStructure(const StructType *ST) {
 173     return ST->getNumElements();
 174   }
 175
 176   inline bool operator<(const StructValType &STV) const {
 177     if (ElTypes < STV.ElTypes) return true;
 178     else if (ElTypes > STV.ElTypes) return false;
 179     else return (int)packed < (int)STV.packed;
 180   }
 181 };
 182
 183 // UnionValType - Define a class to hold the key that goes into the TypeMap
 184 //
 185 class UnionValType {
 186   std::vector<const Type*> ElTypes;
 187 public:
 188   UnionValType(const Type* const* Types, unsigned NumTypes)
 189     : ElTypes(&Types[0], &Types[NumTypes]) {}
 190
 191   static UnionValType get(const UnionType *UT) {
 192     std::vector<const Type *> ElTypes;
 193     ElTypes.reserve(UT->getNumElements());
 194     for (unsigned i = 0, e = UT->getNumElements(); i != e; ++i)
 195       ElTypes.push_back(UT->getElementType(i));
 196
 197     return UnionValType(&ElTypes[0], ElTypes.size());
 198   }
 199
 200   static unsigned hashTypeStructure(const UnionType *UT) {
 201     return UT->getNumElements();
 202   }
 203
 204   inline bool operator<(const UnionValType &UTV) const {
 205     return (ElTypes < UTV.ElTypes);
 206   }
 207 };
 208
 209 // FunctionValType - Define a class to hold the key that goes into the TypeMap
 210 //
 211 class FunctionValType {
 212   const Type *RetTy;
 213   std::vector<const Type*> ArgTypes;
 214   bool isVarArg;
 215 public:
 216   FunctionValType(const Type *ret, const std::vector<const Type*> &args,
 217                   bool isVA) : RetTy(ret), ArgTypes(args), isVarArg(isVA) {}
 218
 219   static FunctionValType get(const FunctionType *FT);
 220
 221   static unsigned hashTypeStructure(const FunctionType *FT) {
 222     unsigned Result = FT->getNumParams()*2 + FT->isVarArg();
 223     return Result;
 224   }
 225
 226   inline bool operator<(const FunctionValType &MTV) const {
 227     if (RetTy < MTV.RetTy) return true;
 228     if (RetTy > MTV.RetTy) return false;
 229     if (isVarArg < MTV.isVarArg) return true;
 230     if (isVarArg > MTV.isVarArg) return false;
 231     if (ArgTypes < MTV.ArgTypes) return true;
 232     if (ArgTypes > MTV.ArgTypes) return false;
 233     return false;
 234   }
 235 };
 236
 237 class TypeMapBase {
 238 protected:
 239   /// TypesByHash - Keep track of types by their structure hash value.  Note
 240   /// that we only keep track of types that have cycles through themselves in
 241   /// this map.
 242   ///
 243   std::multimap<unsigned, PATypeHolder> TypesByHash;
 244
 245   ~TypeMapBase() {
 246     // PATypeHolder won't destroy non-abstract types.
 247     // We can't destroy them by simply iterating, because
 248     // they may contain references to each-other.
 249     for (std::multimap<unsigned, PATypeHolder>::iterator I
 250          = TypesByHash.begin(), E = TypesByHash.end(); I != E; ++I) {
 251       Type *Ty = const_cast<Type*>(I->second.Ty);
 252       I->second.destroy();
 253       // We can't invoke destroy or delete, because the type may
 254       // contain references to already freed types.
 255       // So we have to destruct the object the ugly way.
 256       if (Ty) {
 257         Ty->AbstractTypeUsers.clear();
 258         static_cast<const Type*>(Ty)->Type::~Type();
 259         operator delete(Ty);
 260       }
 261     }
 262   }
 263
 264 public:
 265   void RemoveFromTypesByHash(unsigned Hash, const Type *Ty) {
 266     std::multimap<unsigned, PATypeHolder>::iterator I =
 267       TypesByHash.lower_bound(Hash);
 268     for (; I != TypesByHash.end() && I->first == Hash; ++I) {
 269       if (I->second == Ty) {
 270         TypesByHash.erase(I);
 271         return;
 272       }
 273     }
 274
 275     // This must be do to an opaque type that was resolved.  Switch down to hash
 276     // code of zero.
 277     assert(Hash && "Didn't find type entry!");
 278     RemoveFromTypesByHash(0, Ty);
 279   }
 280
 281   /// TypeBecameConcrete - When Ty gets a notification that TheType just became
 282   /// concrete, drop uses and make Ty non-abstract if we should.
 283   void TypeBecameConcrete(DerivedType *Ty, const DerivedType *TheType) {
 284     // If the element just became concrete, remove 'ty' from the abstract
 285     // type user list for the type.  Do this for as many times as Ty uses
 286     // OldType.
 287     for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
 288          I != E; ++I)
 289       if (I->get() == TheType)
 290         TheType->removeAbstractTypeUser(Ty);
 291
 292     // If the type is currently thought to be abstract, rescan all of our
 293     // subtypes to see if the type has just become concrete!  Note that this
 294     // may send out notifications to AbstractTypeUsers that types become
 295     // concrete.
 296     if (Ty->isAbstract())
 297       Ty->PromoteAbstractToConcrete();
 298   }
 299 };
 300
 301 // TypeMap - Make sure that only one instance of a particular type may be
 302 // created on any given run of the compiler... note that this involves updating
 303 // our map if an abstract type gets refined somehow.
 304 //
 305 template<class ValType, class TypeClass>
 306 class TypeMap : public TypeMapBase {
 307   std::map<ValType, PATypeHolder> Map;
 308 public:
 309   typedef typename std::map<ValType, PATypeHolder>::iterator iterator;
 310
 311   inline TypeClass *get(const ValType &V) {
 312     iterator I = Map.find(V);
 313     return I != Map.end() ? cast<TypeClass>((Type*)I->second.get()) : 0;
 314   }
 315
 316   inline void add(const ValType &V, TypeClass *Ty) {
 317     Map.insert(std::make_pair(V, Ty));
 318
 319     // If this type has a cycle, remember it.
 320     TypesByHash.insert(std::make_pair(ValType::hashTypeStructure(Ty), Ty));
 321     print("add");
 322   }
 323
 324   /// RefineAbstractType - This method is called after we have merged a type
 325   /// with another one.  We must now either merge the type away with
 326   /// some other type or reinstall it in the map with it's new configuration.
 327   void RefineAbstractType(TypeClass *Ty, const DerivedType *OldType,
 328                         const Type *NewType) {
 329 #ifdef DEBUG_MERGE_TYPES
 330     DEBUG(dbgs() << "RefineAbstractType(" << (void*)OldType << "[" << *OldType
 331                  << "], " << (void*)NewType << " [" << *NewType << "])\n");
 332 #endif
 333
 334     // Otherwise, we are changing one subelement type into another.  Clearly the
 335     // OldType must have been abstract, making us abstract.
 336     assert(Ty->isAbstract() && "Refining a non-abstract type!");
 337     assert(OldType != NewType);
 338
 339     // Make a temporary type holder for the type so that it doesn't disappear on
 340     // us when we erase the entry from the map.
 341     PATypeHolder TyHolder = Ty;
 342
 343     // The old record is now out-of-date, because one of the children has been
 344     // updated.  Remove the obsolete entry from the map.
 345     unsigned NumErased = Map.erase(ValType::get(Ty));
 346     assert(NumErased && "Element not found!"); NumErased = NumErased;
 347
 348     // Remember the structural hash for the type before we start hacking on it,
 349     // in case we need it later.
 350     unsigned OldTypeHash = ValType::hashTypeStructure(Ty);
 351
 352     // Find the type element we are refining... and change it now!
 353     for (unsigned i = 0, e = Ty->getNumContainedTypes(); i != e; ++i)
 354       if (Ty->ContainedTys[i] == OldType)
 355         Ty->ContainedTys[i] = NewType;
 356     unsigned NewTypeHash = ValType::hashTypeStructure(Ty);
 357
 358     // If there are no cycles going through this node, we can do a simple,
 359     // efficient lookup in the map, instead of an inefficient nasty linear
 360     // lookup.
 361     if (!TypeHasCycleThroughItself(Ty)) {
 362       typename std::map<ValType, PATypeHolder>::iterator I;
 363       bool Inserted;
 364
 365       tie(I, Inserted) = Map.insert(std::make_pair(ValType::get(Ty), Ty));
 366       if (!Inserted) {
 367         // Refined to a different type altogether?
 368         RemoveFromTypesByHash(OldTypeHash, Ty);
 369
 370         // We already have this type in the table.  Get rid of the newly refined
 371         // type.
 372         TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get());
 373         Ty->unlockedRefineAbstractTypeTo(NewTy);
 374         return;
 375       }
 376     } else {
 377       // Now we check to see if there is an existing entry in the table which is
 378       // structurally identical to the newly refined type.  If so, this type
 379       // gets refined to the pre-existing type.
 380       //
 381       std::multimap<unsigned, PATypeHolder>::iterator I, E, Entry;
 382       tie(I, E) = TypesByHash.equal_range(NewTypeHash);
 383       Entry = E;
 384       for (; I != E; ++I) {
 385         if (I->second == Ty) {
 386           // Remember the position of the old type if we see it in our scan.
 387           Entry = I;
 388         } else {
 389           if (TypesEqual(Ty, I->second)) {
 390             TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get());
 391
 392             // Remove the old entry form TypesByHash.  If the hash values differ
 393             // now, remove it from the old place.  Otherwise, continue scanning
 394             // withing this hashcode to reduce work.
 395             if (NewTypeHash != OldTypeHash) {
 396               RemoveFromTypesByHash(OldTypeHash, Ty);
 397             } else {
 398               if (Entry == E) {
 399                 // Find the location of Ty in the TypesByHash structure if we
 400                 // haven't seen it already.
 401                 while (I->second != Ty) {
 402                   ++I;
 403                   assert(I != E && "Structure doesn't contain type??");
 404                 }
 405                 Entry = I;
 406               }
 407               TypesByHash.erase(Entry);
 408             }
 409             Ty->unlockedRefineAbstractTypeTo(NewTy);
 410             return;
 411           }
 412         }
 413       }
 414
 415       // If there is no existing type of the same structure, we reinsert an
 416       // updated record into the map.
 417       Map.insert(std::make_pair(ValType::get(Ty), Ty));
 418     }
 419
 420     // If the hash codes differ, update TypesByHash
 421     if (NewTypeHash != OldTypeHash) {
 422       RemoveFromTypesByHash(OldTypeHash, Ty);
 423       TypesByHash.insert(std::make_pair(NewTypeHash, Ty));
 424     }
 425
 426     // If the type is currently thought to be abstract, rescan all of our
 427     // subtypes to see if the type has just become concrete!  Note that this
 428     // may send out notifications to AbstractTypeUsers that types become
 429     // concrete.
 430     if (Ty->isAbstract())
 431       Ty->PromoteAbstractToConcrete();
 432   }
 433
 434   void print(const char *Arg) const {
 435 #ifdef DEBUG_MERGE_TYPES
 436     DEBUG(dbgs() << "TypeMap<>::" << Arg << " table contents:\n");
 437     unsigned i = 0;
 438     for (typename std::map<ValType, PATypeHolder>::const_iterator I
 439            = Map.begin(), E = Map.end(); I != E; ++I)
 440       DEBUG(dbgs() << " " << (++i) << ". " << (void*)I->second.get() << " "
 441                    << *I->second.get() << "\n");
 442 #endif
 443   }
 444
 445   void dump() const { print("dump output"); }
 446 };
 447 }
 448
 449 #endif