1 //===-- TypesContext.h - Types-related Context Internals ------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines various helper methods and classes used by
11 // LLVMContextImpl for creating and managing types.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_TYPESCONTEXT_H
16 #define LLVM_TYPESCONTEXT_H
18 #include "llvm/ADT/STLExtras.h"
22 //===----------------------------------------------------------------------===//
23 // Derived Type Factory Functions
24 //===----------------------------------------------------------------------===//
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) {
33 for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
36 const Type *SubTy = I->get();
37 HashVal += SubTy->getTypeID();
38 switch (SubTy->getTypeID()) {
40 case Type::OpaqueTyID: return 0; // Opaque -> hash = 0 no matter what.
41 case Type::IntegerTyID:
42 HashVal ^= (cast<IntegerType>(SubTy)->getBitWidth() << 3);
44 case Type::FunctionTyID:
45 HashVal ^= cast<FunctionType>(SubTy)->getNumParams()*2 +
46 cast<FunctionType>(SubTy)->isVarArg();
49 HashVal ^= cast<ArrayType>(SubTy)->getNumElements();
51 case Type::VectorTyID:
52 HashVal ^= cast<VectorType>(SubTy)->getNumElements();
54 case Type::StructTyID:
55 HashVal ^= cast<StructType>(SubTy)->getNumElements();
57 case Type::PointerTyID:
58 HashVal ^= cast<PointerType>(SubTy)->getAddressSpace();
62 return HashVal ? HashVal : 1; // Do not return zero unless opaque subty.
65 //===----------------------------------------------------------------------===//
66 // Integer Type Factory...
68 class IntegerValType {
71 IntegerValType(uint16_t numbits) : bits(numbits) {}
73 static IntegerValType get(const IntegerType *Ty) {
74 return IntegerValType(Ty->getBitWidth());
77 static unsigned hashTypeStructure(const IntegerType *Ty) {
78 return (unsigned)Ty->getBitWidth();
81 inline bool operator<(const IntegerValType &IVT) const {
82 return bits < IVT.bits;
86 // PointerValType - Define a class to hold the key that goes into the TypeMap
88 class PointerValType {
90 unsigned AddressSpace;
92 PointerValType(const Type *val, unsigned as) : ValTy(val), AddressSpace(as) {}
94 static PointerValType get(const PointerType *PT) {
95 return PointerValType(PT->getElementType(), PT->getAddressSpace());
98 static unsigned hashTypeStructure(const PointerType *PT) {
99 return getSubElementHash(PT);
102 bool operator<(const PointerValType &MTV) const {
103 if (AddressSpace < MTV.AddressSpace) return true;
104 return AddressSpace == MTV.AddressSpace && ValTy < MTV.ValTy;
108 //===----------------------------------------------------------------------===//
109 // Array Type Factory...
115 ArrayValType(const Type *val, uint64_t sz) : ValTy(val), Size(sz) {}
117 static ArrayValType get(const ArrayType *AT) {
118 return ArrayValType(AT->getElementType(), AT->getNumElements());
121 static unsigned hashTypeStructure(const ArrayType *AT) {
122 return (unsigned)AT->getNumElements();
125 inline bool operator<(const ArrayValType &MTV) const {
126 if (Size < MTV.Size) return true;
127 return Size == MTV.Size && ValTy < MTV.ValTy;
131 //===----------------------------------------------------------------------===//
132 // Vector Type Factory...
134 class VectorValType {
138 VectorValType(const Type *val, int sz) : ValTy(val), Size(sz) {}
140 static VectorValType get(const VectorType *PT) {
141 return VectorValType(PT->getElementType(), PT->getNumElements());
144 static unsigned hashTypeStructure(const VectorType *PT) {
145 return PT->getNumElements();
148 inline bool operator<(const VectorValType &MTV) const {
149 if (Size < MTV.Size) return true;
150 return Size == MTV.Size && ValTy < MTV.ValTy;
154 // StructValType - Define a class to hold the key that goes into the TypeMap
156 class StructValType {
157 std::vector<const Type*> ElTypes;
160 StructValType(const std::vector<const Type*> &args, bool isPacked)
161 : ElTypes(args), packed(isPacked) {}
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));
169 return StructValType(ElTypes, ST->isPacked());
172 static unsigned hashTypeStructure(const StructType *ST) {
173 return ST->getNumElements();
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;
183 // FunctionValType - Define a class to hold the key that goes into the TypeMap
185 class FunctionValType {
187 std::vector<const Type*> ArgTypes;
190 FunctionValType(const Type *ret, const std::vector<const Type*> &args,
191 bool isVA) : RetTy(ret), ArgTypes(args), isVarArg(isVA) {}
193 static FunctionValType get(const FunctionType *FT);
195 static unsigned hashTypeStructure(const FunctionType *FT) {
196 unsigned Result = FT->getNumParams()*2 + FT->isVarArg();
200 inline bool operator<(const FunctionValType &MTV) const {
201 if (RetTy < MTV.RetTy) return true;
202 if (RetTy > MTV.RetTy) return false;
203 if (isVarArg < MTV.isVarArg) return true;
204 if (isVarArg > MTV.isVarArg) return false;
205 if (ArgTypes < MTV.ArgTypes) return true;
206 if (ArgTypes > MTV.ArgTypes) return false;
213 /// TypesByHash - Keep track of types by their structure hash value. Note
214 /// that we only keep track of types that have cycles through themselves in
217 std::multimap<unsigned, PATypeHolder> TypesByHash;
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);
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.
232 Ty->AbstractTypeUsers.clear();
233 static_cast<const Type*>(Ty)->Type::~Type();
239 void RemoveFromTypesByHash(unsigned Hash, const Type *Ty) {
240 std::multimap<unsigned, PATypeHolder>::iterator I =
241 TypesByHash.lower_bound(Hash);
242 for (; I != TypesByHash.end() && I->first == Hash; ++I) {
243 if (I->second == Ty) {
244 TypesByHash.erase(I);
249 // This must be do to an opaque type that was resolved. Switch down to hash
251 assert(Hash && "Didn't find type entry!");
252 RemoveFromTypesByHash(0, Ty);
255 /// TypeBecameConcrete - When Ty gets a notification that TheType just became
256 /// concrete, drop uses and make Ty non-abstract if we should.
257 void TypeBecameConcrete(DerivedType *Ty, const DerivedType *TheType) {
258 // If the element just became concrete, remove 'ty' from the abstract
259 // type user list for the type. Do this for as many times as Ty uses
261 for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
263 if (I->get() == TheType)
264 TheType->removeAbstractTypeUser(Ty);
266 // If the type is currently thought to be abstract, rescan all of our
267 // subtypes to see if the type has just become concrete! Note that this
268 // may send out notifications to AbstractTypeUsers that types become
270 if (Ty->isAbstract())
271 Ty->PromoteAbstractToConcrete();
275 // TypeMap - Make sure that only one instance of a particular type may be
276 // created on any given run of the compiler... note that this involves updating
277 // our map if an abstract type gets refined somehow.
279 template<class ValType, class TypeClass>
280 class TypeMap : public TypeMapBase {
281 std::map<ValType, PATypeHolder> Map;
283 typedef typename std::map<ValType, PATypeHolder>::iterator iterator;
284 ~TypeMap() { print("ON EXIT"); }
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;
291 inline void add(const ValType &V, TypeClass *Ty) {
292 Map.insert(std::make_pair(V, Ty));
294 // If this type has a cycle, remember it.
295 TypesByHash.insert(std::make_pair(ValType::hashTypeStructure(Ty), Ty));
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");
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);
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;
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!"); NumErased = NumErased;
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);
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);
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
336 if (!TypeHasCycleThroughItself(Ty)) {
337 typename std::map<ValType, PATypeHolder>::iterator I;
340 tie(I, Inserted) = Map.insert(std::make_pair(ValType::get(Ty), Ty));
342 // Refined to a different type altogether?
343 RemoveFromTypesByHash(OldTypeHash, Ty);
345 // We already have this type in the table. Get rid of the newly refined
347 TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get());
348 Ty->unlockedRefineAbstractTypeTo(NewTy);
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.
356 std::multimap<unsigned, PATypeHolder>::iterator I, E, Entry;
357 tie(I, E) = TypesByHash.equal_range(NewTypeHash);
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.
364 if (TypesEqual(Ty, I->second)) {
365 TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get());
367 // Remove the old entry form TypesByHash. If the hash values differ
368 // now, remove it from the old place. Otherwise, continue scanning
369 // withing this hashcode to reduce work.
370 if (NewTypeHash != OldTypeHash) {
371 RemoveFromTypesByHash(OldTypeHash, Ty);
374 // Find the location of Ty in the TypesByHash structure if we
375 // haven't seen it already.
376 while (I->second != Ty) {
378 assert(I != E && "Structure doesn't contain type??");
382 TypesByHash.erase(Entry);
384 Ty->unlockedRefineAbstractTypeTo(NewTy);
390 // If there is no existing type of the same structure, we reinsert an
391 // updated record into the map.
392 Map.insert(std::make_pair(ValType::get(Ty), Ty));
395 // If the hash codes differ, update TypesByHash
396 if (NewTypeHash != OldTypeHash) {
397 RemoveFromTypesByHash(OldTypeHash, Ty);
398 TypesByHash.insert(std::make_pair(NewTypeHash, Ty));
401 // If the type is currently thought to be abstract, rescan all of our
402 // subtypes to see if the type has just become concrete! Note that this
403 // may send out notifications to AbstractTypeUsers that types become
405 if (Ty->isAbstract())
406 Ty->PromoteAbstractToConcrete();
409 void print(const char *Arg) const {
410 #ifdef DEBUG_MERGE_TYPES
411 DEBUG(dbgs() << "TypeMap<>::" << Arg << " table contents:\n");
413 for (typename std::map<ValType, PATypeHolder>::const_iterator I
414 = Map.begin(), E = Map.end(); I != E; ++I)
415 DEBUG(dbgs() << " " << (++i) << ". " << (void*)I->second.get() << " "
416 << *I->second.get() << "\n");
420 void dump() const { print("dump output"); }