X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FType.cpp;h=3a9ea582f112efb088d357bd55f48f55f133986e;hb=ebcba612b537f45a033ccd9a60bee0c45e2e2ded;hp=c9312a86c972913e31e214edc928c3a07e21a45f;hpb=22cab6c752c75f81c05c679befd437e613138f6f;p=oota-llvm.git diff --git a/lib/VMCore/Type.cpp b/lib/VMCore/Type.cpp index c9312a86c97..3a9ea582f11 100644 --- a/lib/VMCore/Type.cpp +++ b/lib/VMCore/Type.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -11,26 +11,44 @@ // //===----------------------------------------------------------------------===// -#include "llvm/AbstractTypeUser.h" #include "llvm/DerivedTypes.h" -#include "llvm/SymbolTable.h" #include "llvm/Constants.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/ManagedStatic.h" +#include "llvm/Support/Debug.h" #include -#include +#include 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 +// #define DEBUG_MERGE_TYPES 1 AbstractTypeUser::~AbstractTypeUser() {} + +//===----------------------------------------------------------------------===// +// Type PATypeHolder Implementation +//===----------------------------------------------------------------------===// + +/// get - This implements the forwarding part of the union-find algorithm for +/// abstract types. Before every access to the Type*, we check to see if the +/// type we are pointing to is forwarding to a new type. If so, we drop our +/// reference to the type. +/// +Type* PATypeHolder::get() const { + const Type *NewTy = Ty->getForwardedType(); + if (!NewTy) return const_cast(Ty); + return *const_cast(this) = NewTy; +} + //===----------------------------------------------------------------------===// // Type Class Implementation //===----------------------------------------------------------------------===// @@ -39,133 +57,133 @@ AbstractTypeUser::~AbstractTypeUser() {} // for types as they are needed. Because resolution of types must invalidate // all of the abstract type descriptions, we keep them in a seperate map to make // this easy. -static std::map ConcreteTypeDescriptions; -static std::map AbstractTypeDescriptions; +static ManagedStatic > ConcreteTypeDescriptions; +static ManagedStatic > AbstractTypeDescriptions; + +/// 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)) + ((FunctionType*)this)->FunctionType::~FunctionType(); + else + ((StructType*)this)->StructType::~StructType(); + + // Finally, remove the memory as an array deallocation of the chars it was + // constructed from. + delete [] reinterpret_cast(this); + + return; + } -Type::Type( const std::string& name, TypeID id ) - : RefCount(0), ForwardType(0) { - if (!name.empty()) - ConcreteTypeDescriptions[this] = name; - ID = id; - Abstract = false; + // 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(TypeID IDNumber) { switch (IDNumber) { - case VoidTyID : return VoidTy; - case BoolTyID : return BoolTy; - case UByteTyID : return UByteTy; - case SByteTyID : return SByteTy; - case UShortTyID: return UShortTy; - case ShortTyID : return ShortTy; - case UIntTyID : return UIntTy; - case IntTyID : return IntTy; - case ULongTyID : return ULongTy; - case LongTyID : return LongTy; - case FloatTyID : return FloatTy; - case DoubleTyID: return DoubleTy; - case LabelTyID : return LabelTy; + 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; } } -// isLosslesslyConvertibleTo - Return true if this type can be converted to -// 'Ty' without any reinterpretation of bits. For example, uint to int. -// -bool Type::isLosslesslyConvertibleTo(const Type *Ty) const { - if (this == Ty) return true; - if ((!isPrimitiveType() && !isa(this)) || - (!isa(Ty) && !Ty->isPrimitiveType())) return false; - - if (getTypeID() == Ty->getTypeID()) - return true; // Handles identity cast, and cast of differing pointer types - - // Now we know that they are two differing primitive or pointer types - switch (getTypeID()) { - case Type::UByteTyID: return Ty == Type::SByteTy; - case Type::SByteTyID: return Ty == Type::UByteTy; - case Type::UShortTyID: return Ty == Type::ShortTy; - case Type::ShortTyID: return Ty == Type::UShortTy; - case Type::UIntTyID: return Ty == Type::IntTy; - case Type::IntTyID: return Ty == Type::UIntTy; - case Type::ULongTyID: return Ty == Type::LongTy; - case Type::LongTyID: return Ty == Type::ULongTy; - case Type::PointerTyID: return isa(Ty); - default: - return false; // Other types have no identity values - } +const Type *Type::getVAArgsPromotedType() const { + if (ID == IntegerTyID && getSubclassData() < 32) + return Type::Int32Ty; + else if (ID == FloatTyID) + return Type::DoubleTy; + else + return this; } -/// getUnsignedVersion - If this is an integer type, return the unsigned -/// variant of this type. For example int -> uint. -const Type *Type::getUnsignedVersion() const { - switch (getTypeID()) { - default: - assert(isInteger()&&"Type::getUnsignedVersion is only valid for integers!"); - case Type::UByteTyID: - case Type::SByteTyID: return Type::UByteTy; - case Type::UShortTyID: - case Type::ShortTyID: return Type::UShortTy; - case Type::UIntTyID: - case Type::IntTyID: return Type::UIntTy; - case Type::ULongTyID: - case Type::LongTyID: return Type::ULongTy; - } +/// 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(); } -/// getSignedVersion - If this is an integer type, return the signed variant -/// of this type. For example uint -> int. -const Type *Type::getSignedVersion() const { - switch (getTypeID()) { - default: - assert(isInteger() && "Type::getSignedVersion is only valid for integers!"); - case Type::UByteTyID: - case Type::SByteTyID: return Type::SByteTy; - case Type::UShortTyID: - case Type::ShortTyID: return Type::ShortTy; - case Type::UIntTyID: - case Type::IntTyID: return Type::IntTy; - case Type::ULongTyID: - case Type::LongTyID: return Type::LongTy; - } +/// 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(); } - -// getPrimitiveSize - Return the basic size of this type if it is a primitive -// type. These are fixed by LLVM and are not target dependent. This will -// return zero if the type does not have a size or is not a primitive type. +// canLosslesllyBitCastTo - Return true if this type can be converted to +// 'Ty' without any reinterpretation of bits. For example, uint to int. // -unsigned Type::getPrimitiveSize() const { - switch (getTypeID()) { - case Type::BoolTyID: - case Type::SByteTyID: - case Type::UByteTyID: return 1; - case Type::UShortTyID: - case Type::ShortTyID: return 2; - case Type::FloatTyID: - case Type::IntTyID: - case Type::UIntTyID: return 4; - case Type::LongTyID: - case Type::ULongTyID: - case Type::DoubleTyID: return 8; - default: return 0; - } +bool Type::canLosslesslyBitCastTo(const Type *Ty) const { + // Identity cast means no change so return true + if (this == Ty) + return true; + + // They are not convertible unless they are at least first class types + if (!this->isFirstClassType() || !Ty->isFirstClassType()) + 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)) + if (const VectorType *thatPTy = dyn_cast(Ty)) + return thisPTy->getBitWidth() == thatPTy->getBitWidth(); + + // 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); + return false; // Other types have no identity values } unsigned Type::getPrimitiveSizeInBits() const { switch (getTypeID()) { - case Type::BoolTyID: return 1; - case Type::SByteTyID: - case Type::UByteTyID: return 8; - case Type::UShortTyID: - case Type::ShortTyID: return 16; - case Type::FloatTyID: - case Type::IntTyID: - case Type::UIntTyID: return 32; - case Type::LongTyID: - case Type::ULongTyID: + 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(this)->getBitWidth(); + case Type::VectorTyID: return cast(this)->getBitWidth(); default: return 0; } } @@ -174,17 +192,22 @@ unsigned Type::getPrimitiveSizeInBits() 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)) + return true; + if (const ArrayType *ATy = dyn_cast(this)) return ATy->getElementType()->isSized(); - if (const PackedType *PTy = dyn_cast(this)) + if (const VectorType *PTy = dyn_cast(this)) return PTy->getElementType()->isSized(); - if (!isa(this)) return false; + if (!isa(this)) + 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; + if (!(*I)->isSized()) + return false; return true; } @@ -213,6 +236,14 @@ const Type *Type::getForwardedTypeInternal() const { return ForwardType; } +void Type::refineAbstractType(const DerivedType *OldTy, const Type *NewTy) { + abort(); +} +void Type::typeBecameConcrete(const DerivedType *AbsTy) { + abort(); +} + + // getTypeDescription - This is a recursive function that walks a type hierarchy // calculating the description for a type. // @@ -220,18 +251,34 @@ static std::string getTypeDescription(const Type *Ty, std::vector &TypeStack) { if (isa(Ty)) { // Base case for the recursion std::map::iterator I = - AbstractTypeDescriptions.lower_bound(Ty); - if (I != AbstractTypeDescriptions.end() && I->first == Ty) + AbstractTypeDescriptions->lower_bound(Ty); + if (I != AbstractTypeDescriptions->end() && I->first == Ty) return I->second; std::string Desc = "opaque"; - AbstractTypeDescriptions.insert(std::make_pair(Ty, Desc)); + AbstractTypeDescriptions->insert(std::make_pair(Ty, Desc)); return Desc; } if (!Ty->isAbstract()) { // Base case for the recursion std::map::iterator I = - ConcreteTypeDescriptions.find(Ty); - if (I != ConcreteTypeDescriptions.end()) return I->second; + ConcreteTypeDescriptions->find(Ty); + if (I != ConcreteTypeDescriptions->end()) + return I->second; + + if (Ty->isPrimitiveType()) { + switch (Ty->getTypeID()) { + default: assert(0 && "Unknown prim type!"); + case Type::VoidTyID: return (*ConcreteTypeDescriptions)[Ty] = "void"; + case Type::FloatTyID: return (*ConcreteTypeDescriptions)[Ty] = "float"; + case Type::DoubleTyID: return (*ConcreteTypeDescriptions)[Ty] = "double"; + case Type::X86_FP80TyID: + return (*ConcreteTypeDescriptions)[Ty] = "x86_fp80"; + case Type::FP128TyID: return (*ConcreteTypeDescriptions)[Ty] = "fp128"; + case Type::PPC_FP128TyID: + return (*ConcreteTypeDescriptions)[Ty] = "ppc_fp128"; + case Type::LabelTyID: return (*ConcreteTypeDescriptions)[Ty] = "label"; + } + } } // Check to see if the Type is already on the stack... @@ -250,11 +297,18 @@ static std::string getTypeDescription(const Type *Ty, TypeStack.push_back(Ty); // Add us to the stack.. switch (Ty->getTypeID()) { + case Type::IntegerTyID: { + const IntegerType *ITy = cast(Ty); + Result = "i" + utostr(ITy->getBitWidth()); + break; + } case Type::FunctionTyID: { const FunctionType *FTy = cast(Ty); - Result = getTypeDescription(FTy->getReturnType(), TypeStack) + " ("; + if (!Result.empty()) + Result += " "; + Result += getTypeDescription(FTy->getReturnType(), TypeStack) + " ("; for (FunctionType::param_iterator I = FTy->param_begin(), - E = FTy->param_end(); I != E; ++I) { + E = FTy->param_end(); I != E; ++I) { if (I != FTy->param_begin()) Result += ", "; Result += getTypeDescription(*I, TypeStack); @@ -268,7 +322,10 @@ static std::string getTypeDescription(const Type *Ty, } case Type::StructTyID: { const StructType *STy = cast(Ty); - Result = "{ "; + if (STy->isPacked()) + Result = "<{ "; + else + Result = "{ "; for (StructType::element_iterator I = STy->element_begin(), E = STy->element_end(); I != E; ++I) { if (I != STy->element_begin()) @@ -276,11 +333,16 @@ static std::string getTypeDescription(const Type *Ty, Result += getTypeDescription(*I, TypeStack); } Result += " }"; + if (STy->isPacked()) + Result += ">"; break; } case Type::PointerTyID: { const PointerType *PTy = cast(Ty); - Result = getTypeDescription(PTy->getElementType(), TypeStack) + " *"; + Result = getTypeDescription(PTy->getElementType(), TypeStack); + if (unsigned AddressSpace = PTy->getAddressSpace()) + Result += " addrspace(" + utostr(AddressSpace) + ")"; + Result += " *"; break; } case Type::ArrayTyID: { @@ -291,8 +353,8 @@ static std::string getTypeDescription(const Type *Ty, Result += getTypeDescription(ATy->getElementType(), TypeStack) + "]"; break; } - case Type::PackedTyID: { - const PackedType *PTy = cast(Ty); + case Type::VectorTyID: { + const VectorType *PTy = cast(Ty); unsigned NumElements = PTy->getNumElements(); Result = "<"; Result += utostr(NumElements) + " x "; @@ -324,89 +386,101 @@ static const std::string &getOrCreateDesc(std::map&Map, const std::string &Type::getDescription() const { if (isAbstract()) - return getOrCreateDesc(AbstractTypeDescriptions, this); + return getOrCreateDesc(*AbstractTypeDescriptions, this); else - return getOrCreateDesc(ConcreteTypeDescriptions, this); + return getOrCreateDesc(*ConcreteTypeDescriptions, this); } bool StructType::indexValid(const Value *V) const { - // Structure indexes require unsigned integer constants. - if (V->getType() == Type::UIntTy) - if (const ConstantUInt *CU = dyn_cast(V)) - return CU->getValue() < ContainedTys.size(); + // Structure indexes require 32-bit integer constants. + if (V->getType() == Type::Int32Ty) + if (const ConstantInt *CU = dyn_cast(V)) + return indexValid(CU->getZExtValue()); return false; } +bool StructType::indexValid(unsigned V) const { + return V < NumContainedTys; +} + // 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 { - assert(indexValid(V) && "Invalid structure index!"); - unsigned Idx = (unsigned)cast(V)->getValue(); - return ContainedTys[Idx]; + unsigned Idx = (unsigned)cast(V)->getZExtValue(); + return getTypeAtIndex(Idx); } +const Type *StructType::getTypeAtIndex(unsigned Idx) const { + assert(indexValid(Idx) && "Invalid structure index!"); + return ContainedTys[Idx]; +} //===----------------------------------------------------------------------===// -// Static 'Type' data +// Primitive 'Type' data //===----------------------------------------------------------------------===// +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 PrimType : public Type { - PrimType(const char *S, TypeID ID) : Type(S, ID) {} + struct BuiltinIntegerType : public IntegerType { + BuiltinIntegerType(unsigned W) : IntegerType(W) {} }; } - -static PrimType TheVoidTy ("void" , Type::VoidTyID); -static PrimType TheBoolTy ("bool" , Type::BoolTyID); -static PrimType TheSByteTy ("sbyte" , Type::SByteTyID); -static PrimType TheUByteTy ("ubyte" , Type::UByteTyID); -static PrimType TheShortTy ("short" , Type::ShortTyID); -static PrimType TheUShortTy("ushort", Type::UShortTyID); -static PrimType TheIntTy ("int" , Type::IntTyID); -static PrimType TheUIntTy ("uint" , Type::UIntTyID); -static PrimType TheLongTy ("long" , Type::LongTyID); -static PrimType TheULongTy ("ulong" , Type::ULongTyID); -static PrimType TheFloatTy ("float" , Type::FloatTyID); -static PrimType TheDoubleTy("double", Type::DoubleTyID); -static PrimType TheLabelTy ("label" , Type::LabelTyID); - -Type *Type::VoidTy = &TheVoidTy; -Type *Type::BoolTy = &TheBoolTy; -Type *Type::SByteTy = &TheSByteTy; -Type *Type::UByteTy = &TheUByteTy; -Type *Type::ShortTy = &TheShortTy; -Type *Type::UShortTy = &TheUShortTy; -Type *Type::IntTy = &TheIntTy; -Type *Type::UIntTy = &TheUIntTy; -Type *Type::LongTy = &TheLongTy; -Type *Type::ULongTy = &TheULongTy; -Type *Type::FloatTy = &TheFloatTy; -Type *Type::DoubleTy = &TheDoubleTy; -Type *Type::LabelTy = &TheLabelTy; +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); //===----------------------------------------------------------------------===// // Derived Type Constructors //===----------------------------------------------------------------------===// +/// isValidReturnType - Return true if the specified type is valid as a return +/// type. +bool FunctionType::isValidReturnType(const Type *RetTy) { + if (RetTy->isFirstClassType()) + return true; + if (RetTy == Type::VoidTy || 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; + + 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 &Params, - bool IsVarArgs) : DerivedType(FunctionTyID), - isVarArgs(IsVarArgs) { - assert((Result->isFirstClassType() || Result == Type::VoidTy || - isa(Result)) && - "LLVM functions cannot return aggregates"); + bool IsVarArgs) + : DerivedType(FunctionTyID), isVarArgs(IsVarArgs) { + ContainedTys = reinterpret_cast(this+1); + NumContainedTys = Params.size() + 1; // + 1 for result type + assert(isValidReturnType(Result) && "invalid return type for function"); + + bool isAbstract = Result->isAbstract(); - ContainedTys.reserve(Params.size()+1); - ContainedTys.push_back(PATypeHandle(Result, this)); + new (&ContainedTys[0]) PATypeHandle(Result, this); for (unsigned i = 0; i != Params.size(); ++i) { assert((Params[i]->isFirstClassType() || isa(Params[i])) && "Function arguments must be value types!"); - - ContainedTys.push_back(PATypeHandle(Params[i], this)); + new (&ContainedTys[i+1]) PATypeHandle(Params[i],this); isAbstract |= Params[i]->isAbstract(); } @@ -414,13 +488,15 @@ FunctionType::FunctionType(const Type *Result, setAbstract(isAbstract); } -StructType::StructType(const std::vector &Types) +StructType::StructType(const std::vector &Types, bool isPacked) : CompositeType(StructTyID) { - ContainedTys.reserve(Types.size()); + 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::VoidTy && "Void type for structure field!!"); - ContainedTys.push_back(PATypeHandle(Types[i], this)); + new (&ContainedTys[i]) PATypeHandle(Types[i], this); isAbstract |= Types[i]->isAbstract(); } @@ -436,17 +512,21 @@ ArrayType::ArrayType(const Type *ElType, uint64_t NumEl) setAbstract(ElType->isAbstract()); } -PackedType::PackedType(const Type *ElType, unsigned NumEl) - : SequentialType(PackedTyID, ElType) { +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(ElType)) && + "Elements of a VectorType must be a primitive type"); - assert(NumEl > 0 && "NumEl of a PackedType must be greater than 0"); - assert((ElType->isIntegral() || ElType->isFloatingPoint()) && - "Elements of a PackedType must be a primitive type"); } -PointerType::PointerType(const Type *E) : SequentialType(PointerTyID, E) { +PointerType::PointerType(const Type *E, unsigned AddrSpace) + : SequentialType(PointerTyID, E) { + AddressSpace = AddrSpace; // Calculate whether or not this type is abstract setAbstract(E->isAbstract()); } @@ -454,7 +534,7 @@ PointerType::PointerType(const Type *E) : SequentialType(PointerTyID, E) { OpaqueType::OpaqueType() : DerivedType(OpaqueTyID) { setAbstract(true); #ifdef DEBUG_MERGE_TYPES - std::cerr << "Derived new type: " << *this << "\n"; + DOUT << "Derived new type: " << *this << "\n"; #endif } @@ -462,19 +542,23 @@ OpaqueType::OpaqueType() : DerivedType(OpaqueTyID) { // another (more concrete) type, we must eliminate all references to other // types, to avoid some circular reference problems. void DerivedType::dropAllTypeUses() { - if (!ContainedTys.empty()) { - while (ContainedTys.size() > 1) - ContainedTys.pop_back(); - + 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 = OpaqueType::get(); static PATypeHolder Holder(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::Int32Ty; } } +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 @@ -485,6 +569,8 @@ struct TypePromotionGraph { TypePromotionGraph(Type *T) : Ty(T) {} }; +} + namespace llvm { template <> struct GraphTraits { typedef Type NodeType; @@ -581,12 +667,17 @@ static bool TypesEqual(const Type *Ty, const Type *Ty2, // 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 PointerType *PTy = dyn_cast(Ty)) { - return TypesEqual(PTy->getElementType(), - cast(Ty2)->getElementType(), EqTypes); + 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; @@ -595,8 +686,8 @@ static bool TypesEqual(const Type *Ty, const Type *Ty2, const ArrayType *ATy2 = cast(Ty2); return ATy->getNumElements() == ATy2->getNumElements() && TypesEqual(ATy->getElementType(), ATy2->getElementType(), EqTypes); - } else if (const PackedType *PTy = dyn_cast(Ty)) { - const PackedType *PTy2 = cast(Ty2); + } 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)) { @@ -605,9 +696,10 @@ static bool TypesEqual(const Type *Ty, const Type *Ty2, FTy->getNumParams() != FTy2->getNumParams() || !TypesEqual(FTy->getReturnType(), FTy2->getReturnType(), EqTypes)) return false; - for (unsigned i = 0, e = FTy2->getNumParams(); i != e; ++i) + 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!"); @@ -625,11 +717,11 @@ static bool TypesEqual(const Type *Ty, const Type *Ty2) { // 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, - std::set &VisitedTypes) { + SmallPtrSet &VisitedTypes) { if (TargetTy == CurTy) return true; if (!CurTy->isAbstract()) return false; - if (!VisitedTypes.insert(CurTy).second) + if (!VisitedTypes.insert(CurTy)) return false; // Already been here. for (Type::subtype_iterator I = CurTy->subtype_begin(), @@ -640,10 +732,10 @@ static bool AbstractTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy, } static bool ConcreteTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy, - std::set &VisitedTypes) { + SmallPtrSet &VisitedTypes) { if (TargetTy == CurTy) return true; - if (!VisitedTypes.insert(CurTy).second) + if (!VisitedTypes.insert(CurTy)) return false; // Already been here. for (Type::subtype_iterator I = CurTy->subtype_begin(), @@ -656,7 +748,7 @@ static bool ConcreteTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy, /// TypeHasCycleThroughItself - Return true if the specified type has a cycle /// back to itself. static bool TypeHasCycleThroughItself(const Type *Ty) { - std::set VisitedTypes; + SmallPtrSet VisitedTypes; if (Ty->isAbstract()) { // Optimized case for abstract types. for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); @@ -672,36 +764,104 @@ static bool TypeHasCycleThroughItself(const Type *Ty) { return false; } +/// getSubElementHash - Generate a hash value for all of the SubType's of this +/// type. The hash value is guaranteed to be zero if any of the subtypes are +/// an opaque type. Otherwise we try to mix them in as well as possible, but do +/// not look at the subtype's subtype's. +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; // Opaque -> hash = 0 no matter what. + case Type::IntegerTyID: + HashVal ^= (cast(SubTy)->getBitWidth() << 3); + break; + case Type::FunctionTyID: + HashVal ^= cast(SubTy)->getNumParams()*2 + + cast(SubTy)->isVarArg(); + break; + case Type::ArrayTyID: + HashVal ^= cast(SubTy)->getNumElements(); + break; + case Type::VectorTyID: + HashVal ^= cast(SubTy)->getNumElements(); + break; + case Type::StructTyID: + HashVal ^= cast(SubTy)->getNumElements(); + break; + case Type::PointerTyID: + HashVal ^= cast(SubTy)->getAddressSpace(); + break; + } + } + return HashVal ? HashVal : 1; // Do not return zero unless opaque subty. +} //===----------------------------------------------------------------------===// // Derived Type Factory Functions //===----------------------------------------------------------------------===// -// TypeMap - Make sure that only one instance of a particular type may be -// created on any given run of the compiler... note that this involves updating -// our map if an abstract type gets refined somehow. -// namespace llvm { -template -class TypeMap { - std::map Map; - +class TypeMapBase { +protected: /// TypesByHash - Keep track of types by their structure hash value. Note /// that we only keep track of types that have cycles through themselves in /// this map. /// std::multimap TypesByHash; - friend void Type::clearAllTypeMaps(); - -private: - void clear(std::vector &DerivedTypes) { - for (typename std::map::iterator I = Map.begin(), - E = Map.end(); I != E; ++I) - DerivedTypes.push_back(I->second.get()); - TypesByHash.clear(); - Map.clear(); +public: + void RemoveFromTypesByHash(unsigned Hash, const Type *Ty) { + std::multimap::iterator I = + TypesByHash.lower_bound(Hash); + for (; I != TypesByHash.end() && I->first == Hash; ++I) { + if (I->second == Ty) { + TypesByHash.erase(I); + return; + } + } + + // This must be do to an opaque type that was resolved. Switch down to hash + // code of zero. + assert(Hash && "Didn't find type entry!"); + RemoveFromTypesByHash(0, Ty); } + + /// TypeBecameConcrete - When Ty gets a notification that TheType just became + /// concrete, drop uses and make Ty non-abstract if we should. + void TypeBecameConcrete(DerivedType *Ty, const DerivedType *TheType) { + // If the element just became concrete, remove 'ty' from the abstract + // type user list for the type. Do this for as many times as Ty uses + // OldType. + for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); + I != E; ++I) + if (I->get() == TheType) + TheType->removeAbstractTypeUser(Ty); + + // If the type is currently thought to be abstract, rescan all of our + // subtypes to see if the type has just become concrete! Note that this + // may send out notifications to AbstractTypeUsers that types become + // concrete. + if (Ty->isAbstract()) + Ty->PromoteAbstractToConcrete(); + } +}; +} + + +// TypeMap - Make sure that only one instance of a particular type may be +// created on any given run of the compiler... note that this involves updating +// our map if an abstract type gets refined somehow. +// +namespace llvm { +template +class TypeMap : public TypeMapBase { + std::map Map; public: typedef typename std::map::iterator iterator; ~TypeMap() { print("ON EXIT"); } @@ -718,29 +878,21 @@ public: TypesByHash.insert(std::make_pair(ValType::hashTypeStructure(Ty), Ty)); print("add"); } - - void RemoveFromTypesByHash(unsigned Hash, const Type *Ty) { - std::multimap::iterator I = - TypesByHash.lower_bound(Hash); - while (I->second != Ty) { - ++I; - assert(I != TypesByHash.end() && I->first == Hash); - } - TypesByHash.erase(I); - } - - /// finishRefinement - This method is called after we have updated an existing - /// type with its new components. We must now either merge the type away with + + /// RefineAbstractType - This method is called after we have merged a type + /// with another one. We must now either merge the type away with /// some other type or reinstall it in the map with it's new configuration. - /// The specified iterator tells us what the type USED to look like. - void finishRefinement(TypeClass *Ty, const DerivedType *OldType, + void RefineAbstractType(TypeClass *Ty, const DerivedType *OldType, const Type *NewType) { - assert((Ty->isAbstract() || !OldType->isAbstract()) && - "Refining a non-abstract type!"); #ifdef DEBUG_MERGE_TYPES - std::cerr << "refineAbstractTy(" << (void*)OldType << "[" << *OldType - << "], " << (void*)NewType << " [" << *NewType << "])\n"; + DOUT << "RefineAbstractType(" << (void*)OldType << "[" << *OldType + << "], " << (void*)NewType << " [" << *NewType << "])\n"; #endif + + // Otherwise, we are changing one subelement type into another. Clearly the + // OldType must have been abstract, making us abstract. + assert(Ty->isAbstract() && "Refining a non-abstract type!"); + assert(OldType != NewType); // Make a temporary type holder for the type so that it doesn't disappear on // us when we erase the entry from the map. @@ -748,33 +900,30 @@ public: // The old record is now out-of-date, because one of the children has been // updated. Remove the obsolete entry from the map. - Map.erase(ValType::get(Ty)); + unsigned NumErased = Map.erase(ValType::get(Ty)); + assert(NumErased && "Element not found!"); NumErased = NumErased; // Remember the structural hash for the type before we start hacking on it, // in case we need it later. unsigned OldTypeHash = ValType::hashTypeStructure(Ty); // Find the type element we are refining... and change it now! - for (unsigned i = 0, e = Ty->ContainedTys.size(); i != e; ++i) - if (Ty->ContainedTys[i] == OldType) { - Ty->ContainedTys[i].removeUserFromConcrete(); + for (unsigned i = 0, e = Ty->getNumContainedTypes(); i != e; ++i) + if (Ty->ContainedTys[i] == OldType) Ty->ContainedTys[i] = NewType; - } - - unsigned TypeHash = ValType::hashTypeStructure(Ty); - + unsigned NewTypeHash = ValType::hashTypeStructure(Ty); + // If there are no cycles going through this node, we can do a simple, // efficient lookup in the map, instead of an inefficient nasty linear // lookup. - if (!Ty->isAbstract() || !TypeHasCycleThroughItself(Ty)) { + if (!TypeHasCycleThroughItself(Ty)) { typename std::map::iterator I; bool Inserted; - ValType V = ValType::get(Ty); - tie(I, Inserted) = Map.insert(std::make_pair(V, Ty)); + tie(I, Inserted) = Map.insert(std::make_pair(ValType::get(Ty), Ty)); if (!Inserted) { // Refined to a different type altogether? - RemoveFromTypesByHash(TypeHash, Ty); + RemoveFromTypesByHash(OldTypeHash, Ty); // We already have this type in the table. Get rid of the newly refined // type. @@ -782,66 +931,72 @@ public: Ty->refineAbstractTypeTo(NewTy); return; } - } else { // Now we check to see if there is an existing entry in the table which is // structurally identical to the newly refined type. If so, this type // gets refined to the pre-existing type. // std::multimap::iterator I, E, Entry; - tie(I, E) = TypesByHash.equal_range(OldTypeHash); + tie(I, E) = TypesByHash.equal_range(NewTypeHash); Entry = E; for (; I != E; ++I) { - if (I->second != Ty) { + if (I->second == Ty) { + // Remember the position of the old type if we see it in our scan. + Entry = I; + } else { if (TypesEqual(Ty, I->second)) { - assert(Ty->isAbstract() && "Replacing a non-abstract type?"); TypeClass *NewTy = cast((Type*)I->second.get()); - if (Entry == E) { - // Find the location of Ty in the TypesByHash structure. - while (I->second != Ty) { - ++I; - assert(I != E && "Structure doesn't contain type??"); + // Remove the old entry form TypesByHash. If the hash values differ + // now, remove it from the old place. Otherwise, continue scanning + // withing this hashcode to reduce work. + if (NewTypeHash != OldTypeHash) { + RemoveFromTypesByHash(OldTypeHash, Ty); + } else { + if (Entry == E) { + // Find the location of Ty in the TypesByHash structure if we + // haven't seen it already. + while (I->second != Ty) { + ++I; + assert(I != E && "Structure doesn't contain type??"); + } + Entry = I; } - Entry = I; + TypesByHash.erase(Entry); } - - TypesByHash.erase(Entry); Ty->refineAbstractTypeTo(NewTy); return; } - } else { - // Remember the position of - Entry = I; } } - // If there is no existing type of the same structure, we reinsert an // updated record into the map. Map.insert(std::make_pair(ValType::get(Ty), Ty)); } // If the hash codes differ, update TypesByHash - if (TypeHash != OldTypeHash) { + if (NewTypeHash != OldTypeHash) { RemoveFromTypesByHash(OldTypeHash, Ty); - TypesByHash.insert(std::make_pair(TypeHash, Ty)); + TypesByHash.insert(std::make_pair(NewTypeHash, Ty)); } - + // If the type is currently thought to be abstract, rescan all of our - // subtypes to see if the type has just become concrete! + // subtypes to see if the type has just become concrete! Note that this + // may send out notifications to AbstractTypeUsers that types become + // concrete. if (Ty->isAbstract()) Ty->PromoteAbstractToConcrete(); } void print(const char *Arg) const { #ifdef DEBUG_MERGE_TYPES - std::cerr << "TypeMap<>::" << Arg << " table contents:\n"; + DOUT << "TypeMap<>::" << Arg << " table contents:\n"; unsigned i = 0; for (typename std::map::const_iterator I = Map.begin(), E = Map.end(); I != E; ++I) - std::cerr << " " << (++i) << ". " << (void*)I->second.get() << " " - << *I->second.get() << "\n"; + DOUT << " " << (++i) << ". " << (void*)I->second.get() << " " + << *I->second.get() << "\n"; #endif } @@ -854,6 +1009,69 @@ public: // Function Type Factory and Value Class... // +//===----------------------------------------------------------------------===// +// Integer Type Factory... +// +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 > IntegerTypes; + +const IntegerType *IntegerType::get(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::Int1Ty); + case 8: return cast(Type::Int8Ty); + case 16: return cast(Type::Int16Ty); + case 32: return cast(Type::Int32Ty); + case 64: return cast(Type::Int64Ty); + default: + break; + } + + IntegerValType IVT(NumBits); + IntegerType *ITy = IntegerTypes->get(IVT); + if (ITy) return ITy; // Found a match, return it! + + // Value not found. Derive a new type! + 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()); +} + // FunctionValType - Define a class to hold the key that goes into the TypeMap // namespace llvm { @@ -863,36 +1081,29 @@ class FunctionValType { bool isVarArg; public: FunctionValType(const Type *ret, const std::vector &args, - bool IVA) : RetTy(ret), isVarArg(IVA) { - for (unsigned i = 0; i < args.size(); ++i) - ArgTypes.push_back(args[i]); - } + bool isVA) : RetTy(ret), ArgTypes(args), isVarArg(isVA) {} static FunctionValType get(const FunctionType *FT); static unsigned hashTypeStructure(const FunctionType *FT) { - return FT->getNumParams()*2+FT->isVarArg(); - } - - // Subclass should override this... to update self as usual - void doRefinement(const DerivedType *OldType, const Type *NewType) { - if (RetTy == OldType) RetTy = NewType; - for (unsigned i = 0, e = ArgTypes.size(); i != e; ++i) - if (ArgTypes[i] == OldType) ArgTypes[i] = NewType; + 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; - return ArgTypes == MTV.ArgTypes && isVarArg < MTV.isVarArg; + if (ArgTypes > MTV.ArgTypes) return false; + return false; } }; } // Define the actual map itself now... -static TypeMap FunctionTypes; +static ManagedStatic > FunctionTypes; FunctionValType FunctionValType::get(const FunctionType *FT) { // Build up a FunctionValType @@ -909,15 +1120,19 @@ FunctionType *FunctionType::get(const Type *ReturnType, const std::vector &Params, bool isVarArg) { FunctionValType VT(ReturnType, Params, isVarArg); - FunctionType *MT = FunctionTypes.get(VT); - if (MT) return MT; + FunctionType *FT = FunctionTypes->get(VT); + if (FT) + return FT; - FunctionTypes.add(VT, MT = new FunctionType(ReturnType, Params, isVarArg)); + FT = (FunctionType*) new char[sizeof(FunctionType) + + sizeof(PATypeHandle)*(Params.size()+1)]; + new (FT) FunctionType(ReturnType, Params, isVarArg); + FunctionTypes->add(VT, FT); #ifdef DEBUG_MERGE_TYPES - std::cerr << "Derived new type: " << MT << "\n"; + DOUT << "Derived new type: " << FT << "\n"; #endif - return MT; + return FT; } //===----------------------------------------------------------------------===// @@ -938,83 +1153,71 @@ public: return (unsigned)AT->getNumElements(); } - // Subclass should override this... to update self as usual - void doRefinement(const DerivedType *OldType, const Type *NewType) { - assert(ValTy == OldType); - ValTy = NewType; - } - inline bool operator<(const ArrayValType &MTV) const { if (Size < MTV.Size) return true; return Size == MTV.Size && ValTy < MTV.ValTy; } }; } -static TypeMap ArrayTypes; +static ManagedStatic > 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); + ArrayType *AT = ArrayTypes->get(AVT); if (AT) return AT; // Found a match, return it! // Value not found. Derive a new type! - ArrayTypes.add(AVT, AT = new ArrayType(ElementType, NumElements)); + ArrayTypes->add(AVT, AT = new ArrayType(ElementType, NumElements)); #ifdef DEBUG_MERGE_TYPES - std::cerr << "Derived new type: " << *AT << "\n"; + DOUT << "Derived new type: " << *AT << "\n"; #endif return AT; } //===----------------------------------------------------------------------===// -// Packed Type Factory... +// Vector Type Factory... // namespace llvm { -class PackedValType { +class VectorValType { const Type *ValTy; unsigned Size; public: - PackedValType(const Type *val, int sz) : ValTy(val), Size(sz) {} + VectorValType(const Type *val, int sz) : ValTy(val), Size(sz) {} - static PackedValType get(const PackedType *PT) { - return PackedValType(PT->getElementType(), PT->getNumElements()); + static VectorValType get(const VectorType *PT) { + return VectorValType(PT->getElementType(), PT->getNumElements()); } - static unsigned hashTypeStructure(const PackedType *PT) { + static unsigned hashTypeStructure(const VectorType *PT) { return PT->getNumElements(); } - // Subclass should override this... to update self as usual - void doRefinement(const DerivedType *OldType, const Type *NewType) { - assert(ValTy == OldType); - ValTy = NewType; - } - - inline bool operator<(const PackedValType &MTV) const { + inline bool operator<(const VectorValType &MTV) const { if (Size < MTV.Size) return true; return Size == MTV.Size && ValTy < MTV.ValTy; } }; } -static TypeMap PackedTypes; +static ManagedStatic > VectorTypes; -PackedType *PackedType::get(const Type *ElementType, unsigned NumElements) { - assert(ElementType && "Can't get packed of null types!"); +VectorType *VectorType::get(const Type *ElementType, unsigned NumElements) { + assert(ElementType && "Can't get vector of null types!"); - PackedValType PVT(ElementType, NumElements); - PackedType *PT = PackedTypes.get(PVT); + VectorValType PVT(ElementType, NumElements); + VectorType *PT = VectorTypes->get(PVT); if (PT) return PT; // Found a match, return it! // Value not found. Derive a new type! - PackedTypes.add(PVT, PT = new PackedType(ElementType, NumElements)); + VectorTypes->add(PVT, PT = new VectorType(ElementType, NumElements)); #ifdef DEBUG_MERGE_TYPES - std::cerr << "Derived new type: " << *PT << "\n"; + DOUT << "Derived new type: " << *PT << "\n"; #endif return PT; } @@ -1028,8 +1231,10 @@ namespace llvm { // class StructValType { std::vector ElTypes; + bool packed; public: - StructValType(const std::vector &args) : ElTypes(args) {} + StructValType(const std::vector &args, bool isPacked) + : ElTypes(args), packed(isPacked) {} static StructValType get(const StructType *ST) { std::vector ElTypes; @@ -1037,41 +1242,52 @@ public: for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) ElTypes.push_back(ST->getElementType(i)); - return StructValType(ElTypes); + return StructValType(ElTypes, ST->isPacked()); } static unsigned hashTypeStructure(const StructType *ST) { return ST->getNumElements(); } - // Subclass should override this... to update self as usual - void doRefinement(const DerivedType *OldType, const Type *NewType) { - for (unsigned i = 0; i < ElTypes.size(); ++i) - if (ElTypes[i] == OldType) ElTypes[i] = NewType; - } - inline bool operator<(const StructValType &STV) const { - return ElTypes < STV.ElTypes; + if (ElTypes < STV.ElTypes) return true; + else if (ElTypes > STV.ElTypes) return false; + else return (int)packed < (int)STV.packed; } }; } -static TypeMap StructTypes; +static ManagedStatic > StructTypes; -StructType *StructType::get(const std::vector &ETypes) { - StructValType STV(ETypes); - StructType *ST = StructTypes.get(STV); +StructType *StructType::get(const std::vector &ETypes, + bool isPacked) { + StructValType STV(ETypes, isPacked); + StructType *ST = StructTypes->get(STV); if (ST) return ST; // Value not found. Derive a new type! - StructTypes.add(STV, ST = new StructType(ETypes)); + ST = (StructType*) new char[sizeof(StructType) + + sizeof(PATypeHandle) * ETypes.size()]; + new (ST) StructType(ETypes, isPacked); + StructTypes->add(STV, ST); #ifdef DEBUG_MERGE_TYPES - std::cerr << "Derived new type: " << *ST << "\n"; + DOUT << "Derived new type: " << *ST << "\n"; #endif return ST; } +StructType *StructType::get(const Type *type, ...) { + va_list ap; + std::vector StructFields; + va_start(ap, type); + while (type) { + StructFields.push_back(type); + type = va_arg(ap, llvm::Type*); + } + return llvm::StructType::get(StructFields); +} + //===----------------------------------------------------------------------===// @@ -1083,52 +1299,46 @@ StructType *StructType::get(const std::vector &ETypes) { namespace llvm { class PointerValType { const Type *ValTy; + unsigned AddressSpace; public: - PointerValType(const Type *val) : ValTy(val) {} + PointerValType(const Type *val, unsigned as) : ValTy(val), AddressSpace(as) {} static PointerValType get(const PointerType *PT) { - return PointerValType(PT->getElementType()); + return PointerValType(PT->getElementType(), PT->getAddressSpace()); } static unsigned hashTypeStructure(const PointerType *PT) { - return 0; - } - - // Subclass should override this... to update self as usual - void doRefinement(const DerivedType *OldType, const Type *NewType) { - assert(ValTy == OldType); - ValTy = NewType; + return getSubElementHash(PT); } bool operator<(const PointerValType &MTV) const { - return ValTy < MTV.ValTy; + if (AddressSpace < MTV.AddressSpace) return true; + return AddressSpace == MTV.AddressSpace && ValTy < MTV.ValTy; } }; } -static TypeMap PointerTypes; +static ManagedStatic > PointerTypes; -PointerType *PointerType::get(const Type *ValueType) { +PointerType *PointerType::get(const Type *ValueType, unsigned AddressSpace) { assert(ValueType && "Can't get a pointer to type!"); - // FIXME: The sparc backend makes void pointers, which is horribly broken. - // "Fix" it, then reenable this assertion. - //assert(ValueType != Type::VoidTy && - // "Pointer to void is not valid, use sbyte* instead!"); - PointerValType PVT(ValueType); + 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); + PointerType *PT = PointerTypes->get(PVT); if (PT) return PT; // Value not found. Derive a new type! - PointerTypes.add(PVT, PT = new PointerType(ValueType)); + PointerTypes->add(PVT, PT = new PointerType(ValueType, AddressSpace)); #ifdef DEBUG_MERGE_TYPES - std::cerr << "Derived new type: " << *PT << "\n"; + DOUT << "Derived new type: " << *PT << "\n"; #endif return PT; } - //===----------------------------------------------------------------------===// // Derived Type Refinement Functions //===----------------------------------------------------------------------===// @@ -1138,7 +1348,7 @@ PointerType *PointerType::get(const Type *ValueType) { // 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 DerivedType::removeAbstractTypeUser(AbstractTypeUser *U) const { +void Type::removeAbstractTypeUser(AbstractTypeUser *U) const { // 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. @@ -1153,21 +1363,20 @@ void DerivedType::removeAbstractTypeUser(AbstractTypeUser *U) const { AbstractTypeUsers.erase(AbstractTypeUsers.begin()+i); #ifdef DEBUG_MERGE_TYPES - std::cerr << " remAbstractTypeUser[" << (void*)this << ", " - << *this << "][" << i << "] User = " << U << "\n"; + DOUT << " remAbstractTypeUser[" << (void*)this << ", " + << *this << "][" << i << "] User = " << U << "\n"; #endif if (AbstractTypeUsers.empty() && getRefCount() == 0 && isAbstract()) { #ifdef DEBUG_MERGE_TYPES - std::cerr << "DELETEing unused abstract type: <" << *this - << ">[" << (void*)this << "]" << "\n"; + DOUT << "DELETEing unused abstract type: <" << *this + << ">[" << (void*)this << "]" << "\n"; #endif - delete this; // No users of this abstract type! + this->destroy(); } } - -// refineAbstractTypeTo - This function is used to when it is discovered that +// refineAbstractTypeTo - 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. @@ -1178,12 +1387,12 @@ void DerivedType::refineAbstractTypeTo(const Type *NewType) { assert(ForwardType == 0 && "This type has already been refined!"); // The descriptions may be out of date. Conservatively clear them all! - AbstractTypeDescriptions.clear(); + AbstractTypeDescriptions->clear(); #ifdef DEBUG_MERGE_TYPES - std::cerr << "REFINING abstract type [" << (void*)this << " " - << *this << "] to [" << (void*)NewType << " " - << *NewType << "]!\n"; + DOUT << "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 @@ -1217,12 +1426,12 @@ void DerivedType::refineAbstractTypeTo(const Type *NewType) { while (!AbstractTypeUsers.empty() && NewTy != this) { AbstractTypeUser *User = AbstractTypeUsers.back(); - unsigned OldSize = AbstractTypeUsers.size(); + unsigned OldSize = AbstractTypeUsers.size(); OldSize=OldSize; #ifdef DEBUG_MERGE_TYPES - std::cerr << " REFINING user " << OldSize-1 << "[" << (void*)User - << "] of abstract type [" << (void*)this << " " - << *this << "] to [" << (void*)NewTy.get() << " " - << *NewTy << "]!\n"; + DOUT << " REFINING user " << OldSize-1 << "[" << (void*)User + << "] of abstract type [" << (void*)this << " " + << *this << "] to [" << (void*)NewTy.get() << " " + << *NewTy << "]!\n"; #endif User->refineAbstractType(this, NewTy); @@ -1241,10 +1450,10 @@ void DerivedType::refineAbstractTypeTo(const Type *NewType) { // void DerivedType::notifyUsesThatTypeBecameConcrete() { #ifdef DEBUG_MERGE_TYPES - std::cerr << "typeIsREFINED type: " << (void*)this << " " << *this << "\n"; + DOUT << "typeIsREFINED type: " << (void*)this << " " << *this << "\n"; #endif - unsigned OldSize = AbstractTypeUsers.size(); + unsigned OldSize = AbstractTypeUsers.size(); OldSize=OldSize; while (!AbstractTypeUsers.empty()) { AbstractTypeUser *ATU = AbstractTypeUsers.back(); ATU->typeBecameConcrete(this); @@ -1254,20 +1463,17 @@ void DerivedType::notifyUsesThatTypeBecameConcrete() { } } - - - // 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) { - FunctionTypes.finishRefinement(this, OldType, NewType); + FunctionTypes->RefineAbstractType(this, OldType, NewType); } void FunctionType::typeBecameConcrete(const DerivedType *AbsTy) { - refineAbstractType(AbsTy, AbsTy); + FunctionTypes->TypeBecameConcrete(this, AbsTy); } @@ -1277,24 +1483,24 @@ void FunctionType::typeBecameConcrete(const DerivedType *AbsTy) { // void ArrayType::refineAbstractType(const DerivedType *OldType, const Type *NewType) { - ArrayTypes.finishRefinement(this, OldType, NewType); + ArrayTypes->RefineAbstractType(this, OldType, NewType); } void ArrayType::typeBecameConcrete(const DerivedType *AbsTy) { - refineAbstractType(AbsTy, AbsTy); + ArrayTypes->TypeBecameConcrete(this, AbsTy); } // 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 PackedType::refineAbstractType(const DerivedType *OldType, +void VectorType::refineAbstractType(const DerivedType *OldType, const Type *NewType) { - PackedTypes.finishRefinement(this, OldType, NewType); + VectorTypes->RefineAbstractType(this, OldType, NewType); } -void PackedType::typeBecameConcrete(const DerivedType *AbsTy) { - refineAbstractType(AbsTy, AbsTy); +void VectorType::typeBecameConcrete(const DerivedType *AbsTy) { + VectorTypes->TypeBecameConcrete(this, AbsTy); } // refineAbstractType - Called when a contained type is found to be more @@ -1303,11 +1509,11 @@ void PackedType::typeBecameConcrete(const DerivedType *AbsTy) { // void StructType::refineAbstractType(const DerivedType *OldType, const Type *NewType) { - StructTypes.finishRefinement(this, OldType, NewType); + StructTypes->RefineAbstractType(this, OldType, NewType); } void StructType::typeBecameConcrete(const DerivedType *AbsTy) { - refineAbstractType(AbsTy, AbsTy); + StructTypes->TypeBecameConcrete(this, AbsTy); } // refineAbstractType - Called when a contained type is found to be more @@ -1316,24 +1522,17 @@ void StructType::typeBecameConcrete(const DerivedType *AbsTy) { // void PointerType::refineAbstractType(const DerivedType *OldType, const Type *NewType) { - PointerTypes.finishRefinement(this, OldType, NewType); + PointerTypes->RefineAbstractType(this, OldType, NewType); } void PointerType::typeBecameConcrete(const DerivedType *AbsTy) { - refineAbstractType(AbsTy, AbsTy); + PointerTypes->TypeBecameConcrete(this, AbsTy); } bool SequentialType::indexValid(const Value *V) const { - const Type *Ty = V->getType(); - switch (Ty->getTypeID()) { - case Type::IntTyID: - case Type::UIntTyID: - case Type::LongTyID: - case Type::ULongTyID: - return true; - default: - return false; - } + if (const IntegerType *IT = dyn_cast(V->getType())) + return IT->getBitWidth() == 32 || IT->getBitWidth() == 64; + return false; } namespace llvm { @@ -1350,26 +1549,3 @@ std::ostream &operator<<(std::ostream &OS, const Type &T) { return OS; } } - -/// clearAllTypeMaps - This method frees all internal memory used by the -/// type subsystem, which can be used in environments where this memory is -/// otherwise reported as a leak. -void Type::clearAllTypeMaps() { - std::vector DerivedTypes; - - FunctionTypes.clear(DerivedTypes); - PointerTypes.clear(DerivedTypes); - StructTypes.clear(DerivedTypes); - ArrayTypes.clear(DerivedTypes); - PackedTypes.clear(DerivedTypes); - - for(std::vector::iterator I = DerivedTypes.begin(), - E = DerivedTypes.end(); I != E; ++I) - (*I)->ContainedTys.clear(); - for(std::vector::iterator I = DerivedTypes.begin(), - E = DerivedTypes.end(); I != E; ++I) - delete *I; - DerivedTypes.clear(); -} - -// vim: sw=2