X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FType.cpp;h=3a9ea582f112efb088d357bd55f48f55f133986e;hb=ebcba612b537f45a033ccd9a60bee0c45e2e2ded;hp=7ccf35a9736cf1f704d817dea60de7324737e2f9;hpb=2e1c1964706c5202305f6a7086865ff3559920df;p=oota-llvm.git diff --git a/lib/VMCore/Type.cpp b/lib/VMCore/Type.cpp index 7ccf35a9736..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,9 +11,7 @@ // //===----------------------------------------------------------------------===// -#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" @@ -22,15 +20,16 @@ #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() {} @@ -63,144 +62,128 @@ static ManagedStatic > AbstractTypeDescriptions; -Type::Type(const char *Name, TypeID id) - : ID(id), Abstract(false), RefCount(0), ForwardType(0) { - assert(Name && Name[0] && "Should use other ctor if no name!"); - (*ConcreteTypeDescriptions)[this] = Name; -} +/// 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; + } + // 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; } } +const Type *Type::getVAArgsPromotedType() const { + if (ID == IntegerTyID && getSubclassData() < 32) + return Type::Int32Ty; + else if (ID == FloatTyID) + return Type::DoubleTy; + else + 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(); +} + /// 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) return true; - if (ID != Type::PackedTyID) return false; + 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(); + return cast(this)->getElementType()->isFloatingPoint(); } - -// isLosslesslyConvertibleTo - Return true if this type can be converted to +// canLosslesllyBitCastTo - 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; - - // Packed type conversions are always bitwise. - if (isa(this) && isa(Ty)) +bool Type::canLosslesslyBitCastTo(const Type *Ty) const { + // Identity cast means no change so return true + 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 - } -} - -/// 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; - } -} + // They are not convertible unless they are at least first class types + if (!this->isFirstClassType() || !Ty->isFirstClassType()) + return false; -/// 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; - } -} - - -// 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. -// -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; - } + // 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; } } @@ -209,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; } @@ -274,7 +262,23 @@ static std::string getTypeDescription(const Type *Ty, if (!Ty->isAbstract()) { // Base case for the recursion std::map::iterator I = ConcreteTypeDescriptions->find(Ty); - if (I != ConcreteTypeDescriptions->end()) return I->second; + 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... @@ -293,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); @@ -311,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()) @@ -319,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: { @@ -334,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 "; @@ -374,72 +393,94 @@ const std::string &Type::getDescription() const { bool StructType::indexValid(const Value *V) const { - // Structure indexes require unsigned integer constants. - if (V->getType() == Type::UIntTy) + // Structure indexes require 32-bit integer constants. + if (V->getType() == Type::Int32Ty) if (const ConstantInt *CU = dyn_cast(V)) - return CU->getZExtValue() < ContainedTys.size(); + 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)->getZExtValue(); - return ContainedTys[Idx]; + return getTypeAtIndex(Idx); } +const Type *StructType::getTypeAtIndex(unsigned Idx) const { + assert(indexValid(Idx) && "Invalid structure index!"); + return ContainedTys[Idx]; +} //===----------------------------------------------------------------------===// // Primitive 'Type' data //===----------------------------------------------------------------------===// -#define DeclarePrimType(TY, Str) \ - namespace { \ - struct VISIBILITY_HIDDEN TY##Type : public Type { \ - TY##Type() : Type(Str, Type::TY##TyID) {} \ - }; \ - } \ - static ManagedStatic The##TY##Ty; \ - Type *Type::TY##Ty = &*The##TY##Ty - -DeclarePrimType(Void, "void"); -DeclarePrimType(Bool, "bool"); -DeclarePrimType(SByte, "sbyte"); -DeclarePrimType(UByte, "ubyte"); -DeclarePrimType(Short, "short"); -DeclarePrimType(UShort, "ushort"); -DeclarePrimType(Int, "int"); -DeclarePrimType(UInt, "uint"); -DeclarePrimType(Long, "long"); -DeclarePrimType(ULong, "ulong"); -DeclarePrimType(Float, "float"); -DeclarePrimType(Double, "double"); -DeclarePrimType(Label, "label"); -#undef DeclarePrimType +const Type *Type::VoidTy = new Type(Type::VoidTyID); +const Type *Type::FloatTy = new Type(Type::FloatTyID); +const Type *Type::DoubleTy = new Type(Type::DoubleTyID); +const Type *Type::X86_FP80Ty = new Type(Type::X86_FP80TyID); +const Type *Type::FP128Ty = new Type(Type::FP128TyID); +const Type *Type::PPC_FP128Ty = new Type(Type::PPC_FP128TyID); +const Type *Type::LabelTy = new Type(Type::LabelTyID); + +namespace { + struct BuiltinIntegerType : public IntegerType { + BuiltinIntegerType(unsigned W) : IntegerType(W) {} + }; +} +const IntegerType *Type::Int1Ty = new BuiltinIntegerType(1); +const IntegerType *Type::Int8Ty = new BuiltinIntegerType(8); +const IntegerType *Type::Int16Ty = new BuiltinIntegerType(16); +const IntegerType *Type::Int32Ty = new BuiltinIntegerType(32); +const IntegerType *Type::Int64Ty = new BuiltinIntegerType(64); //===----------------------------------------------------------------------===// // 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(); } @@ -447,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(); } @@ -469,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()); } @@ -487,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 } @@ -495,22 +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()) { + 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 intty's. It doesn't matter what we + // 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 = ContainedTys.size(); i != e; ++i) - ContainedTys[i] = Type::IntTy; + 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 @@ -521,6 +569,8 @@ struct TypePromotionGraph { TypePromotionGraph(Type *T) : Ty(T) {} }; +} + namespace llvm { template <> struct GraphTraits { typedef Type NodeType; @@ -617,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; @@ -631,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)) { @@ -641,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!"); @@ -661,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(), @@ -676,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(), @@ -692,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(); @@ -722,6 +778,9 @@ static unsigned getSubElementHash(const Type *Ty) { 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(); @@ -729,12 +788,15 @@ static unsigned getSubElementHash(const Type *Ty) { case Type::ArrayTyID: HashVal ^= cast(SubTy)->getNumElements(); break; - case Type::PackedTyID: - HashVal ^= cast(SubTy)->getNumElements(); + 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. @@ -817,22 +879,14 @@ public: print("add"); } - 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(); - } - - /// RefineAbstractType - This method is called after we have merged a type + /// 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. void RefineAbstractType(TypeClass *Ty, const DerivedType *OldType, const Type *NewType) { #ifdef DEBUG_MERGE_TYPES - std::cerr << "RefineAbstractType(" << (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 @@ -847,14 +901,14 @@ public: // The old record is now out-of-date, because one of the children has been // updated. Remove the obsolete entry from the map. unsigned NumErased = Map.erase(ValType::get(Ty)); - assert(NumErased && "Element not found!"); + 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) + for (unsigned i = 0, e = Ty->getNumContainedTypes(); i != e; ++i) if (Ty->ContainedTys[i] == OldType) Ty->ContainedTys[i] = NewType; unsigned NewTypeHash = ValType::hashTypeStructure(Ty); @@ -937,12 +991,12 @@ public: 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 } @@ -955,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 { @@ -964,30 +1081,23 @@ 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; } }; } @@ -1010,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; } //===----------------------------------------------------------------------===// @@ -1039,12 +1153,6 @@ 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; @@ -1065,58 +1173,51 @@ ArrayType *ArrayType::get(const Type *ElementType, uint64_t 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 ManagedStatic > PackedTypes; +static ManagedStatic > VectorTypes; -PackedType *PackedType::get(const Type *ElementType, unsigned NumElements) { - assert(ElementType && "Can't get packed of null types!"); - assert(isPowerOf2_32(NumElements) && "Vector length should be a power of 2!"); +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; } @@ -1130,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; @@ -1139,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 ManagedStatic > StructTypes; -StructType *StructType::get(const std::vector &ETypes) { - StructValType STV(ETypes); +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); +} + //===----------------------------------------------------------------------===// @@ -1185,46 +1299,42 @@ 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 getSubElementHash(PT); } - // Subclass should override this... to update self as usual - void doRefinement(const DerivedType *OldType, const Type *NewType) { - assert(ValTy == OldType); - ValTy = NewType; - } - bool operator<(const PointerValType &MTV) const { - return ValTy < MTV.ValTy; + if (AddressSpace < MTV.AddressSpace) return true; + return AddressSpace == MTV.AddressSpace && ValTy < MTV.ValTy; } }; } 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!"); 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); + PointerValType PVT(ValueType, AddressSpace); 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; } @@ -1253,20 +1363,19 @@ void Type::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 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 @@ -1281,9 +1390,9 @@ void DerivedType::refineAbstractTypeTo(const Type *NewType) { 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 @@ -1317,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); @@ -1341,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); @@ -1385,13 +1494,13 @@ void ArrayType::typeBecameConcrete(const DerivedType *AbsTy) { // 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->RefineAbstractType(this, OldType, NewType); + VectorTypes->RefineAbstractType(this, OldType, NewType); } -void PackedType::typeBecameConcrete(const DerivedType *AbsTy) { - PackedTypes->TypeBecameConcrete(this, AbsTy); +void VectorType::typeBecameConcrete(const DerivedType *AbsTy) { + VectorTypes->TypeBecameConcrete(this, AbsTy); } // refineAbstractType - Called when a contained type is found to be more @@ -1421,16 +1530,9 @@ void PointerType::typeBecameConcrete(const DerivedType *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 {