#include "llvm/DerivedTypes.h"
#include "llvm/Constants.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ManagedStatic.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cstdarg>
using namespace llvm;
AbstractTypeUser::~AbstractTypeUser() {}
static ManagedStatic<TypePrinting> ConcreteTypeDescriptions;
static ManagedStatic<TypePrinting> AbstractTypeDescriptions;
void Type::destroy() const {
if (isa<FunctionType>(this) || isa<StructType>(this)) {
for (unsigned i = 0; i < NumContainedTys; ++i)
ContainedTys[i].PATypeHandle::~PATypeHandle();
if (isa<FunctionType>(this))
static_cast<const FunctionType*>(this)->FunctionType::~FunctionType();
else
static_cast<const StructType*>(this)->StructType::~StructType();
operator delete(const_cast<Type *>(this));
return;
}
delete this;
}
const Type *Type::getPrimitiveType(TypeID IDNumber) {
switch (IDNumber) {
case VoidTyID : return VoidTy;
case FloatTyID : return FloatTy;
case DoubleTyID : return DoubleTy;
case X86_FP80TyID : return X86_FP80Ty;
case FP128TyID : return FP128Ty;
case PPC_FP128TyID : return PPC_FP128Ty;
case LabelTyID : return LabelTy;
default:
return 0;
}
}
const Type *Type::getVAArgsPromotedType() const {
if (ID == IntegerTyID && getSubclassData() < 32)
return Type::Int32Ty;
else if (ID == FloatTyID)
return Type::DoubleTy;
else
return this;
}
bool Type::isIntOrIntVector() const {
if (isInteger())
return true;
if (ID != Type::VectorTyID) return false;
return cast<VectorType>(this)->getElementType()->isInteger();
}
bool Type::isFPOrFPVector() const {
if (ID == Type::FloatTyID || ID == Type::DoubleTyID ||
ID == Type::FP128TyID || ID == Type::X86_FP80TyID ||
ID == Type::PPC_FP128TyID)
return true;
if (ID != Type::VectorTyID) return false;
return cast<VectorType>(this)->getElementType()->isFloatingPoint();
}
bool Type::canLosslesslyBitCastTo(const Type *Ty) const {
if (this == Ty)
return true;
if (!this->isFirstClassType() || !Ty->isFirstClassType())
return false;
if (const VectorType *thisPTy = dyn_cast<VectorType>(this))
if (const VectorType *thatPTy = dyn_cast<VectorType>(Ty))
return thisPTy->getBitWidth() == thatPTy->getBitWidth();
if (isa<PointerType>(this))
return isa<PointerType>(Ty);
return false; }
unsigned Type::getPrimitiveSizeInBits() const {
switch (getTypeID()) {
case Type::FloatTyID: return 32;
case Type::DoubleTyID: return 64;
case Type::X86_FP80TyID: return 80;
case Type::FP128TyID: return 128;
case Type::PPC_FP128TyID: return 128;
case Type::IntegerTyID: return cast<IntegerType>(this)->getBitWidth();
case Type::VectorTyID: return cast<VectorType>(this)->getBitWidth();
default: return 0;
}
}
bool Type::isSizedDerivedType() const {
if (isa<IntegerType>(this))
return true;
if (const ArrayType *ATy = dyn_cast<ArrayType>(this))
return ATy->getElementType()->isSized();
if (const VectorType *PTy = dyn_cast<VectorType>(this))
return PTy->getElementType()->isSized();
if (!isa<StructType>(this))
return false;
for (subtype_iterator I = subtype_begin(), E = subtype_end(); I != E; ++I)
if (!(*I)->isSized())
return false;
return true;
}
const Type *Type::getForwardedTypeInternal() const {
assert(ForwardType && "This type is not being forwarded to another type!");
const Type *RealForwardedType = ForwardType->getForwardedType();
if (!RealForwardedType)
return ForwardType;
if (RealForwardedType->isAbstract())
cast<DerivedType>(RealForwardedType)->addRef();
cast<DerivedType>(ForwardType)->dropRef();
ForwardType = RealForwardedType;
return ForwardType;
}
void Type::refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
abort();
}
void Type::typeBecameConcrete(const DerivedType *AbsTy) {
abort();
}
std::string Type::getDescription() const {
TypePrinting &Map =
isAbstract() ? *AbstractTypeDescriptions : *ConcreteTypeDescriptions;
std::string DescStr;
raw_string_ostream DescOS(DescStr);
Map.print(this, DescOS);
return DescOS.str();
}
bool StructType::indexValid(const Value *V) const {
if (V->getType() == Type::Int32Ty)
if (const ConstantInt *CU = dyn_cast<ConstantInt>(V))
return indexValid(CU->getZExtValue());
return false;
}
bool StructType::indexValid(unsigned V) const {
return V < NumContainedTys;
}
const Type *StructType::getTypeAtIndex(const Value *V) const {
unsigned Idx = (unsigned)cast<ConstantInt>(V)->getZExtValue();
return getTypeAtIndex(Idx);
}
const Type *StructType::getTypeAtIndex(unsigned Idx) const {
assert(indexValid(Idx) && "Invalid structure index!");
return ContainedTys[Idx];
}
const Type *Type::VoidTy = new Type(Type::VoidTyID);
const Type *Type::FloatTy = new Type(Type::FloatTyID);
const Type *Type::DoubleTy = new Type(Type::DoubleTyID);
const Type *Type::X86_FP80Ty = new Type(Type::X86_FP80TyID);
const Type *Type::FP128Ty = new Type(Type::FP128TyID);
const Type *Type::PPC_FP128Ty = new Type(Type::PPC_FP128TyID);
const Type *Type::LabelTy = new Type(Type::LabelTyID);
namespace {
struct BuiltinIntegerType : public IntegerType {
explicit BuiltinIntegerType(unsigned W) : IntegerType(W) {}
};
}
const IntegerType *Type::Int1Ty = new BuiltinIntegerType(1);
const IntegerType *Type::Int8Ty = new BuiltinIntegerType(8);
const IntegerType *Type::Int16Ty = new BuiltinIntegerType(16);
const IntegerType *Type::Int32Ty = new BuiltinIntegerType(32);
const IntegerType *Type::Int64Ty = new BuiltinIntegerType(64);
const Type *Type::EmptyStructTy = StructType::get(NULL, NULL);
bool FunctionType::isValidReturnType(const Type *RetTy) {
if (RetTy->isFirstClassType())
return true;
if (RetTy == Type::VoidTy || isa<OpaqueType>(RetTy))
return true;
const StructType *SRetTy = dyn_cast<StructType>(RetTy);
if (SRetTy == 0 || SRetTy->getNumElements() == 0)
return false;
for (unsigned i = 0, e = SRetTy->getNumElements(); i != e; ++i)
if (!SRetTy->getElementType(i)->isFirstClassType())
return false;
return true;
}
FunctionType::FunctionType(const Type *Result,
const std::vector<const Type*> &Params,
bool IsVarArgs)
: DerivedType(FunctionTyID), isVarArgs(IsVarArgs) {
ContainedTys = reinterpret_cast<PATypeHandle*>(this+1);
NumContainedTys = Params.size() + 1; assert(isValidReturnType(Result) && "invalid return type for function");
bool isAbstract = Result->isAbstract();
new (&ContainedTys[0]) PATypeHandle(Result, this);
for (unsigned i = 0; i != Params.size(); ++i) {
assert((Params[i]->isFirstClassType() || isa<OpaqueType>(Params[i])) &&
"Function arguments must be value types!");
new (&ContainedTys[i+1]) PATypeHandle(Params[i],this);
isAbstract |= Params[i]->isAbstract();
}
setAbstract(isAbstract);
}
StructType::StructType(const std::vector<const Type*> &Types, bool isPacked)
: CompositeType(StructTyID) {
ContainedTys = reinterpret_cast<PATypeHandle*>(this + 1);
NumContainedTys = Types.size();
setSubclassData(isPacked);
bool isAbstract = false;
for (unsigned i = 0; i < Types.size(); ++i) {
assert(Types[i] != Type::VoidTy && "Void type for structure field!!");
new (&ContainedTys[i]) PATypeHandle(Types[i], this);
isAbstract |= Types[i]->isAbstract();
}
setAbstract(isAbstract);
}
ArrayType::ArrayType(const Type *ElType, uint64_t NumEl)
: SequentialType(ArrayTyID, ElType) {
NumElements = NumEl;
setAbstract(ElType->isAbstract());
}
VectorType::VectorType(const Type *ElType, unsigned NumEl)
: SequentialType(VectorTyID, ElType) {
NumElements = NumEl;
setAbstract(ElType->isAbstract());
assert(NumEl > 0 && "NumEl of a VectorType must be greater than 0");
assert((ElType->isInteger() || ElType->isFloatingPoint() ||
isa<OpaqueType>(ElType)) &&
"Elements of a VectorType must be a primitive type");
}
PointerType::PointerType(const Type *E, unsigned AddrSpace)
: SequentialType(PointerTyID, E) {
AddressSpace = AddrSpace;
setAbstract(E->isAbstract());
}
OpaqueType::OpaqueType() : DerivedType(OpaqueTyID) {
setAbstract(true);
#ifdef DEBUG_MERGE_TYPES
DOUT << "Derived new type: " << *this << "\n";
#endif
}
void PATypeHolder::destroy() {
Ty = 0;
}
void DerivedType::dropAllTypeUses() {
if (NumContainedTys != 0) {
static Type *AlwaysOpaqueTy = OpaqueType::get();
static PATypeHolder Holder(AlwaysOpaqueTy);
ContainedTys[0] = AlwaysOpaqueTy;
for (unsigned i = 1, e = NumContainedTys; i != e; ++i)
ContainedTys[i] = Type::Int32Ty;
}
}
namespace {
struct TypePromotionGraph {
Type *Ty;
TypePromotionGraph(Type *T) : Ty(T) {}
};
}
namespace llvm {
template <> struct GraphTraits<TypePromotionGraph> {
typedef Type NodeType;
typedef Type::subtype_iterator ChildIteratorType;
static inline NodeType *getEntryNode(TypePromotionGraph G) { return G.Ty; }
static inline ChildIteratorType child_begin(NodeType *N) {
if (N->isAbstract())
return N->subtype_begin();
else return N->subtype_end();
}
static inline ChildIteratorType child_end(NodeType *N) {
return N->subtype_end();
}
};
}
void Type::PromoteAbstractToConcrete() {
if (!isAbstract()) return;
scc_iterator<TypePromotionGraph> SI = scc_begin(TypePromotionGraph(this));
scc_iterator<TypePromotionGraph> SE = scc_end (TypePromotionGraph(this));
for (; SI != SE; ++SI) {
std::vector<Type*> &SCC = *SI;
if (SCC[0]->isAbstract()) {
if (isa<OpaqueType>(SCC[0]))
return;
for (unsigned i = 0, e = SCC.size(); i != e; ++i)
for (Type::subtype_iterator CI = SCC[i]->subtype_begin(),
E = SCC[i]->subtype_end(); CI != E; ++CI)
if ((*CI)->isAbstract())
if (std::find(SCC.begin(), SCC.end(), *CI) == SCC.end())
return;
for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
assert(SCC[i]->isAbstract() && "Why are we processing concrete types?");
SCC[i]->setAbstract(false);
}
for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
assert(!SCC[i]->isAbstract() && "Concrete type became abstract?");
cast<DerivedType>(SCC[i])->notifyUsesThatTypeBecameConcrete();
}
}
}
}
static bool TypesEqual(const Type *Ty, const Type *Ty2,
std::map<const Type *, const Type *> &EqTypes) {
if (Ty == Ty2) return true;
if (Ty->getTypeID() != Ty2->getTypeID()) return false;
if (isa<OpaqueType>(Ty))
return false;
std::map<const Type*, const Type*>::iterator It = EqTypes.find(Ty);
if (It != EqTypes.end())
return It->second == Ty2;
EqTypes.insert(It, std::make_pair(Ty, Ty2));
if (const IntegerType *ITy = dyn_cast<IntegerType>(Ty)) {
const IntegerType *ITy2 = cast<IntegerType>(Ty2);
return ITy->getBitWidth() == ITy2->getBitWidth();
} else if (const PointerType *PTy = dyn_cast<PointerType>(Ty)) {
const PointerType *PTy2 = cast<PointerType>(Ty2);
return PTy->getAddressSpace() == PTy2->getAddressSpace() &&
TypesEqual(PTy->getElementType(), PTy2->getElementType(), EqTypes);
} else if (const StructType *STy = dyn_cast<StructType>(Ty)) {
const StructType *STy2 = cast<StructType>(Ty2);
if (STy->getNumElements() != STy2->getNumElements()) return false;
if (STy->isPacked() != STy2->isPacked()) return false;
for (unsigned i = 0, e = STy2->getNumElements(); i != e; ++i)
if (!TypesEqual(STy->getElementType(i), STy2->getElementType(i), EqTypes))
return false;
return true;
} else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
const ArrayType *ATy2 = cast<ArrayType>(Ty2);
return ATy->getNumElements() == ATy2->getNumElements() &&
TypesEqual(ATy->getElementType(), ATy2->getElementType(), EqTypes);
} else if (const VectorType *PTy = dyn_cast<VectorType>(Ty)) {
const VectorType *PTy2 = cast<VectorType>(Ty2);
return PTy->getNumElements() == PTy2->getNumElements() &&
TypesEqual(PTy->getElementType(), PTy2->getElementType(), EqTypes);
} else if (const FunctionType *FTy = dyn_cast<FunctionType>(Ty)) {
const FunctionType *FTy2 = cast<FunctionType>(Ty2);
if (FTy->isVarArg() != FTy2->isVarArg() ||
FTy->getNumParams() != FTy2->getNumParams() ||
!TypesEqual(FTy->getReturnType(), FTy2->getReturnType(), EqTypes))
return false;
for (unsigned i = 0, e = FTy2->getNumParams(); i != e; ++i) {
if (!TypesEqual(FTy->getParamType(i), FTy2->getParamType(i), EqTypes))
return false;
}
return true;
} else {
assert(0 && "Unknown derived type!");
return false;
}
}
static bool TypesEqual(const Type *Ty, const Type *Ty2) {
std::map<const Type *, const Type *> EqTypes;
return TypesEqual(Ty, Ty2, EqTypes);
}
static bool AbstractTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy,
SmallPtrSet<const Type*, 128> &VisitedTypes) {
if (TargetTy == CurTy) return true;
if (!CurTy->isAbstract()) return false;
if (!VisitedTypes.insert(CurTy))
return false;
for (Type::subtype_iterator I = CurTy->subtype_begin(),
E = CurTy->subtype_end(); I != E; ++I)
if (AbstractTypeHasCycleThrough(TargetTy, *I, VisitedTypes))
return true;
return false;
}
static bool ConcreteTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy,
SmallPtrSet<const Type*, 128> &VisitedTypes) {
if (TargetTy == CurTy) return true;
if (!VisitedTypes.insert(CurTy))
return false;
for (Type::subtype_iterator I = CurTy->subtype_begin(),
E = CurTy->subtype_end(); I != E; ++I)
if (ConcreteTypeHasCycleThrough(TargetTy, *I, VisitedTypes))
return true;
return false;
}
static bool TypeHasCycleThroughItself(const Type *Ty) {
SmallPtrSet<const Type*, 128> VisitedTypes;
if (Ty->isAbstract()) { for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
I != E; ++I)
if (AbstractTypeHasCycleThrough(Ty, *I, VisitedTypes))
return true;
} else {
for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
I != E; ++I)
if (ConcreteTypeHasCycleThrough(Ty, *I, VisitedTypes))
return true;
}
return false;
}
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; }
namespace llvm {
class TypeMapBase {
protected:
std::multimap<unsigned, PATypeHolder> TypesByHash;
public:
~TypeMapBase() {
#if 0
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);
}
}
#endif
}
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();
}
};
}
namespace llvm {
template<class ValType, class TypeClass>
class TypeMap : public TypeMapBase {
std::map<ValType, PATypeHolder> Map;
public:
typedef typename std::map<ValType, PATypeHolder>::iterator iterator;
~TypeMap() { print("ON EXIT"); }
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
DOUT << "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->refineAbstractTypeTo(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->refineAbstractTypeTo(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
DOUT << "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)
DOUT << " " << (++i) << ". " << (void*)I->second.get() << " "
<< *I->second.get() << "\n";
#endif
}
void dump() const { print("dump output"); }
};
}
namespace llvm {
class IntegerValType {
uint32_t bits;
public:
IntegerValType(uint16_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;
}
};
}
static ManagedStatic<TypeMap<IntegerValType, IntegerType> > IntegerTypes;
const IntegerType *IntegerType::get(unsigned NumBits) {
assert(NumBits >= MIN_INT_BITS && "bitwidth too small");
assert(NumBits <= MAX_INT_BITS && "bitwidth too large");
switch (NumBits) {
case 1: return cast<IntegerType>(Type::Int1Ty);
case 8: return cast<IntegerType>(Type::Int8Ty);
case 16: return cast<IntegerType>(Type::Int16Ty);
case 32: return cast<IntegerType>(Type::Int32Ty);
case 64: return cast<IntegerType>(Type::Int64Ty);
default:
break;
}
IntegerValType IVT(NumBits);
IntegerType *ITy = IntegerTypes->get(IVT);
if (ITy) return ITy;
ITy = new IntegerType(NumBits);
IntegerTypes->add(IVT, ITy);
#ifdef DEBUG_MERGE_TYPES
DOUT << "Derived new type: " << *ITy << "\n";
#endif
return ITy;
}
bool IntegerType::isPowerOf2ByteWidth() const {
unsigned BitWidth = getBitWidth();
return (BitWidth > 7) && isPowerOf2_32(BitWidth);
}
APInt IntegerType::getMask() const {
return APInt::getAllOnesValue(getBitWidth());
}
namespace llvm {
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;
}
};
}
static ManagedStatic<TypeMap<FunctionValType, FunctionType> > FunctionTypes;
FunctionValType FunctionValType::get(const FunctionType *FT) {
std::vector<const Type *> ParamTypes;
ParamTypes.reserve(FT->getNumParams());
for (unsigned i = 0, e = FT->getNumParams(); i != e; ++i)
ParamTypes.push_back(FT->getParamType(i));
return FunctionValType(FT->getReturnType(), ParamTypes, FT->isVarArg());
}
FunctionType *FunctionType::get(const Type *ReturnType,
const std::vector<const Type*> &Params,
bool isVarArg) {
FunctionValType VT(ReturnType, Params, isVarArg);
FunctionType *FT = FunctionTypes->get(VT);
if (FT)
return FT;
FT = (FunctionType*) operator new(sizeof(FunctionType) +
sizeof(PATypeHandle)*(Params.size()+1));
new (FT) FunctionType(ReturnType, Params, isVarArg);
FunctionTypes->add(VT, FT);
#ifdef DEBUG_MERGE_TYPES
DOUT << "Derived new type: " << FT << "\n";
#endif
return FT;
}
namespace llvm {
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;
}
};
}
static ManagedStatic<TypeMap<ArrayValType, ArrayType> > ArrayTypes;
ArrayType *ArrayType::get(const Type *ElementType, uint64_t NumElements) {
assert(ElementType && "Can't get array of null types!");
ArrayValType AVT(ElementType, NumElements);
ArrayType *AT = ArrayTypes->get(AVT);
if (AT) return AT;
ArrayTypes->add(AVT, AT = new ArrayType(ElementType, NumElements));
#ifdef DEBUG_MERGE_TYPES
DOUT << "Derived new type: " << *AT << "\n";
#endif
return AT;
}
namespace llvm {
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;
}
};
}
static ManagedStatic<TypeMap<VectorValType, VectorType> > VectorTypes;
VectorType *VectorType::get(const Type *ElementType, unsigned NumElements) {
assert(ElementType && "Can't get vector of null types!");
VectorValType PVT(ElementType, NumElements);
VectorType *PT = VectorTypes->get(PVT);
if (PT) return PT;
VectorTypes->add(PVT, PT = new VectorType(ElementType, NumElements));
#ifdef DEBUG_MERGE_TYPES
DOUT << "Derived new type: " << *PT << "\n";
#endif
return PT;
}
namespace llvm {
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;
}
};
}
static ManagedStatic<TypeMap<StructValType, StructType> > StructTypes;
StructType *StructType::get(const std::vector<const Type*> &ETypes,
bool isPacked) {
StructValType STV(ETypes, isPacked);
StructType *ST = StructTypes->get(STV);
if (ST) return ST;
ST = (StructType*) operator new(sizeof(StructType) +
sizeof(PATypeHandle) * ETypes.size());
new (ST) StructType(ETypes, isPacked);
StructTypes->add(STV, ST);
#ifdef DEBUG_MERGE_TYPES
DOUT << "Derived new type: " << *ST << "\n";
#endif
return ST;
}
StructType *StructType::get(const Type *type, ...) {
va_list ap;
std::vector<const llvm::Type*> StructFields;
va_start(ap, type);
while (type) {
StructFields.push_back(type);
type = va_arg(ap, llvm::Type*);
}
return llvm::StructType::get(StructFields);
}
namespace llvm {
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;
}
};
}
static ManagedStatic<TypeMap<PointerValType, PointerType> > PointerTypes;
PointerType *PointerType::get(const Type *ValueType, unsigned AddressSpace) {
assert(ValueType && "Can't get a pointer to <null> type!");
assert(ValueType != Type::VoidTy &&
"Pointer to void is not valid, use sbyte* instead!");
assert(ValueType != Type::LabelTy && "Pointer to label is not valid!");
PointerValType PVT(ValueType, AddressSpace);
PointerType *PT = PointerTypes->get(PVT);
if (PT) return PT;
PointerTypes->add(PVT, PT = new PointerType(ValueType, AddressSpace));
#ifdef DEBUG_MERGE_TYPES
DOUT << "Derived new type: " << *PT << "\n";
#endif
return PT;
}
PointerType *Type::getPointerTo(unsigned addrs) const {
return PointerType::get(this, addrs);
}
void Type::removeAbstractTypeUser(AbstractTypeUser *U) const {
unsigned i;
for (i = AbstractTypeUsers.size(); AbstractTypeUsers[i-1] != U; --i)
assert(i != 0 && "AbstractTypeUser not in user list!");
--i; assert(i < AbstractTypeUsers.size() && "Index out of range!");
AbstractTypeUsers.erase(AbstractTypeUsers.begin()+i);
#ifdef DEBUG_MERGE_TYPES
DOUT << " remAbstractTypeUser[" << (void*)this << ", "
<< *this << "][" << i << "] User = " << U << "\n";
#endif
if (AbstractTypeUsers.empty() && getRefCount() == 0 && isAbstract()) {
#ifdef DEBUG_MERGE_TYPES
DOUT << "DELETEing unused abstract type: <" << *this
<< ">[" << (void*)this << "]" << "\n";
#endif
this->destroy();
}
}
void DerivedType::refineAbstractTypeTo(const Type *NewType) {
assert(isAbstract() && "refineAbstractTypeTo: Current type is not abstract!");
assert(this != NewType && "Can't refine to myself!");
assert(ForwardType == 0 && "This type has already been refined!");
if (AbstractTypeDescriptions.isConstructed())
AbstractTypeDescriptions->clear();
#ifdef DEBUG_MERGE_TYPES
DOUT << "REFINING abstract type [" << (void*)this << " "
<< *this << "] to [" << (void*)NewType << " "
<< *NewType << "]!\n";
#endif
PATypeHolder NewTy(NewType);
ForwardType = NewType;
if (NewType->isAbstract())
cast<DerivedType>(NewType)->addRef();
PATypeHolder CurrentTy(this);
dropAllTypeUses();
while (!AbstractTypeUsers.empty() && NewTy != this) {
AbstractTypeUser *User = AbstractTypeUsers.back();
unsigned OldSize = AbstractTypeUsers.size(); OldSize=OldSize;
#ifdef DEBUG_MERGE_TYPES
DOUT << " REFINING user " << OldSize-1 << "[" << (void*)User
<< "] of abstract type [" << (void*)this << " "
<< *this << "] to [" << (void*)NewTy.get() << " "
<< *NewTy << "]!\n";
#endif
User->refineAbstractType(this, NewTy);
assert(AbstractTypeUsers.size() != OldSize &&
"AbsTyUser did not remove self from user list!");
}
}
void DerivedType::notifyUsesThatTypeBecameConcrete() {
#ifdef DEBUG_MERGE_TYPES
DOUT << "typeIsREFINED type: " << (void*)this << " " << *this << "\n";
#endif
unsigned OldSize = AbstractTypeUsers.size(); OldSize=OldSize;
while (!AbstractTypeUsers.empty()) {
AbstractTypeUser *ATU = AbstractTypeUsers.back();
ATU->typeBecameConcrete(this);
assert(AbstractTypeUsers.size() < OldSize-- &&
"AbstractTypeUser did not remove itself from the use list!");
}
}
void FunctionType::refineAbstractType(const DerivedType *OldType,
const Type *NewType) {
FunctionTypes->RefineAbstractType(this, OldType, NewType);
}
void FunctionType::typeBecameConcrete(const DerivedType *AbsTy) {
FunctionTypes->TypeBecameConcrete(this, AbsTy);
}
void ArrayType::refineAbstractType(const DerivedType *OldType,
const Type *NewType) {
ArrayTypes->RefineAbstractType(this, OldType, NewType);
}
void ArrayType::typeBecameConcrete(const DerivedType *AbsTy) {
ArrayTypes->TypeBecameConcrete(this, AbsTy);
}
void VectorType::refineAbstractType(const DerivedType *OldType,
const Type *NewType) {
VectorTypes->RefineAbstractType(this, OldType, NewType);
}
void VectorType::typeBecameConcrete(const DerivedType *AbsTy) {
VectorTypes->TypeBecameConcrete(this, AbsTy);
}
void StructType::refineAbstractType(const DerivedType *OldType,
const Type *NewType) {
StructTypes->RefineAbstractType(this, OldType, NewType);
}
void StructType::typeBecameConcrete(const DerivedType *AbsTy) {
StructTypes->TypeBecameConcrete(this, AbsTy);
}
void PointerType::refineAbstractType(const DerivedType *OldType,
const Type *NewType) {
PointerTypes->RefineAbstractType(this, OldType, NewType);
}
void PointerType::typeBecameConcrete(const DerivedType *AbsTy) {
PointerTypes->TypeBecameConcrete(this, AbsTy);
}
bool SequentialType::indexValid(const Value *V) const {
if (const IntegerType *IT = dyn_cast<IntegerType>(V->getType()))
return IT->getBitWidth() == 16 || IT->getBitWidth() == 32 ||
IT->getBitWidth() == 64;
return false;
}
namespace llvm {
std::ostream &operator<<(std::ostream &OS, const Type *T) {
if (T == 0)
OS << "<null> value!\n";
else
T->print(OS);
return OS;
}
std::ostream &operator<<(std::ostream &OS, const Type &T) {
T.print(OS);
return OS;
}
raw_ostream &operator<<(raw_ostream &OS, const Type &T) {
T.print(OS);
return OS;
}
}