LLVM API Documentation

TypesContext.h

Go to the documentation of this file.
00001 //===-------------------- TypesContext.h - Implementation ------*- C++ -*--===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 //  This file defines various helper methods and classes used by
00011 // LLVMContextImpl for creating and managing types.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #ifndef LLVM_TYPESCONTEXT_H
00016 #define LLVM_TYPESCONTEXT_H
00017 
00018 #include "llvm/ADT/STLExtras.h"
00019 #include <map>
00020 
00021 
00022 //===----------------------------------------------------------------------===//
00023 //                       Derived Type Factory Functions
00024 //===----------------------------------------------------------------------===//
00025 namespace llvm {
00026 
00027 /// getSubElementHash - Generate a hash value for all of the SubType's of this
00028 /// type.  The hash value is guaranteed to be zero if any of the subtypes are 
00029 /// an opaque type.  Otherwise we try to mix them in as well as possible, but do
00030 /// not look at the subtype's subtype's.
00031 static unsigned getSubElementHash(const Type *Ty) {
00032   unsigned HashVal = 0;
00033   for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
00034        I != E; ++I) {
00035     HashVal *= 32;
00036     const Type *SubTy = I->get();
00037     HashVal += SubTy->getTypeID();
00038     switch (SubTy->getTypeID()) {
00039     default: break;
00040     case Type::OpaqueTyID: return 0;    // Opaque -> hash = 0 no matter what.
00041     case Type::IntegerTyID:
00042       HashVal ^= (cast<IntegerType>(SubTy)->getBitWidth() << 3);
00043       break;
00044     case Type::FunctionTyID:
00045       HashVal ^= cast<FunctionType>(SubTy)->getNumParams()*2 + 
00046                  cast<FunctionType>(SubTy)->isVarArg();
00047       break;
00048     case Type::ArrayTyID:
00049       HashVal ^= cast<ArrayType>(SubTy)->getNumElements();
00050       break;
00051     case Type::VectorTyID:
00052       HashVal ^= cast<VectorType>(SubTy)->getNumElements();
00053       break;
00054     case Type::StructTyID:
00055       HashVal ^= cast<StructType>(SubTy)->getNumElements();
00056       break;
00057     case Type::PointerTyID:
00058       HashVal ^= cast<PointerType>(SubTy)->getAddressSpace();
00059       break;
00060     }
00061   }
00062   return HashVal ? HashVal : 1;  // Do not return zero unless opaque subty.
00063 }
00064 
00065 //===----------------------------------------------------------------------===//
00066 // Integer Type Factory...
00067 //
00068 class IntegerValType {
00069   uint32_t bits;
00070 public:
00071   IntegerValType(uint16_t numbits) : bits(numbits) {}
00072 
00073   static IntegerValType get(const IntegerType *Ty) {
00074     return IntegerValType(Ty->getBitWidth());
00075   }
00076 
00077   static unsigned hashTypeStructure(const IntegerType *Ty) {
00078     return (unsigned)Ty->getBitWidth();
00079   }
00080 
00081   inline bool operator<(const IntegerValType &IVT) const {
00082     return bits < IVT.bits;
00083   }
00084 };
00085 
00086 // PointerValType - Define a class to hold the key that goes into the TypeMap
00087 //
00088 class PointerValType {
00089   const Type *ValTy;
00090   unsigned AddressSpace;
00091 public:
00092   PointerValType(const Type *val, unsigned as) : ValTy(val), AddressSpace(as) {}
00093 
00094   static PointerValType get(const PointerType *PT) {
00095     return PointerValType(PT->getElementType(), PT->getAddressSpace());
00096   }
00097 
00098   static unsigned hashTypeStructure(const PointerType *PT) {
00099     return getSubElementHash(PT);
00100   }
00101 
00102   bool operator<(const PointerValType &MTV) const {
00103     if (AddressSpace < MTV.AddressSpace) return true;
00104     return AddressSpace == MTV.AddressSpace && ValTy < MTV.ValTy;
00105   }
00106 };
00107 
00108 //===----------------------------------------------------------------------===//
00109 // Array Type Factory...
00110 //
00111 class ArrayValType {
00112   const Type *ValTy;
00113   uint64_t Size;
00114 public:
00115   ArrayValType(const Type *val, uint64_t sz) : ValTy(val), Size(sz) {}
00116 
00117   static ArrayValType get(const ArrayType *AT) {
00118     return ArrayValType(AT->getElementType(), AT->getNumElements());
00119   }
00120 
00121   static unsigned hashTypeStructure(const ArrayType *AT) {
00122     return (unsigned)AT->getNumElements();
00123   }
00124 
00125   inline bool operator<(const ArrayValType &MTV) const {
00126     if (Size < MTV.Size) return true;
00127     return Size == MTV.Size && ValTy < MTV.ValTy;
00128   }
00129 };
00130 
00131 //===----------------------------------------------------------------------===//
00132 // Vector Type Factory...
00133 //
00134 class VectorValType {
00135   const Type *ValTy;
00136   unsigned Size;
00137 public:
00138   VectorValType(const Type *val, int sz) : ValTy(val), Size(sz) {}
00139 
00140   static VectorValType get(const VectorType *PT) {
00141     return VectorValType(PT->getElementType(), PT->getNumElements());
00142   }
00143 
00144   static unsigned hashTypeStructure(const VectorType *PT) {
00145     return PT->getNumElements();
00146   }
00147 
00148   inline bool operator<(const VectorValType &MTV) const {
00149     if (Size < MTV.Size) return true;
00150     return Size == MTV.Size && ValTy < MTV.ValTy;
00151   }
00152 };
00153 
00154 // StructValType - Define a class to hold the key that goes into the TypeMap
00155 //
00156 class StructValType {
00157   std::vector<const Type*> ElTypes;
00158   bool packed;
00159 public:
00160   StructValType(const std::vector<const Type*> &args, bool isPacked)
00161     : ElTypes(args), packed(isPacked) {}
00162 
00163   static StructValType get(const StructType *ST) {
00164     std::vector<const Type *> ElTypes;
00165     ElTypes.reserve(ST->getNumElements());
00166     for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i)
00167       ElTypes.push_back(ST->getElementType(i));
00168 
00169     return StructValType(ElTypes, ST->isPacked());
00170   }
00171 
00172   static unsigned hashTypeStructure(const StructType *ST) {
00173     return ST->getNumElements();
00174   }
00175 
00176   inline bool operator<(const StructValType &STV) const {
00177     if (ElTypes < STV.ElTypes) return true;
00178     else if (ElTypes > STV.ElTypes) return false;
00179     else return (int)packed < (int)STV.packed;
00180   }
00181 };
00182 
00183 // FunctionValType - Define a class to hold the key that goes into the TypeMap
00184 //
00185 class FunctionValType {
00186   const Type *RetTy;
00187   std::vector<const Type*> ArgTypes;
00188   bool isVarArg;
00189 public:
00190   FunctionValType(const Type *ret, const std::vector<const Type*> &args,
00191                   bool isVA) : RetTy(ret), ArgTypes(args), isVarArg(isVA) {}
00192 
00193   static FunctionValType get(const FunctionType *FT);
00194 
00195   static unsigned hashTypeStructure(const FunctionType *FT) {
00196     unsigned Result = FT->getNumParams()*2 + FT->isVarArg();
00197     return Result;
00198   }
00199 
00200   inline bool operator<(const FunctionValType &MTV) const {
00201     if (RetTy < MTV.RetTy) return true;
00202     if (RetTy > MTV.RetTy) return false;
00203     if (isVarArg < MTV.isVarArg) return true;
00204     if (isVarArg > MTV.isVarArg) return false;
00205     if (ArgTypes < MTV.ArgTypes) return true;
00206     if (ArgTypes > MTV.ArgTypes) return false;
00207     return false;
00208   }
00209 };
00210 
00211 class TypeMapBase {
00212 protected:
00213   /// TypesByHash - Keep track of types by their structure hash value.  Note
00214   /// that we only keep track of types that have cycles through themselves in
00215   /// this map.
00216   ///
00217   std::multimap<unsigned, PATypeHolder> TypesByHash;
00218 
00219 public:
00220   ~TypeMapBase() {
00221     // PATypeHolder won't destroy non-abstract types.
00222     // We can't destroy them by simply iterating, because
00223     // they may contain references to each-other.
00224 #if 0
00225     for (std::multimap<unsigned, PATypeHolder>::iterator I
00226          = TypesByHash.begin(), E = TypesByHash.end(); I != E; ++I) {
00227       Type *Ty = const_cast<Type*>(I->second.Ty);
00228       I->second.destroy();
00229       // We can't invoke destroy or delete, because the type may
00230       // contain references to already freed types.
00231       // So we have to destruct the object the ugly way.
00232       if (Ty) {
00233         Ty->AbstractTypeUsers.clear();
00234         static_cast<const Type*>(Ty)->Type::~Type();
00235         operator delete(Ty);
00236       }
00237     }
00238 #endif
00239   }
00240 
00241   void RemoveFromTypesByHash(unsigned Hash, const Type *Ty) {
00242     std::multimap<unsigned, PATypeHolder>::iterator I =
00243       TypesByHash.lower_bound(Hash);
00244     for (; I != TypesByHash.end() && I->first == Hash; ++I) {
00245       if (I->second == Ty) {
00246         TypesByHash.erase(I);
00247         return;
00248       }
00249     }
00250 
00251     // This must be do to an opaque type that was resolved.  Switch down to hash
00252     // code of zero.
00253     assert(Hash && "Didn't find type entry!");
00254     RemoveFromTypesByHash(0, Ty);
00255   }
00256 
00257   /// TypeBecameConcrete - When Ty gets a notification that TheType just became
00258   /// concrete, drop uses and make Ty non-abstract if we should.
00259   void TypeBecameConcrete(DerivedType *Ty, const DerivedType *TheType) {
00260     // If the element just became concrete, remove 'ty' from the abstract
00261     // type user list for the type.  Do this for as many times as Ty uses
00262     // OldType.
00263     for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
00264          I != E; ++I)
00265       if (I->get() == TheType)
00266         TheType->removeAbstractTypeUser(Ty);
00267 
00268     // If the type is currently thought to be abstract, rescan all of our
00269     // subtypes to see if the type has just become concrete!  Note that this
00270     // may send out notifications to AbstractTypeUsers that types become
00271     // concrete.
00272     if (Ty->isAbstract())
00273       Ty->PromoteAbstractToConcrete();
00274   }
00275 };
00276 
00277 // TypeMap - Make sure that only one instance of a particular type may be
00278 // created on any given run of the compiler... note that this involves updating
00279 // our map if an abstract type gets refined somehow.
00280 //
00281 template<class ValType, class TypeClass>
00282 class TypeMap : public TypeMapBase {
00283   std::map<ValType, PATypeHolder> Map;
00284 public:
00285   typedef typename std::map<ValType, PATypeHolder>::iterator iterator;
00286   ~TypeMap() { print("ON EXIT"); }
00287 
00288   inline TypeClass *get(const ValType &V) {
00289     iterator I = Map.find(V);
00290     return I != Map.end() ? cast<TypeClass>((Type*)I->second.get()) : 0;
00291   }
00292 
00293   inline void add(const ValType &V, TypeClass *Ty) {
00294     Map.insert(std::make_pair(V, Ty));
00295 
00296     // If this type has a cycle, remember it.
00297     TypesByHash.insert(std::make_pair(ValType::hashTypeStructure(Ty), Ty));
00298     print("add");
00299   }
00300   
00301   /// RefineAbstractType - This method is called after we have merged a type
00302   /// with another one.  We must now either merge the type away with
00303   /// some other type or reinstall it in the map with it's new configuration.
00304   void RefineAbstractType(TypeClass *Ty, const DerivedType *OldType,
00305                         const Type *NewType) {
00306 #ifdef DEBUG_MERGE_TYPES
00307     DOUT << "RefineAbstractType(" << (void*)OldType << "[" << *OldType
00308          << "], " << (void*)NewType << " [" << *NewType << "])\n";
00309 #endif
00310     
00311     // Otherwise, we are changing one subelement type into another.  Clearly the
00312     // OldType must have been abstract, making us abstract.
00313     assert(Ty->isAbstract() && "Refining a non-abstract type!");
00314     assert(OldType != NewType);
00315 
00316     // Make a temporary type holder for the type so that it doesn't disappear on
00317     // us when we erase the entry from the map.
00318     PATypeHolder TyHolder = Ty;
00319 
00320     // The old record is now out-of-date, because one of the children has been
00321     // updated.  Remove the obsolete entry from the map.
00322     unsigned NumErased = Map.erase(ValType::get(Ty));
00323     assert(NumErased && "Element not found!"); NumErased = NumErased;
00324 
00325     // Remember the structural hash for the type before we start hacking on it,
00326     // in case we need it later.
00327     unsigned OldTypeHash = ValType::hashTypeStructure(Ty);
00328 
00329     // Find the type element we are refining... and change it now!
00330     for (unsigned i = 0, e = Ty->getNumContainedTypes(); i != e; ++i)
00331       if (Ty->ContainedTys[i] == OldType)
00332         Ty->ContainedTys[i] = NewType;
00333     unsigned NewTypeHash = ValType::hashTypeStructure(Ty);
00334     
00335     // If there are no cycles going through this node, we can do a simple,
00336     // efficient lookup in the map, instead of an inefficient nasty linear
00337     // lookup.
00338     if (!TypeHasCycleThroughItself(Ty)) {
00339       typename std::map<ValType, PATypeHolder>::iterator I;
00340       bool Inserted;
00341 
00342       tie(I, Inserted) = Map.insert(std::make_pair(ValType::get(Ty), Ty));
00343       if (!Inserted) {
00344         // Refined to a different type altogether?
00345         RemoveFromTypesByHash(OldTypeHash, Ty);
00346 
00347         // We already have this type in the table.  Get rid of the newly refined
00348         // type.
00349         TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get());
00350         Ty->unlockedRefineAbstractTypeTo(NewTy);
00351         return;
00352       }
00353     } else {
00354       // Now we check to see if there is an existing entry in the table which is
00355       // structurally identical to the newly refined type.  If so, this type
00356       // gets refined to the pre-existing type.
00357       //
00358       std::multimap<unsigned, PATypeHolder>::iterator I, E, Entry;
00359       tie(I, E) = TypesByHash.equal_range(NewTypeHash);
00360       Entry = E;
00361       for (; I != E; ++I) {
00362         if (I->second == Ty) {
00363           // Remember the position of the old type if we see it in our scan.
00364           Entry = I;
00365         } else {
00366           if (TypesEqual(Ty, I->second)) {
00367             TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get());
00368 
00369             // Remove the old entry form TypesByHash.  If the hash values differ
00370             // now, remove it from the old place.  Otherwise, continue scanning
00371             // withing this hashcode to reduce work.
00372             if (NewTypeHash != OldTypeHash) {
00373               RemoveFromTypesByHash(OldTypeHash, Ty);
00374             } else {
00375               if (Entry == E) {
00376                 // Find the location of Ty in the TypesByHash structure if we
00377                 // haven't seen it already.
00378                 while (I->second != Ty) {
00379                   ++I;
00380                   assert(I != E && "Structure doesn't contain type??");
00381                 }
00382                 Entry = I;
00383               }
00384               TypesByHash.erase(Entry);
00385             }
00386             Ty->unlockedRefineAbstractTypeTo(NewTy);
00387             return;
00388           }
00389         }
00390       }
00391 
00392       // If there is no existing type of the same structure, we reinsert an
00393       // updated record into the map.
00394       Map.insert(std::make_pair(ValType::get(Ty), Ty));
00395     }
00396 
00397     // If the hash codes differ, update TypesByHash
00398     if (NewTypeHash != OldTypeHash) {
00399       RemoveFromTypesByHash(OldTypeHash, Ty);
00400       TypesByHash.insert(std::make_pair(NewTypeHash, Ty));
00401     }
00402     
00403     // If the type is currently thought to be abstract, rescan all of our
00404     // subtypes to see if the type has just become concrete!  Note that this
00405     // may send out notifications to AbstractTypeUsers that types become
00406     // concrete.
00407     if (Ty->isAbstract())
00408       Ty->PromoteAbstractToConcrete();
00409   }
00410 
00411   void print(const char *Arg) const {
00412 #ifdef DEBUG_MERGE_TYPES
00413     DOUT << "TypeMap<>::" << Arg << " table contents:\n";
00414     unsigned i = 0;
00415     for (typename std::map<ValType, PATypeHolder>::const_iterator I
00416            = Map.begin(), E = Map.end(); I != E; ++I)
00417       DOUT << " " << (++i) << ". " << (void*)I->second.get() << " "
00418            << *I->second.get() << "\n";
00419 #endif
00420   }
00421 
00422   void dump() const { print("dump output"); }
00423 };
00424 }
00425 
00426 #endif