#ifndef LLVM_TYPESCONTEXT_H
#define LLVM_TYPESCONTEXT_H
#include "llvm/ADT/STLExtras.h"
#include <map>
namespace llvm {
static unsigned getSubElementHash(const Type *Ty) {
unsigned HashVal = 0;
for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
I != E; ++I) {
HashVal *= 32;
const Type *SubTy = I->get();
HashVal += SubTy->getTypeID();
switch (SubTy->getTypeID()) {
default: break;
case Type::OpaqueTyID: return 0; case Type::IntegerTyID:
HashVal ^= (cast<IntegerType>(SubTy)->getBitWidth() << 3);
break;
case Type::FunctionTyID:
HashVal ^= cast<FunctionType>(SubTy)->getNumParams()*2 +
cast<FunctionType>(SubTy)->isVarArg();
break;
case Type::ArrayTyID:
HashVal ^= cast<ArrayType>(SubTy)->getNumElements();
break;
case Type::VectorTyID:
HashVal ^= cast<VectorType>(SubTy)->getNumElements();
break;
case Type::StructTyID:
HashVal ^= cast<StructType>(SubTy)->getNumElements();
break;
case Type::PointerTyID:
HashVal ^= cast<PointerType>(SubTy)->getAddressSpace();
break;
}
}
return HashVal ? HashVal : 1; }
class IntegerValType {
uint32_t bits;
public:
IntegerValType(uint32_t numbits) : bits(numbits) {}
static IntegerValType get(const IntegerType *Ty) {
return IntegerValType(Ty->getBitWidth());
}
static unsigned hashTypeStructure(const IntegerType *Ty) {
return (unsigned)Ty->getBitWidth();
}
inline bool operator<(const IntegerValType &IVT) const {
return bits < IVT.bits;
}
};
class PointerValType {
const Type *ValTy;
unsigned AddressSpace;
public:
PointerValType(const Type *val, unsigned as) : ValTy(val), AddressSpace(as) {}
static PointerValType get(const PointerType *PT) {
return PointerValType(PT->getElementType(), PT->getAddressSpace());
}
static unsigned hashTypeStructure(const PointerType *PT) {
return getSubElementHash(PT);
}
bool operator<(const PointerValType &MTV) const {
if (AddressSpace < MTV.AddressSpace) return true;
return AddressSpace == MTV.AddressSpace && ValTy < MTV.ValTy;
}
};
class ArrayValType {
const Type *ValTy;
uint64_t Size;
public:
ArrayValType(const Type *val, uint64_t sz) : ValTy(val), Size(sz) {}
static ArrayValType get(const ArrayType *AT) {
return ArrayValType(AT->getElementType(), AT->getNumElements());
}
static unsigned hashTypeStructure(const ArrayType *AT) {
return (unsigned)AT->getNumElements();
}
inline bool operator<(const ArrayValType &MTV) const {
if (Size < MTV.Size) return true;
return Size == MTV.Size && ValTy < MTV.ValTy;
}
};
class VectorValType {
const Type *ValTy;
unsigned Size;
public:
VectorValType(const Type *val, int sz) : ValTy(val), Size(sz) {}
static VectorValType get(const VectorType *PT) {
return VectorValType(PT->getElementType(), PT->getNumElements());
}
static unsigned hashTypeStructure(const VectorType *PT) {
return PT->getNumElements();
}
inline bool operator<(const VectorValType &MTV) const {
if (Size < MTV.Size) return true;
return Size == MTV.Size && ValTy < MTV.ValTy;
}
};
class StructValType {
std::vector<const Type*> ElTypes;
bool packed;
public:
StructValType(const std::vector<const Type*> &args, bool isPacked)
: ElTypes(args), packed(isPacked) {}
static StructValType get(const StructType *ST) {
std::vector<const Type *> ElTypes;
ElTypes.reserve(ST->getNumElements());
for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i)
ElTypes.push_back(ST->getElementType(i));
return StructValType(ElTypes, ST->isPacked());
}
static unsigned hashTypeStructure(const StructType *ST) {
return ST->getNumElements();
}
inline bool operator<(const StructValType &STV) const {
if (ElTypes < STV.ElTypes) return true;
else if (ElTypes > STV.ElTypes) return false;
else return (int)packed < (int)STV.packed;
}
};
class UnionValType {
std::vector<const Type*> ElTypes;
public:
UnionValType(const Type* const* Types, unsigned NumTypes)
: ElTypes(&Types[0], &Types[NumTypes]) {}
static UnionValType get(const UnionType *UT) {
std::vector<const Type *> ElTypes;
ElTypes.reserve(UT->getNumElements());
for (unsigned i = 0, e = UT->getNumElements(); i != e; ++i)
ElTypes.push_back(UT->getElementType(i));
return UnionValType(&ElTypes[0], ElTypes.size());
}
static unsigned hashTypeStructure(const UnionType *UT) {
return UT->getNumElements();
}
inline bool operator<(const UnionValType &UTV) const {
return (ElTypes < UTV.ElTypes);
}
};
class FunctionValType {
const Type *RetTy;
std::vector<const Type*> ArgTypes;
bool isVarArg;
public:
FunctionValType(const Type *ret, const std::vector<const Type*> &args,
bool isVA) : RetTy(ret), ArgTypes(args), isVarArg(isVA) {}
static FunctionValType get(const FunctionType *FT);
static unsigned hashTypeStructure(const FunctionType *FT) {
unsigned Result = FT->getNumParams()*2 + FT->isVarArg();
return Result;
}
inline bool operator<(const FunctionValType &MTV) const {
if (RetTy < MTV.RetTy) return true;
if (RetTy > MTV.RetTy) return false;
if (isVarArg < MTV.isVarArg) return true;
if (isVarArg > MTV.isVarArg) return false;
if (ArgTypes < MTV.ArgTypes) return true;
if (ArgTypes > MTV.ArgTypes) return false;
return false;
}
};
class TypeMapBase {
protected:
std::multimap<unsigned, PATypeHolder> TypesByHash;
~TypeMapBase() {
for (std::multimap<unsigned, PATypeHolder>::iterator I
= TypesByHash.begin(), E = TypesByHash.end(); I != E; ++I) {
Type *Ty = const_cast<Type*>(I->second.Ty);
I->second.destroy();
if (Ty) {
Ty->AbstractTypeUsers.clear();
static_cast<const Type*>(Ty)->Type::~Type();
operator delete(Ty);
}
}
}
public:
void RemoveFromTypesByHash(unsigned Hash, const Type *Ty) {
std::multimap<unsigned, PATypeHolder>::iterator I =
TypesByHash.lower_bound(Hash);
for (; I != TypesByHash.end() && I->first == Hash; ++I) {
if (I->second == Ty) {
TypesByHash.erase(I);
return;
}
}
assert(Hash && "Didn't find type entry!");
RemoveFromTypesByHash(0, Ty);
}
void TypeBecameConcrete(DerivedType *Ty, const DerivedType *TheType) {
for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
I != E; ++I)
if (I->get() == TheType)
TheType->removeAbstractTypeUser(Ty);
if (Ty->isAbstract())
Ty->PromoteAbstractToConcrete();
}
};
template<class ValType, class TypeClass>
class TypeMap : public TypeMapBase {
std::map<ValType, PATypeHolder> Map;
public:
typedef typename std::map<ValType, PATypeHolder>::iterator iterator;
inline TypeClass *get(const ValType &V) {
iterator I = Map.find(V);
return I != Map.end() ? cast<TypeClass>((Type*)I->second.get()) : 0;
}
inline void add(const ValType &V, TypeClass *Ty) {
Map.insert(std::make_pair(V, Ty));
TypesByHash.insert(std::make_pair(ValType::hashTypeStructure(Ty), Ty));
print("add");
}
void RefineAbstractType(TypeClass *Ty, const DerivedType *OldType,
const Type *NewType) {
#ifdef DEBUG_MERGE_TYPES
DEBUG(dbgs() << "RefineAbstractType(" << (void*)OldType << "[" << *OldType
<< "], " << (void*)NewType << " [" << *NewType << "])\n");
#endif
assert(Ty->isAbstract() && "Refining a non-abstract type!");
assert(OldType != NewType);
PATypeHolder TyHolder = Ty;
unsigned NumErased = Map.erase(ValType::get(Ty));
assert(NumErased && "Element not found!"); NumErased = NumErased;
unsigned OldTypeHash = ValType::hashTypeStructure(Ty);
for (unsigned i = 0, e = Ty->getNumContainedTypes(); i != e; ++i)
if (Ty->ContainedTys[i] == OldType)
Ty->ContainedTys[i] = NewType;
unsigned NewTypeHash = ValType::hashTypeStructure(Ty);
if (!TypeHasCycleThroughItself(Ty)) {
typename std::map<ValType, PATypeHolder>::iterator I;
bool Inserted;
tie(I, Inserted) = Map.insert(std::make_pair(ValType::get(Ty), Ty));
if (!Inserted) {
RemoveFromTypesByHash(OldTypeHash, Ty);
TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get());
Ty->unlockedRefineAbstractTypeTo(NewTy);
return;
}
} else {
std::multimap<unsigned, PATypeHolder>::iterator I, E, Entry;
tie(I, E) = TypesByHash.equal_range(NewTypeHash);
Entry = E;
for (; I != E; ++I) {
if (I->second == Ty) {
Entry = I;
} else {
if (TypesEqual(Ty, I->second)) {
TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get());
if (NewTypeHash != OldTypeHash) {
RemoveFromTypesByHash(OldTypeHash, Ty);
} else {
if (Entry == E) {
while (I->second != Ty) {
++I;
assert(I != E && "Structure doesn't contain type??");
}
Entry = I;
}
TypesByHash.erase(Entry);
}
Ty->unlockedRefineAbstractTypeTo(NewTy);
return;
}
}
}
Map.insert(std::make_pair(ValType::get(Ty), Ty));
}
if (NewTypeHash != OldTypeHash) {
RemoveFromTypesByHash(OldTypeHash, Ty);
TypesByHash.insert(std::make_pair(NewTypeHash, Ty));
}
if (Ty->isAbstract())
Ty->PromoteAbstractToConcrete();
}
void print(const char *Arg) const {
#ifdef DEBUG_MERGE_TYPES
DEBUG(dbgs() << "TypeMap<>::" << Arg << " table contents:\n");
unsigned i = 0;
for (typename std::map<ValType, PATypeHolder>::const_iterator I
= Map.begin(), E = Map.end(); I != E; ++I)
DEBUG(dbgs() << " " << (++i) << ". " << (void*)I->second.get() << " "
<< *I->second.get() << "\n");
#endif
}
void dump() const { print("dump output"); }
};
}
#endif