X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FType.cpp;h=445e15d38816731c98472725f4936eb7f4685d8a;hb=7adfe3fd60f2480969f307b5dd377864f7c3eacd;hp=696ac96ae6a72d1ea084c579e8a0bc246cda49ee;hpb=63a03cf58505aa839f721f212cd1518ebf133979;p=oota-llvm.git diff --git a/lib/VMCore/Type.cpp b/lib/VMCore/Type.cpp index 696ac96ae6a..445e15d3881 100644 --- a/lib/VMCore/Type.cpp +++ b/lib/VMCore/Type.cpp @@ -12,85 +12,20 @@ //===----------------------------------------------------------------------===// #include "LLVMContextImpl.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Constants.h" -#include "llvm/Assembly/Writer.h" -#include "llvm/LLVMContext.h" -#include "llvm/Metadata.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/ErrorHandling.h" -#include "llvm/Support/ManagedStatic.h" -#include "llvm/Support/MathExtras.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/System/Mutex.h" -#include "llvm/System/RWMutex.h" -#include "llvm/System/Threading.h" +#include "llvm/Module.h" #include #include +#include "llvm/ADT/SmallString.h" using namespace llvm; -// DEBUG_MERGE_TYPES - Enable this #define to see how and when derived types are -// created and later destroyed, all in an effort to make sure that there is only -// a single canonical version of a type. -// -// #define DEBUG_MERGE_TYPES 1 - -AbstractTypeUser::~AbstractTypeUser() {} - - //===----------------------------------------------------------------------===// // Type Class Implementation //===----------------------------------------------------------------------===// -/// Because of the way Type subclasses are allocated, this function is necessary -/// to use the correct kind of "delete" operator to deallocate the Type object. -/// Some type objects (FunctionTy, StructTy) allocate additional space after -/// the space for their derived type to hold the contained types array of -/// PATypeHandles. Using this allocation scheme means all the PATypeHandles are -/// allocated with the type object, decreasing allocations and eliminating the -/// need for a std::vector to be used in the Type class itself. -/// @brief Type destruction function -void Type::destroy() const { - - // Structures and Functions allocate their contained types past the end of - // the type object itself. These need to be destroyed differently than the - // other types. - if (isa(this) || isa(this)) { - // First, make sure we destruct any PATypeHandles allocated by these - // subclasses. They must be manually destructed. - for (unsigned i = 0; i < NumContainedTys; ++i) - ContainedTys[i].PATypeHandle::~PATypeHandle(); - - // Now call the destructor for the subclass directly because we're going - // to delete this as an array of char. - if (isa(this)) - static_cast(this)->FunctionType::~FunctionType(); - else - static_cast(this)->StructType::~StructType(); - - // Finally, remove the memory as an array deallocation of the chars it was - // constructed from. - operator delete(const_cast(this)); - - return; - } - - // For all the other type subclasses, there is either no contained types or - // just one (all Sequentials). For Sequentials, the PATypeHandle is not - // allocated past the type object, its included directly in the SequentialType - // class. This means we can safely just do "normal" delete of this object and - // all the destructors that need to run will be run. - delete this; -} - -const Type *Type::getPrimitiveType(LLVMContext &C, TypeID IDNumber) { +Type *Type::getPrimitiveType(LLVMContext &C, TypeID IDNumber) { switch (IDNumber) { case VoidTyID : return getVoidTy(C); + case HalfTyID : return getHalfTy(C); case FloatTyID : return getFloatTy(C); case DoubleTyID : return getDoubleTy(C); case X86_FP80TyID : return getX86_FP80Ty(C); @@ -98,55 +33,35 @@ const Type *Type::getPrimitiveType(LLVMContext &C, TypeID IDNumber) { case PPC_FP128TyID : return getPPC_FP128Ty(C); case LabelTyID : return getLabelTy(C); case MetadataTyID : return getMetadataTy(C); + case X86_MMXTyID : return getX86_MMXTy(C); default: return 0; } } -const Type *Type::getVAArgsPromotedType(LLVMContext &C) const { - if (ID == IntegerTyID && getSubclassData() < 32) - return Type::getInt32Ty(C); - else if (ID == FloatTyID) - return Type::getDoubleTy(C); - else - return this; -} - /// getScalarType - If this is a vector type, return the element type, /// otherwise return this. -const Type *Type::getScalarType() const { - if (const VectorType *VTy = dyn_cast(this)) +Type *Type::getScalarType() { + if (VectorType *VTy = dyn_cast(this)) return VTy->getElementType(); return this; } -/// isIntOrIntVector - Return true if this is an integer type or a vector of -/// integer types. -/// -bool Type::isIntOrIntVector() const { - if (isInteger()) - return true; - if (ID != Type::VectorTyID) return false; - - return cast(this)->getElementType()->isInteger(); +const Type *Type::getScalarType() const { + if (const VectorType *VTy = dyn_cast(this)) + return VTy->getElementType(); + return this; } -/// isFPOrFPVector - Return true if this is a FP type or a vector of FP types. -/// -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(this)->getElementType()->isFloatingPoint(); +/// isIntegerTy - Return true if this is an IntegerType of the specified width. +bool Type::isIntegerTy(unsigned Bitwidth) const { + return isIntegerTy() && cast(this)->getBitWidth() == Bitwidth; } // canLosslesslyBitCastTo - Return true if this type can be converted to // 'Ty' without any reinterpretation of bits. For example, i8* to i32*. // -bool Type::canLosslesslyBitCastTo(const Type *Ty) const { +bool Type::canLosslesslyBitCastTo(Type *Ty) const { // Identity cast means no change so return true if (this == Ty) return true; @@ -156,26 +71,57 @@ bool Type::canLosslesslyBitCastTo(const Type *Ty) const { return false; // Vector -> Vector conversions are always lossless if the two vector types - // have the same size, otherwise not. - if (const VectorType *thisPTy = dyn_cast(this)) + // have the same size, otherwise not. Also, 64-bit vector types can be + // converted to x86mmx. + if (const VectorType *thisPTy = dyn_cast(this)) { if (const VectorType *thatPTy = dyn_cast(Ty)) return thisPTy->getBitWidth() == thatPTy->getBitWidth(); + if (Ty->getTypeID() == Type::X86_MMXTyID && + thisPTy->getBitWidth() == 64) + return true; + } + + if (this->getTypeID() == Type::X86_MMXTyID) + if (const VectorType *thatPTy = dyn_cast(Ty)) + if (thatPTy->getBitWidth() == 64) + return true; // At this point we have only various mismatches of the first class types // remaining and ptr->ptr. Just select the lossless conversions. Everything // else is not lossless. - if (isa(this)) - return isa(Ty); + if (this->isPointerTy()) + return Ty->isPointerTy(); return false; // Other types have no identity values } +bool Type::isEmptyTy() const { + const ArrayType *ATy = dyn_cast(this); + if (ATy) { + unsigned NumElements = ATy->getNumElements(); + return NumElements == 0 || ATy->getElementType()->isEmptyTy(); + } + + const StructType *STy = dyn_cast(this); + if (STy) { + unsigned NumElements = STy->getNumElements(); + for (unsigned i = 0; i < NumElements; ++i) + if (!STy->getElementType(i)->isEmptyTy()) + return false; + return true; + } + + return false; +} + unsigned Type::getPrimitiveSizeInBits() const { switch (getTypeID()) { + case Type::HalfTyID: return 16; 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::X86_MMXTyID: return 64; case Type::IntegerTyID: return cast(this)->getBitWidth(); case Type::VectorTyID: return cast(this)->getBitWidth(); default: return 0; @@ -185,7 +131,7 @@ unsigned Type::getPrimitiveSizeInBits() const { /// getScalarSizeInBits - If this is a vector type, return the /// getPrimitiveSizeInBits value for the element type. Otherwise return the /// getPrimitiveSizeInBits value for this type. -unsigned Type::getScalarSizeInBits() const { +unsigned Type::getScalarSizeInBits() { return getScalarType()->getPrimitiveSizeInBits(); } @@ -195,12 +141,13 @@ unsigned Type::getScalarSizeInBits() const { int Type::getFPMantissaWidth() const { if (const VectorType *VTy = dyn_cast(this)) return VTy->getElementType()->getFPMantissaWidth(); - assert(isFloatingPoint() && "Not a floating point type!"); - if (ID == FloatTyID) return 24; - if (ID == DoubleTyID) return 53; - if (ID == X86_FP80TyID) return 64; - if (ID == FP128TyID) return 113; - assert(ID == PPC_FP128TyID && "unknown fp type"); + assert(isFloatingPointTy() && "Not a floating point type!"); + if (getTypeID() == HalfTyID) return 11; + if (getTypeID() == FloatTyID) return 24; + if (getTypeID() == DoubleTyID) return 53; + if (getTypeID() == X86_FP80TyID) return 64; + if (getTypeID() == FP128TyID) return 113; + assert(getTypeID() == PPC_FP128TyID && "unknown fp type"); return -1; } @@ -208,1008 +155,613 @@ int Type::getFPMantissaWidth() const { /// iff all of the members of the type are sized as well. Since asking for /// their size is relatively uncommon, move this operation out of line. bool Type::isSizedDerivedType() const { - if (isa(this)) + if (this->isIntegerTy()) return true; if (const ArrayType *ATy = dyn_cast(this)) return ATy->getElementType()->isSized(); - if (const VectorType *PTy = dyn_cast(this)) - return PTy->getElementType()->isSized(); + if (const VectorType *VTy = dyn_cast(this)) + return VTy->getElementType()->isSized(); - if (!isa(this)) + if (!this->isStructTy()) return false; - // Okay, our struct is sized if all of the elements are... - for (subtype_iterator I = subtype_begin(), E = subtype_end(); I != E; ++I) - if (!(*I)->isSized()) - return false; - - return true; + return cast(this)->isSized(); } -/// getForwardedTypeInternal - This method is used to implement the union-find -/// algorithm for when a type is being forwarded to another type. -const Type *Type::getForwardedTypeInternal() const { - assert(ForwardType && "This type is not being forwarded to another type!"); - - // Check to see if the forwarded type has been forwarded on. If so, collapse - // the forwarding links. - const Type *RealForwardedType = ForwardType->getForwardedType(); - if (!RealForwardedType) - return ForwardType; // No it's not forwarded again - - // Yes, it is forwarded again. First thing, add the reference to the new - // forward type. - if (RealForwardedType->isAbstract()) - cast(RealForwardedType)->addRef(); +//===----------------------------------------------------------------------===// +// Subclass Helper Methods +//===----------------------------------------------------------------------===// - // Now drop the old reference. This could cause ForwardType to get deleted. - cast(ForwardType)->dropRef(); +unsigned Type::getIntegerBitWidth() const { + return cast(this)->getBitWidth(); +} - // Return the updated type. - ForwardType = RealForwardedType; - return ForwardType; +bool Type::isFunctionVarArg() const { + return cast(this)->isVarArg(); } -void Type::refineAbstractType(const DerivedType *OldTy, const Type *NewTy) { - llvm_unreachable("Attempting to refine a derived type!"); +Type *Type::getFunctionParamType(unsigned i) const { + return cast(this)->getParamType(i); } -void Type::typeBecameConcrete(const DerivedType *AbsTy) { - llvm_unreachable("DerivedType is already a concrete type!"); + +unsigned Type::getFunctionNumParams() const { + return cast(this)->getNumParams(); } +StringRef Type::getStructName() const { + return cast(this)->getName(); +} -std::string Type::getDescription() const { - LLVMContextImpl *pImpl = getContext().pImpl; - TypePrinting &Map = - isAbstract() ? - pImpl->AbstractTypeDescriptions : - pImpl->ConcreteTypeDescriptions; - - std::string DescStr; - raw_string_ostream DescOS(DescStr); - Map.print(this, DescOS); - return DescOS.str(); +unsigned Type::getStructNumElements() const { + return cast(this)->getNumElements(); } +Type *Type::getStructElementType(unsigned N) const { + return cast(this)->getElementType(N); +} -bool StructType::indexValid(const Value *V) const { - // Structure indexes require 32-bit integer constants. - if (V->getType() == Type::getInt32Ty(V->getContext())) - if (const ConstantInt *CU = dyn_cast(V)) - return indexValid(CU->getZExtValue()); - return false; +Type *Type::getSequentialElementType() const { + return cast(this)->getElementType(); } -bool StructType::indexValid(unsigned V) const { - return V < NumContainedTys; +uint64_t Type::getArrayNumElements() const { + return cast(this)->getNumElements(); } -// getTypeAtIndex - Given an index value into the type, return the type of the -// element. For a structure type, this must be a constant value... -// -const Type *StructType::getTypeAtIndex(const Value *V) const { - unsigned Idx = (unsigned)cast(V)->getZExtValue(); - return getTypeAtIndex(Idx); +unsigned Type::getVectorNumElements() const { + return cast(this)->getNumElements(); } -const Type *StructType::getTypeAtIndex(unsigned Idx) const { - assert(indexValid(Idx) && "Invalid structure index!"); - return ContainedTys[Idx]; +unsigned Type::getPointerAddressSpace() const { + if (isPointerTy()) + return cast(this)->getAddressSpace(); + if (isVectorTy()) + return getSequentialElementType()->getPointerAddressSpace(); + llvm_unreachable("Should never reach here!"); + return 0; } + //===----------------------------------------------------------------------===// // Primitive 'Type' data //===----------------------------------------------------------------------===// -const Type *Type::getVoidTy(LLVMContext &C) { - return &C.pImpl->VoidTy; +Type *Type::getVoidTy(LLVMContext &C) { return &C.pImpl->VoidTy; } +Type *Type::getLabelTy(LLVMContext &C) { return &C.pImpl->LabelTy; } +Type *Type::getHalfTy(LLVMContext &C) { return &C.pImpl->HalfTy; } +Type *Type::getFloatTy(LLVMContext &C) { return &C.pImpl->FloatTy; } +Type *Type::getDoubleTy(LLVMContext &C) { return &C.pImpl->DoubleTy; } +Type *Type::getMetadataTy(LLVMContext &C) { return &C.pImpl->MetadataTy; } +Type *Type::getX86_FP80Ty(LLVMContext &C) { return &C.pImpl->X86_FP80Ty; } +Type *Type::getFP128Ty(LLVMContext &C) { return &C.pImpl->FP128Ty; } +Type *Type::getPPC_FP128Ty(LLVMContext &C) { return &C.pImpl->PPC_FP128Ty; } +Type *Type::getX86_MMXTy(LLVMContext &C) { return &C.pImpl->X86_MMXTy; } + +IntegerType *Type::getInt1Ty(LLVMContext &C) { return &C.pImpl->Int1Ty; } +IntegerType *Type::getInt8Ty(LLVMContext &C) { return &C.pImpl->Int8Ty; } +IntegerType *Type::getInt16Ty(LLVMContext &C) { return &C.pImpl->Int16Ty; } +IntegerType *Type::getInt32Ty(LLVMContext &C) { return &C.pImpl->Int32Ty; } +IntegerType *Type::getInt64Ty(LLVMContext &C) { return &C.pImpl->Int64Ty; } + +IntegerType *Type::getIntNTy(LLVMContext &C, unsigned N) { + return IntegerType::get(C, N); +} + +PointerType *Type::getHalfPtrTy(LLVMContext &C, unsigned AS) { + return getHalfTy(C)->getPointerTo(AS); } -const Type *Type::getLabelTy(LLVMContext &C) { - return &C.pImpl->LabelTy; +PointerType *Type::getFloatPtrTy(LLVMContext &C, unsigned AS) { + return getFloatTy(C)->getPointerTo(AS); } -const Type *Type::getFloatTy(LLVMContext &C) { - return &C.pImpl->FloatTy; +PointerType *Type::getDoublePtrTy(LLVMContext &C, unsigned AS) { + return getDoubleTy(C)->getPointerTo(AS); } -const Type *Type::getDoubleTy(LLVMContext &C) { - return &C.pImpl->DoubleTy; +PointerType *Type::getX86_FP80PtrTy(LLVMContext &C, unsigned AS) { + return getX86_FP80Ty(C)->getPointerTo(AS); } -const Type *Type::getMetadataTy(LLVMContext &C) { - return &C.pImpl->MetadataTy; +PointerType *Type::getFP128PtrTy(LLVMContext &C, unsigned AS) { + return getFP128Ty(C)->getPointerTo(AS); } -const Type *Type::getX86_FP80Ty(LLVMContext &C) { - return &C.pImpl->X86_FP80Ty; +PointerType *Type::getPPC_FP128PtrTy(LLVMContext &C, unsigned AS) { + return getPPC_FP128Ty(C)->getPointerTo(AS); } -const Type *Type::getFP128Ty(LLVMContext &C) { - return &C.pImpl->FP128Ty; +PointerType *Type::getX86_MMXPtrTy(LLVMContext &C, unsigned AS) { + return getX86_MMXTy(C)->getPointerTo(AS); } -const Type *Type::getPPC_FP128Ty(LLVMContext &C) { - return &C.pImpl->PPC_FP128Ty; +PointerType *Type::getIntNPtrTy(LLVMContext &C, unsigned N, unsigned AS) { + return getIntNTy(C, N)->getPointerTo(AS); } -const IntegerType *Type::getInt1Ty(LLVMContext &C) { - return &C.pImpl->Int1Ty; +PointerType *Type::getInt1PtrTy(LLVMContext &C, unsigned AS) { + return getInt1Ty(C)->getPointerTo(AS); } -const IntegerType *Type::getInt8Ty(LLVMContext &C) { - return &C.pImpl->Int8Ty; +PointerType *Type::getInt8PtrTy(LLVMContext &C, unsigned AS) { + return getInt8Ty(C)->getPointerTo(AS); } -const IntegerType *Type::getInt16Ty(LLVMContext &C) { - return &C.pImpl->Int16Ty; +PointerType *Type::getInt16PtrTy(LLVMContext &C, unsigned AS) { + return getInt16Ty(C)->getPointerTo(AS); } -const IntegerType *Type::getInt32Ty(LLVMContext &C) { - return &C.pImpl->Int32Ty; +PointerType *Type::getInt32PtrTy(LLVMContext &C, unsigned AS) { + return getInt32Ty(C)->getPointerTo(AS); } -const IntegerType *Type::getInt64Ty(LLVMContext &C) { - return &C.pImpl->Int64Ty; +PointerType *Type::getInt64PtrTy(LLVMContext &C, unsigned AS) { + return getInt64Ty(C)->getPointerTo(AS); } + //===----------------------------------------------------------------------===// -// Derived Type Constructors +// IntegerType Implementation //===----------------------------------------------------------------------===// -/// isValidReturnType - Return true if the specified type is valid as a return -/// type. -bool FunctionType::isValidReturnType(const Type *RetTy) { - if (RetTy->isFirstClassType()) { - if (const PointerType *PTy = dyn_cast(RetTy)) - return PTy->getElementType() != Type::getMetadataTy(RetTy->getContext()); - return true; +IntegerType *IntegerType::get(LLVMContext &C, unsigned NumBits) { + assert(NumBits >= MIN_INT_BITS && "bitwidth too small"); + assert(NumBits <= MAX_INT_BITS && "bitwidth too large"); + + // Check for the built-in integer types + switch (NumBits) { + case 1: return cast(Type::getInt1Ty(C)); + case 8: return cast(Type::getInt8Ty(C)); + case 16: return cast(Type::getInt16Ty(C)); + case 32: return cast(Type::getInt32Ty(C)); + case 64: return cast(Type::getInt64Ty(C)); + default: + break; } - if (RetTy == Type::getVoidTy(RetTy->getContext()) || - RetTy == Type::getMetadataTy(RetTy->getContext()) || - isa(RetTy)) - return true; - // If this is a multiple return case, verify that each return is a first class - // value and that there is at least one value. - const StructType *SRetTy = dyn_cast(RetTy); - if (SRetTy == 0 || SRetTy->getNumElements() == 0) - return false; + IntegerType *&Entry = C.pImpl->IntegerTypes[NumBits]; - for (unsigned i = 0, e = SRetTy->getNumElements(); i != e; ++i) - if (!SRetTy->getElementType(i)->isFirstClassType()) - return false; - return true; + if (Entry == 0) + Entry = new (C.pImpl->TypeAllocator) IntegerType(C, NumBits); + + return Entry; } -/// isValidArgumentType - Return true if the specified type is valid as an -/// argument type. -bool FunctionType::isValidArgumentType(const Type *ArgTy) { - if ((!ArgTy->isFirstClassType() && !isa(ArgTy)) || - (isa(ArgTy) && - cast(ArgTy)->getElementType() == - Type::getMetadataTy(ArgTy->getContext()))) - return false; +bool IntegerType::isPowerOf2ByteWidth() const { + unsigned BitWidth = getBitWidth(); + return (BitWidth > 7) && isPowerOf2_32(BitWidth); +} - return true; +APInt IntegerType::getMask() const { + return APInt::getAllOnesValue(getBitWidth()); } -FunctionType::FunctionType(const Type *Result, - const std::vector &Params, +//===----------------------------------------------------------------------===// +// FunctionType Implementation +//===----------------------------------------------------------------------===// + +FunctionType::FunctionType(Type *Result, ArrayRef Params, bool IsVarArgs) - : DerivedType(Result->getContext(), FunctionTyID), isVarArgs(IsVarArgs) { - ContainedTys = reinterpret_cast(this+1); - NumContainedTys = Params.size() + 1; // + 1 for result type + : Type(Result->getContext(), FunctionTyID) { + Type **SubTys = reinterpret_cast(this+1); assert(isValidReturnType(Result) && "invalid return type for function"); + setSubclassData(IsVarArgs); + SubTys[0] = const_cast(Result); - bool isAbstract = Result->isAbstract(); - new (&ContainedTys[0]) PATypeHandle(Result, this); - - for (unsigned i = 0; i != Params.size(); ++i) { + for (unsigned i = 0, e = Params.size(); i != e; ++i) { assert(isValidArgumentType(Params[i]) && "Not a valid type for function argument!"); - new (&ContainedTys[i+1]) PATypeHandle(Params[i], this); - isAbstract |= Params[i]->isAbstract(); - } - - // Calculate whether or not this type is abstract - setAbstract(isAbstract); -} - -StructType::StructType(LLVMContext &C, - const std::vector &Types, bool isPacked) - : CompositeType(C, StructTyID) { - ContainedTys = reinterpret_cast(this + 1); - NumContainedTys = Types.size(); - setSubclassData(isPacked); - bool isAbstract = false; - for (unsigned i = 0; i < Types.size(); ++i) { - assert(Types[i] && " type for structure field!"); - assert(isValidElementType(Types[i]) && - "Invalid type for structure element!"); - new (&ContainedTys[i]) PATypeHandle(Types[i], this); - isAbstract |= Types[i]->isAbstract(); + SubTys[i+1] = Params[i]; } - // Calculate whether or not this type is abstract - setAbstract(isAbstract); -} - -ArrayType::ArrayType(const Type *ElType, uint64_t NumEl) - : SequentialType(ArrayTyID, ElType) { - NumElements = NumEl; - - // Calculate whether or not this type is abstract - 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(isValidElementType(ElType) && - "Elements of a VectorType must be a primitive type"); - -} - - -PointerType::PointerType(const Type *E, unsigned AddrSpace) - : SequentialType(PointerTyID, E) { - AddressSpace = AddrSpace; - // Calculate whether or not this type is abstract - setAbstract(E->isAbstract()); -} - -OpaqueType::OpaqueType(LLVMContext &C) : DerivedType(C, OpaqueTyID) { - setAbstract(true); -#ifdef DEBUG_MERGE_TYPES - DEBUG(errs() << "Derived new type: " << *this << "\n"); -#endif + ContainedTys = SubTys; + NumContainedTys = Params.size() + 1; // + 1 for result type } -void PATypeHolder::destroy() { - Ty = 0; -} - -// dropAllTypeUses - When this (abstract) type is resolved to be equal to -// another (more concrete) type, we must eliminate all references to other -// types, to avoid some circular reference problems. -void DerivedType::dropAllTypeUses() { - if (NumContainedTys != 0) { - // The type must stay abstract. To do this, we insert a pointer to a type - // that will never get resolved, thus will always be abstract. - static Type *AlwaysOpaqueTy = 0; - static PATypeHolder* Holder = 0; - Type *tmp = AlwaysOpaqueTy; - if (llvm_is_multithreaded()) { - sys::MemoryFence(); - if (!tmp) { - llvm_acquire_global_lock(); - tmp = AlwaysOpaqueTy; - if (!tmp) { - tmp = OpaqueType::get(getContext()); - PATypeHolder* tmp2 = new PATypeHolder(AlwaysOpaqueTy); - sys::MemoryFence(); - AlwaysOpaqueTy = tmp; - Holder = tmp2; - } - - llvm_release_global_lock(); - } - } else { - AlwaysOpaqueTy = OpaqueType::get(getContext()); - Holder = new PATypeHolder(AlwaysOpaqueTy); - } - - ContainedTys[0] = AlwaysOpaqueTy; - - // Change the rest of the types to be Int32Ty's. It doesn't matter what we - // pick so long as it doesn't point back to this type. We choose something - // concrete to avoid overhead for adding to AbstracTypeUser lists and stuff. - for (unsigned i = 1, e = NumContainedTys; i != e; ++i) - ContainedTys[i] = Type::getInt32Ty(getContext()); +// FunctionType::get - The factory function for the FunctionType class. +FunctionType *FunctionType::get(Type *ReturnType, + ArrayRef Params, bool isVarArg) { + LLVMContextImpl *pImpl = ReturnType->getContext().pImpl; + FunctionTypeKeyInfo::KeyTy Key(ReturnType, Params, isVarArg); + LLVMContextImpl::FunctionTypeMap::iterator I = + pImpl->FunctionTypes.find_as(Key); + FunctionType *FT; + + if (I == pImpl->FunctionTypes.end()) { + FT = (FunctionType*) pImpl->TypeAllocator. + Allocate(sizeof(FunctionType) + sizeof(Type*) * (Params.size() + 1), + AlignOf::Alignment); + new (FT) FunctionType(ReturnType, Params, isVarArg); + pImpl->FunctionTypes[FT] = true; + } else { + FT = I->first; } -} - - -namespace { - -/// TypePromotionGraph and graph traits - this is designed to allow us to do -/// efficient SCC processing of type graphs. This is the exact same as -/// GraphTraits, except that we pretend that concrete types have no -/// children to avoid processing them. -struct TypePromotionGraph { - Type *Ty; - TypePromotionGraph(Type *T) : Ty(T) {} -}; + return FT; } -namespace llvm { - template <> struct GraphTraits { - 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 // No need to process children of concrete types. - return N->subtype_end(); - } - static inline ChildIteratorType child_end(NodeType *N) { - return N->subtype_end(); - } - }; +FunctionType *FunctionType::get(Type *Result, bool isVarArg) { + return get(Result, ArrayRef(), isVarArg); } - -// PromoteAbstractToConcrete - This is a recursive function that walks a type -// graph calculating whether or not a type is abstract. -// -void Type::PromoteAbstractToConcrete() { - if (!isAbstract()) return; - - scc_iterator SI = scc_begin(TypePromotionGraph(this)); - scc_iterator SE = scc_end (TypePromotionGraph(this)); - - for (; SI != SE; ++SI) { - std::vector &SCC = *SI; - - // Concrete types are leaves in the tree. Since an SCC will either be all - // abstract or all concrete, we only need to check one type. - if (SCC[0]->isAbstract()) { - if (isa(SCC[0])) - return; // Not going to be concrete, sorry. - - // If all of the children of all of the types in this SCC are concrete, - // then this SCC is now concrete as well. If not, neither this SCC, nor - // any parent SCCs will be concrete, so we might as well just exit. - 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 the child type is in our SCC, it doesn't make the entire SCC - // abstract unless there is a non-SCC abstract type. - if (std::find(SCC.begin(), SCC.end(), *CI) == SCC.end()) - return; // Not going to be concrete, sorry. - - // Okay, we just discovered this whole SCC is now concrete, mark it as - // such! - 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?"); - // The type just became concrete, notify all users! - cast(SCC[i])->notifyUsesThatTypeBecameConcrete(); - } - } - } +/// isValidReturnType - Return true if the specified type is valid as a return +/// type. +bool FunctionType::isValidReturnType(Type *RetTy) { + return !RetTy->isFunctionTy() && !RetTy->isLabelTy() && + !RetTy->isMetadataTy(); } +/// isValidArgumentType - Return true if the specified type is valid as an +/// argument type. +bool FunctionType::isValidArgumentType(Type *ArgTy) { + return ArgTy->isFirstClassType(); +} //===----------------------------------------------------------------------===// -// Type Structural Equality Testing +// StructType Implementation //===----------------------------------------------------------------------===// -// TypesEqual - Two types are considered structurally equal if they have the -// same "shape": Every level and element of the types have identical primitive -// ID's, and the graphs have the same edges/nodes in them. Nodes do not have to -// be pointer equals to be equivalent though. This uses an optimistic algorithm -// that assumes that two graphs are the same until proven otherwise. -// -static bool TypesEqual(const Type *Ty, const Type *Ty2, - std::map &EqTypes) { - if (Ty == Ty2) return true; - if (Ty->getTypeID() != Ty2->getTypeID()) return false; - if (isa(Ty)) - return false; // Two unequal opaque types are never equal - - std::map::iterator It = EqTypes.find(Ty); - if (It != EqTypes.end()) - return It->second == Ty2; // Looping back on a type, check for equality - - // Otherwise, add the mapping to the table to make sure we don't get - // recursion on the types... - EqTypes.insert(It, std::make_pair(Ty, Ty2)); - - // Two really annoying special cases that breaks an otherwise nice simple - // algorithm is the fact that arraytypes have sizes that differentiates types, - // and that function types can be varargs or not. Consider this now. - // - if (const IntegerType *ITy = dyn_cast(Ty)) { - const IntegerType *ITy2 = cast(Ty2); - return ITy->getBitWidth() == ITy2->getBitWidth(); - } else if (const PointerType *PTy = dyn_cast(Ty)) { - const PointerType *PTy2 = cast(Ty2); - return PTy->getAddressSpace() == PTy2->getAddressSpace() && - TypesEqual(PTy->getElementType(), PTy2->getElementType(), EqTypes); - } else if (const StructType *STy = dyn_cast(Ty)) { - const StructType *STy2 = cast(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(Ty)) { - const ArrayType *ATy2 = cast(Ty2); - return ATy->getNumElements() == ATy2->getNumElements() && - TypesEqual(ATy->getElementType(), ATy2->getElementType(), EqTypes); - } else if (const VectorType *PTy = dyn_cast(Ty)) { - const VectorType *PTy2 = cast(Ty2); - return PTy->getNumElements() == PTy2->getNumElements() && - TypesEqual(PTy->getElementType(), PTy2->getElementType(), EqTypes); - } else if (const FunctionType *FTy = dyn_cast(Ty)) { - const FunctionType *FTy2 = cast(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; +// Primitive Constructors. + +StructType *StructType::get(LLVMContext &Context, ArrayRef ETypes, + bool isPacked) { + LLVMContextImpl *pImpl = Context.pImpl; + AnonStructTypeKeyInfo::KeyTy Key(ETypes, isPacked); + LLVMContextImpl::StructTypeMap::iterator I = + pImpl->AnonStructTypes.find_as(Key); + StructType *ST; + + if (I == pImpl->AnonStructTypes.end()) { + // Value not found. Create a new type! + ST = new (Context.pImpl->TypeAllocator) StructType(Context); + ST->setSubclassData(SCDB_IsLiteral); // Literal struct. + ST->setBody(ETypes, isPacked); + Context.pImpl->AnonStructTypes[ST] = true; } else { - llvm_unreachable("Unknown derived type!"); - return false; + ST = I->first; } -} - -static bool TypesEqual(const Type *Ty, const Type *Ty2) { - std::map EqTypes; - return TypesEqual(Ty, Ty2, EqTypes); -} - -// AbstractTypeHasCycleThrough - Return true there is a path from CurTy to -// TargetTy in the type graph. We know that Ty is an abstract type, so if we -// ever reach a non-abstract type, we know that we don't need to search the -// subgraph. -static bool AbstractTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy, - SmallPtrSet &VisitedTypes) { - if (TargetTy == CurTy) return true; - if (!CurTy->isAbstract()) return false; - - if (!VisitedTypes.insert(CurTy)) - return false; // Already been here. - for (Type::subtype_iterator I = CurTy->subtype_begin(), - E = CurTy->subtype_end(); I != E; ++I) - if (AbstractTypeHasCycleThrough(TargetTy, *I, VisitedTypes)) - return true; - return false; + return ST; } -static bool ConcreteTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy, - SmallPtrSet &VisitedTypes) { - if (TargetTy == CurTy) return true; - - if (!VisitedTypes.insert(CurTy)) - return false; // Already been here. +void StructType::setBody(ArrayRef Elements, bool isPacked) { + assert(isOpaque() && "Struct body already set!"); + + setSubclassData(getSubclassData() | SCDB_HasBody); + if (isPacked) + setSubclassData(getSubclassData() | SCDB_Packed); - for (Type::subtype_iterator I = CurTy->subtype_begin(), - E = CurTy->subtype_end(); I != E; ++I) - if (ConcreteTypeHasCycleThrough(TargetTy, *I, VisitedTypes)) - return true; - return false; + unsigned NumElements = Elements.size(); + Type **Elts = getContext().pImpl->TypeAllocator.Allocate(NumElements); + memcpy(Elts, Elements.data(), sizeof(Elements[0]) * NumElements); + + ContainedTys = Elts; + NumContainedTys = NumElements; } -/// TypeHasCycleThroughItself - Return true if the specified type has a cycle -/// back to itself. -static bool TypeHasCycleThroughItself(const Type *Ty) { - SmallPtrSet VisitedTypes; +void StructType::setName(StringRef Name) { + if (Name == getName()) return; - if (Ty->isAbstract()) { // Optimized case for abstract types. - 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; -} + StringMap &SymbolTable = getContext().pImpl->NamedStructTypes; + typedef StringMap::MapEntryTy EntryTy; -//===----------------------------------------------------------------------===// -// Function Type Factory and Value Class... -// -const IntegerType *IntegerType::get(LLVMContext &C, unsigned NumBits) { - assert(NumBits >= MIN_INT_BITS && "bitwidth too small"); - assert(NumBits <= MAX_INT_BITS && "bitwidth too large"); + // If this struct already had a name, remove its symbol table entry. Don't + // delete the data yet because it may be part of the new name. + if (SymbolTableEntry) + SymbolTable.remove((EntryTy *)SymbolTableEntry); - // Check for the built-in integer types - switch (NumBits) { - case 1: return cast(Type::getInt1Ty(C)); - case 8: return cast(Type::getInt8Ty(C)); - case 16: return cast(Type::getInt16Ty(C)); - case 32: return cast(Type::getInt32Ty(C)); - case 64: return cast(Type::getInt64Ty(C)); - default: - break; + // If this is just removing the name, we're done. + if (Name.empty()) { + if (SymbolTableEntry) { + // Delete the old string data. + ((EntryTy *)SymbolTableEntry)->Destroy(SymbolTable.getAllocator()); + SymbolTableEntry = 0; + } + return; } - - LLVMContextImpl *pImpl = C.pImpl; - IntegerValType IVT(NumBits); - IntegerType *ITy = 0; + // Look up the entry for the name. + EntryTy *Entry = &getContext().pImpl->NamedStructTypes.GetOrCreateValue(Name); - // First, see if the type is already in the table, for which - // a reader lock suffices. - sys::SmartScopedLock L(pImpl->TypeMapLock); - ITy = pImpl->IntegerTypes.get(IVT); - - if (!ITy) { - // Value not found. Derive a new type! - ITy = new IntegerType(C, NumBits); - pImpl->IntegerTypes.add(IVT, ITy); + // While we have a name collision, try a random rename. + if (Entry->getValue()) { + SmallString<64> TempStr(Name); + TempStr.push_back('.'); + raw_svector_ostream TmpStream(TempStr); + unsigned NameSize = Name.size(); + + do { + TempStr.resize(NameSize + 1); + TmpStream.resync(); + TmpStream << getContext().pImpl->NamedStructTypesUniqueID++; + + Entry = &getContext().pImpl-> + NamedStructTypes.GetOrCreateValue(TmpStream.str()); + } while (Entry->getValue()); } -#ifdef DEBUG_MERGE_TYPES - DEBUG(errs() << "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()); -} + // Okay, we found an entry that isn't used. It's us! + Entry->setValue(this); -FunctionValType FunctionValType::get(const FunctionType *FT) { - // Build up a FunctionValType - std::vector 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()); + // Delete the old string data. + if (SymbolTableEntry) + ((EntryTy *)SymbolTableEntry)->Destroy(SymbolTable.getAllocator()); + SymbolTableEntry = Entry; } +//===----------------------------------------------------------------------===// +// StructType Helper functions. -// FunctionType::get - The factory function for the FunctionType class... -FunctionType *FunctionType::get(const Type *ReturnType, - const std::vector &Params, - bool isVarArg) { - FunctionValType VT(ReturnType, Params, isVarArg); - FunctionType *FT = 0; - - LLVMContextImpl *pImpl = ReturnType->getContext().pImpl; - - sys::SmartScopedLock L(pImpl->TypeMapLock); - FT = pImpl->FunctionTypes.get(VT); - - if (!FT) { - FT = (FunctionType*) operator new(sizeof(FunctionType) + - sizeof(PATypeHandle)*(Params.size()+1)); - new (FT) FunctionType(ReturnType, Params, isVarArg); - pImpl->FunctionTypes.add(VT, FT); - } - -#ifdef DEBUG_MERGE_TYPES - DEBUG(errs() << "Derived new type: " << FT << "\n"); -#endif - return FT; +StructType *StructType::create(LLVMContext &Context, StringRef Name) { + StructType *ST = new (Context.pImpl->TypeAllocator) StructType(Context); + if (!Name.empty()) + ST->setName(Name); + return ST; } -ArrayType *ArrayType::get(const Type *ElementType, uint64_t NumElements) { - assert(ElementType && "Can't get array of types!"); - assert(isValidElementType(ElementType) && "Invalid type for array element!"); - - ArrayValType AVT(ElementType, NumElements); - ArrayType *AT = 0; +StructType *StructType::get(LLVMContext &Context, bool isPacked) { + return get(Context, llvm::ArrayRef(), isPacked); +} - LLVMContextImpl *pImpl = ElementType->getContext().pImpl; - - sys::SmartScopedLock L(pImpl->TypeMapLock); - AT = pImpl->ArrayTypes.get(AVT); - - if (!AT) { - // Value not found. Derive a new type! - pImpl->ArrayTypes.add(AVT, AT = new ArrayType(ElementType, NumElements)); +StructType *StructType::get(Type *type, ...) { + assert(type != 0 && "Cannot create a struct type with no elements with this"); + LLVMContext &Ctx = type->getContext(); + va_list ap; + SmallVector StructFields; + va_start(ap, type); + while (type) { + StructFields.push_back(type); + type = va_arg(ap, llvm::Type*); } -#ifdef DEBUG_MERGE_TYPES - DEBUG(errs() << "Derived new type: " << *AT << "\n"); -#endif - return AT; + return llvm::StructType::get(Ctx, StructFields); } -bool ArrayType::isValidElementType(const Type *ElemTy) { - if (ElemTy == Type::getVoidTy(ElemTy->getContext()) || - ElemTy == Type::getLabelTy(ElemTy->getContext()) || - ElemTy == Type::getMetadataTy(ElemTy->getContext())) - return false; - - if (const PointerType *PTy = dyn_cast(ElemTy)) - if (PTy->getElementType() == Type::getMetadataTy(ElemTy->getContext())) - return false; - - return true; +StructType *StructType::create(LLVMContext &Context, ArrayRef Elements, + StringRef Name, bool isPacked) { + StructType *ST = create(Context, Name); + ST->setBody(Elements, isPacked); + return ST; } -VectorType *VectorType::get(const Type *ElementType, unsigned NumElements) { - assert(ElementType && "Can't get vector of types!"); - - VectorValType PVT(ElementType, NumElements); - VectorType *PT = 0; - - LLVMContextImpl *pImpl = ElementType->getContext().pImpl; - - sys::SmartScopedLock L(pImpl->TypeMapLock); - PT = pImpl->VectorTypes.get(PVT); - - if (!PT) { - pImpl->VectorTypes.add(PVT, PT = new VectorType(ElementType, NumElements)); - } -#ifdef DEBUG_MERGE_TYPES - DEBUG(errs() << "Derived new type: " << *PT << "\n"); -#endif - return PT; +StructType *StructType::create(LLVMContext &Context, ArrayRef Elements) { + return create(Context, Elements, StringRef()); } -bool VectorType::isValidElementType(const Type *ElemTy) { - if (ElemTy->isInteger() || ElemTy->isFloatingPoint() || - isa(ElemTy)) - return true; - - return false; +StructType *StructType::create(LLVMContext &Context) { + return create(Context, StringRef()); } -//===----------------------------------------------------------------------===// -// Struct Type Factory... -// +StructType *StructType::create(ArrayRef Elements, StringRef Name, + bool isPacked) { + assert(!Elements.empty() && + "This method may not be invoked with an empty list"); + return create(Elements[0]->getContext(), Elements, Name, isPacked); +} -StructType *StructType::get(LLVMContext &Context, - const std::vector &ETypes, - bool isPacked) { - StructValType STV(ETypes, isPacked); - StructType *ST = 0; - - LLVMContextImpl *pImpl = Context.pImpl; - - sys::SmartScopedLock L(pImpl->TypeMapLock); - ST = pImpl->StructTypes.get(STV); - - if (!ST) { - // Value not found. Derive a new type! - ST = (StructType*) operator new(sizeof(StructType) + - sizeof(PATypeHandle) * ETypes.size()); - new (ST) StructType(Context, ETypes, isPacked); - pImpl->StructTypes.add(STV, ST); - } -#ifdef DEBUG_MERGE_TYPES - DEBUG(errs() << "Derived new type: " << *ST << "\n"); -#endif - return ST; +StructType *StructType::create(ArrayRef Elements) { + assert(!Elements.empty() && + "This method may not be invoked with an empty list"); + return create(Elements[0]->getContext(), Elements, StringRef()); } -StructType *StructType::get(LLVMContext &Context, const Type *type, ...) { +StructType *StructType::create(StringRef Name, Type *type, ...) { + assert(type != 0 && "Cannot create a struct type with no elements with this"); + LLVMContext &Ctx = type->getContext(); va_list ap; - std::vector StructFields; + SmallVector StructFields; va_start(ap, type); while (type) { StructFields.push_back(type); type = va_arg(ap, llvm::Type*); } - return llvm::StructType::get(Context, StructFields); + return llvm::StructType::create(Ctx, StructFields, Name); } -bool StructType::isValidElementType(const Type *ElemTy) { - if (ElemTy == Type::getVoidTy(ElemTy->getContext()) || - ElemTy == Type::getLabelTy(ElemTy->getContext()) || - ElemTy == Type::getMetadataTy(ElemTy->getContext())) +bool StructType::isSized() const { + if ((getSubclassData() & SCDB_IsSized) != 0) + return true; + if (isOpaque()) return false; - if (const PointerType *PTy = dyn_cast(ElemTy)) - if (PTy->getElementType() == Type::getMetadataTy(ElemTy->getContext())) + // Okay, our struct is sized if all of the elements are, but if one of the + // elements is opaque, the struct isn't sized *yet*, but may become sized in + // the future, so just bail out without caching. + for (element_iterator I = element_begin(), E = element_end(); I != E; ++I) + if (!(*I)->isSized()) return false; + // Here we cheat a bit and cast away const-ness. The goal is to memoize when + // we find a sized type, as types can only move from opaque to sized, not the + // other way. + const_cast(this)->setSubclassData( + getSubclassData() | SCDB_IsSized); return true; } - -//===----------------------------------------------------------------------===// -// Pointer Type Factory... -// - -PointerType *PointerType::get(const Type *ValueType, unsigned AddressSpace) { - assert(ValueType && "Can't get a pointer to type!"); - assert(ValueType != Type::getVoidTy(ValueType->getContext()) && - "Pointer to void is not valid, use i8* instead!"); - assert(isValidElementType(ValueType) && "Invalid type for pointer element!"); - PointerValType PVT(ValueType, AddressSpace); - - PointerType *PT = 0; - - LLVMContextImpl *pImpl = ValueType->getContext().pImpl; - - sys::SmartScopedLock L(pImpl->TypeMapLock); - PT = pImpl->PointerTypes.get(PVT); +StringRef StructType::getName() const { + assert(!isLiteral() && "Literal structs never have names"); + if (SymbolTableEntry == 0) return StringRef(); - if (!PT) { - // Value not found. Derive a new type! - pImpl->PointerTypes.add(PVT, PT = new PointerType(ValueType, AddressSpace)); + return ((StringMapEntry *)SymbolTableEntry)->getKey(); +} + +void StructType::setBody(Type *type, ...) { + assert(type != 0 && "Cannot create a struct type with no elements with this"); + va_list ap; + SmallVector StructFields; + va_start(ap, type); + while (type) { + StructFields.push_back(type); + type = va_arg(ap, llvm::Type*); } -#ifdef DEBUG_MERGE_TYPES - DEBUG(errs() << "Derived new type: " << *PT << "\n"); -#endif - return PT; + setBody(StructFields); } -PointerType *Type::getPointerTo(unsigned addrs) const { - return PointerType::get(this, addrs); +bool StructType::isValidElementType(Type *ElemTy) { + return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() && + !ElemTy->isMetadataTy() && !ElemTy->isFunctionTy(); } -bool PointerType::isValidElementType(const Type *ElemTy) { - if (ElemTy == Type::getVoidTy(ElemTy->getContext()) || - ElemTy == Type::getLabelTy(ElemTy->getContext())) +/// isLayoutIdentical - Return true if this is layout identical to the +/// specified struct. +bool StructType::isLayoutIdentical(StructType *Other) const { + if (this == Other) return true; + + if (isPacked() != Other->isPacked() || + getNumElements() != Other->getNumElements()) return false; + + return std::equal(element_begin(), element_end(), Other->element_begin()); +} - if (const PointerType *PTy = dyn_cast(ElemTy)) - if (PTy->getElementType() == Type::getMetadataTy(ElemTy->getContext())) - return false; - - return true; +/// getTypeByName - Return the type with the specified name, or null if there +/// is none by that name. +StructType *Module::getTypeByName(StringRef Name) const { + StringMap::iterator I = + getContext().pImpl->NamedStructTypes.find(Name); + if (I != getContext().pImpl->NamedStructTypes.end()) + return I->second; + return 0; } //===----------------------------------------------------------------------===// -// Derived Type Refinement Functions +// CompositeType Implementation //===----------------------------------------------------------------------===// -// addAbstractTypeUser - Notify an abstract type that there is a new user of -// it. This function is called primarily by the PATypeHandle class. -void Type::addAbstractTypeUser(AbstractTypeUser *U) const { - assert(isAbstract() && "addAbstractTypeUser: Current type not abstract!"); - LLVMContextImpl *pImpl = getContext().pImpl; - pImpl->AbstractTypeUsersLock.acquire(); - AbstractTypeUsers.push_back(U); - pImpl->AbstractTypeUsersLock.release(); -} - - -// removeAbstractTypeUser - Notify an abstract type that a user of the class -// no longer has a handle to the type. This function is called primarily by -// the PATypeHandle class. When there are no users of the abstract type, it -// is annihilated, because there is no way to get a reference to it ever again. -// -void Type::removeAbstractTypeUser(AbstractTypeUser *U) const { - LLVMContextImpl *pImpl = getContext().pImpl; - pImpl->AbstractTypeUsersLock.acquire(); - - // Search from back to front because we will notify users from back to - // front. Also, it is likely that there will be a stack like behavior to - // users that register and unregister users. - // - unsigned i; - for (i = AbstractTypeUsers.size(); AbstractTypeUsers[i-1] != U; --i) - assert(i != 0 && "AbstractTypeUser not in user list!"); - - --i; // Convert to be in range 0 <= i < size() - assert(i < AbstractTypeUsers.size() && "Index out of range!"); // Wraparound? - - AbstractTypeUsers.erase(AbstractTypeUsers.begin()+i); - -#ifdef DEBUG_MERGE_TYPES - DEBUG(errs() << " remAbstractTypeUser[" << (void*)this << ", " - << *this << "][" << i << "] User = " << U << "\n"); -#endif - - if (AbstractTypeUsers.empty() && getRefCount() == 0 && isAbstract()) { -#ifdef DEBUG_MERGE_TYPES - DEBUG(errs() << "DELETEing unused abstract type: <" << *this - << ">[" << (void*)this << "]" << "\n"); -#endif - - this->destroy(); +Type *CompositeType::getTypeAtIndex(const Value *V) { + if (StructType *STy = dyn_cast(this)) { + unsigned Idx = (unsigned)cast(V)->getZExtValue(); + assert(indexValid(Idx) && "Invalid structure index!"); + return STy->getElementType(Idx); } - pImpl->AbstractTypeUsersLock.release(); + return cast(this)->getElementType(); } - -// unlockedRefineAbstractTypeTo - This function is used when it is discovered -// that the 'this' abstract type is actually equivalent to the NewType -// specified. This causes all users of 'this' to switch to reference the more -// concrete type NewType and for 'this' to be deleted. Only used for internal -// callers. -// -void DerivedType::unlockedRefineAbstractTypeTo(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!"); - - LLVMContextImpl *pImpl = getContext().pImpl; - - // The descriptions may be out of date. Conservatively clear them all! - pImpl->AbstractTypeDescriptions.clear(); - -#ifdef DEBUG_MERGE_TYPES - DEBUG(errs() << "REFINING abstract type [" << (void*)this << " " - << *this << "] to [" << (void*)NewType << " " - << *NewType << "]!\n"); -#endif - - // Make sure to put the type to be refined to into a holder so that if IT gets - // refined, that we will not continue using a dead reference... - // - PATypeHolder NewTy(NewType); - // Any PATypeHolders referring to this type will now automatically forward o - // the type we are resolved to. - ForwardType = NewType; - if (NewType->isAbstract()) - cast(NewType)->addRef(); - - // Add a self use of the current type so that we don't delete ourself until - // after the function exits. - // - PATypeHolder CurrentTy(this); - - // To make the situation simpler, we ask the subclass to remove this type from - // the type map, and to replace any type uses with uses of non-abstract types. - // This dramatically limits the amount of recursive type trouble we can find - // ourselves in. - dropAllTypeUses(); - - // Iterate over all of the uses of this type, invoking callback. Each user - // should remove itself from our use list automatically. We have to check to - // make sure that NewTy doesn't _become_ 'this'. If it does, resolving types - // will not cause users to drop off of the use list. If we resolve to ourself - // we succeed! - // - pImpl->AbstractTypeUsersLock.acquire(); - while (!AbstractTypeUsers.empty() && NewTy != this) { - AbstractTypeUser *User = AbstractTypeUsers.back(); - - unsigned OldSize = AbstractTypeUsers.size(); OldSize=OldSize; -#ifdef DEBUG_MERGE_TYPES - DEBUG(errs() << " 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!"); +Type *CompositeType::getTypeAtIndex(unsigned Idx) { + if (StructType *STy = dyn_cast(this)) { + assert(indexValid(Idx) && "Invalid structure index!"); + return STy->getElementType(Idx); } - pImpl->AbstractTypeUsersLock.release(); - - // If we were successful removing all users from the type, 'this' will be - // deleted when the last PATypeHolder is destroyed or updated from this type. - // This may occur on exit of this function, as the CurrentTy object is - // destroyed. + + return cast(this)->getElementType(); +} +bool CompositeType::indexValid(const Value *V) const { + if (const StructType *STy = dyn_cast(this)) { + // Structure indexes require 32-bit integer constants. + if (V->getType()->isIntegerTy(32)) + if (const ConstantInt *CU = dyn_cast(V)) + return CU->getZExtValue() < STy->getNumElements(); + return false; + } + + // Sequential types can be indexed by any integer. + return V->getType()->isIntegerTy(); } -// refineAbstractTypeTo - This function is used by external callers to notify -// us that this abstract type is equivalent to another type. -// -void DerivedType::refineAbstractTypeTo(const Type *NewType) { - // All recursive calls will go through unlockedRefineAbstractTypeTo, - // to avoid deadlock problems. - sys::SmartScopedLock L(NewType->getContext().pImpl->TypeMapLock); - unlockedRefineAbstractTypeTo(NewType); +bool CompositeType::indexValid(unsigned Idx) const { + if (const StructType *STy = dyn_cast(this)) + return Idx < STy->getNumElements(); + // Sequential types can be indexed by any integer. + return true; } -// notifyUsesThatTypeBecameConcrete - Notify AbstractTypeUsers of this type that -// the current type has transitioned from being abstract to being concrete. -// -void DerivedType::notifyUsesThatTypeBecameConcrete() { -#ifdef DEBUG_MERGE_TYPES - DEBUG(errs() << "typeIsREFINED type: " << (void*)this << " " << *this <<"\n"); -#endif - LLVMContextImpl *pImpl = getContext().pImpl; - - pImpl->AbstractTypeUsersLock.acquire(); - unsigned OldSize = AbstractTypeUsers.size(); OldSize=OldSize; - while (!AbstractTypeUsers.empty()) { - AbstractTypeUser *ATU = AbstractTypeUsers.back(); - ATU->typeBecameConcrete(this); +//===----------------------------------------------------------------------===// +// ArrayType Implementation +//===----------------------------------------------------------------------===// - assert(AbstractTypeUsers.size() < OldSize-- && - "AbstractTypeUser did not remove itself from the use list!"); - } - pImpl->AbstractTypeUsersLock.release(); +ArrayType::ArrayType(Type *ElType, uint64_t NumEl) + : SequentialType(ArrayTyID, ElType) { + NumElements = NumEl; } -// refineAbstractType - Called when a contained type is found to be more -// concrete - this could potentially change us from an abstract type to a -// concrete type. -// -void FunctionType::refineAbstractType(const DerivedType *OldType, - const Type *NewType) { - LLVMContextImpl *pImpl = OldType->getContext().pImpl; - pImpl->FunctionTypes.RefineAbstractType(this, OldType, NewType); +ArrayType *ArrayType::get(Type *elementType, uint64_t NumElements) { + Type *ElementType = const_cast(elementType); + assert(isValidElementType(ElementType) && "Invalid type for array element!"); + + LLVMContextImpl *pImpl = ElementType->getContext().pImpl; + ArrayType *&Entry = + pImpl->ArrayTypes[std::make_pair(ElementType, NumElements)]; + + if (Entry == 0) + Entry = new (pImpl->TypeAllocator) ArrayType(ElementType, NumElements); + return Entry; } -void FunctionType::typeBecameConcrete(const DerivedType *AbsTy) { - LLVMContextImpl *pImpl = AbsTy->getContext().pImpl; - pImpl->FunctionTypes.TypeBecameConcrete(this, AbsTy); +bool ArrayType::isValidElementType(Type *ElemTy) { + return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() && + !ElemTy->isMetadataTy() && !ElemTy->isFunctionTy(); } +//===----------------------------------------------------------------------===// +// VectorType Implementation +//===----------------------------------------------------------------------===// -// refineAbstractType - Called when a contained type is found to be more -// concrete - this could potentially change us from an abstract type to a -// concrete type. -// -void ArrayType::refineAbstractType(const DerivedType *OldType, - const Type *NewType) { - LLVMContextImpl *pImpl = OldType->getContext().pImpl; - pImpl->ArrayTypes.RefineAbstractType(this, OldType, NewType); +VectorType::VectorType(Type *ElType, unsigned NumEl) + : SequentialType(VectorTyID, ElType) { + NumElements = NumEl; } -void ArrayType::typeBecameConcrete(const DerivedType *AbsTy) { - LLVMContextImpl *pImpl = AbsTy->getContext().pImpl; - pImpl->ArrayTypes.TypeBecameConcrete(this, AbsTy); +VectorType *VectorType::get(Type *elementType, unsigned NumElements) { + Type *ElementType = const_cast(elementType); + assert(NumElements > 0 && "#Elements of a VectorType must be greater than 0"); + assert(isValidElementType(ElementType) && + "Elements of a VectorType must be a primitive type"); + + LLVMContextImpl *pImpl = ElementType->getContext().pImpl; + VectorType *&Entry = ElementType->getContext().pImpl + ->VectorTypes[std::make_pair(ElementType, NumElements)]; + + if (Entry == 0) + Entry = new (pImpl->TypeAllocator) VectorType(ElementType, NumElements); + return Entry; } -// refineAbstractType - Called when a contained type is found to be more -// concrete - this could potentially change us from an abstract type to a -// concrete type. -// -void VectorType::refineAbstractType(const DerivedType *OldType, - const Type *NewType) { - LLVMContextImpl *pImpl = OldType->getContext().pImpl; - pImpl->VectorTypes.RefineAbstractType(this, OldType, NewType); +bool VectorType::isValidElementType(Type *ElemTy) { + if (PointerType *PTy = dyn_cast(ElemTy)) + ElemTy = PTy->getElementType(); + return ElemTy->isIntegerTy() || ElemTy->isFloatingPointTy(); } -void VectorType::typeBecameConcrete(const DerivedType *AbsTy) { - LLVMContextImpl *pImpl = AbsTy->getContext().pImpl; - pImpl->VectorTypes.TypeBecameConcrete(this, AbsTy); -} +//===----------------------------------------------------------------------===// +// PointerType Implementation +//===----------------------------------------------------------------------===// -// refineAbstractType - Called when a contained type is found to be more -// concrete - this could potentially change us from an abstract type to a -// concrete type. -// -void StructType::refineAbstractType(const DerivedType *OldType, - const Type *NewType) { - LLVMContextImpl *pImpl = OldType->getContext().pImpl; - pImpl->StructTypes.RefineAbstractType(this, OldType, NewType); -} +PointerType *PointerType::get(Type *EltTy, unsigned AddressSpace) { + assert(EltTy && "Can't get a pointer to type!"); + assert(isValidElementType(EltTy) && "Invalid type for pointer element!"); + + LLVMContextImpl *CImpl = EltTy->getContext().pImpl; + + // Since AddressSpace #0 is the common case, we special case it. + PointerType *&Entry = AddressSpace == 0 ? CImpl->PointerTypes[EltTy] + : CImpl->ASPointerTypes[std::make_pair(EltTy, AddressSpace)]; -void StructType::typeBecameConcrete(const DerivedType *AbsTy) { - LLVMContextImpl *pImpl = AbsTy->getContext().pImpl; - pImpl->StructTypes.TypeBecameConcrete(this, AbsTy); + if (Entry == 0) + Entry = new (CImpl->TypeAllocator) PointerType(EltTy, AddressSpace); + return Entry; } -// refineAbstractType - Called when a contained type is found to be more -// concrete - this could potentially change us from an abstract type to a -// concrete type. -// -void PointerType::refineAbstractType(const DerivedType *OldType, - const Type *NewType) { - LLVMContextImpl *pImpl = OldType->getContext().pImpl; - pImpl->PointerTypes.RefineAbstractType(this, OldType, NewType); -} -void PointerType::typeBecameConcrete(const DerivedType *AbsTy) { - LLVMContextImpl *pImpl = AbsTy->getContext().pImpl; - pImpl->PointerTypes.TypeBecameConcrete(this, AbsTy); +PointerType::PointerType(Type *E, unsigned AddrSpace) + : SequentialType(PointerTyID, E) { +#ifndef NDEBUG + const unsigned oldNCT = NumContainedTys; +#endif + setSubclassData(AddrSpace); + // Check for miscompile. PR11652. + assert(oldNCT == NumContainedTys && "bitfield written out of bounds?"); } -bool SequentialType::indexValid(const Value *V) const { - if (isa(V->getType())) - return true; - return false; +PointerType *Type::getPointerTo(unsigned addrs) { + return PointerType::get(this, addrs); } -namespace llvm { -raw_ostream &operator<<(raw_ostream &OS, const Type &T) { - T.print(OS); - return OS; -} +bool PointerType::isValidElementType(Type *ElemTy) { + return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() && + !ElemTy->isMetadataTy(); }