LLVM API Documentation
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