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