X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FType.cpp;h=ba8830912cae910bdf3efbdf5bab21ba019d240d;hb=d358cfc1bf2292922672ac35d4e897fe07de4785;hp=686527315fbc758cc9d115033f60be211b8f727e;hpb=950273b3e750d40d8bc7a7971902829615e3ce24;p=oota-llvm.git diff --git a/lib/VMCore/Type.cpp b/lib/VMCore/Type.cpp index 686527315fb..ba8830912ca 100644 --- a/lib/VMCore/Type.cpp +++ b/lib/VMCore/Type.cpp @@ -1,58 +1,56 @@ -//===-- Type.cpp - Implement the Type class ----------------------*- C++ -*--=// +//===-- Type.cpp - Implement the Type class -------------------------------===// +// +// 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 implements the Type class for the VMCore library. // //===----------------------------------------------------------------------===// +#include "llvm/AbstractTypeUser.h" #include "llvm/DerivedTypes.h" #include "llvm/SymbolTable.h" #include "llvm/Constants.h" -#include "Support/StringExtras.h" -#include "Support/STLExtras.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 +#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 cannonical version of a type. +// a single canonical version of a type. // //#define DEBUG_MERGE_TYPES 1 +AbstractTypeUser::~AbstractTypeUser() {} //===----------------------------------------------------------------------===// // Type Class Implementation //===----------------------------------------------------------------------===// -static unsigned CurUID = 0; -static std::vector UIDMappings; - -void PATypeHolder::dump() const { - std::cerr << "PATypeHolder(" << (void*)this << ")\n"; -} - - -Type::Type(const std::string &name, PrimitiveID id) - : Value(Type::TypeTy, Value::TypeVal) { - setDescription(name); - ID = id; - Abstract = Recursive = false; - UID = CurUID++; // Assign types UID's as they are created - UIDMappings.push_back(this); -} - -void Type::setName(const std::string &Name, SymbolTable *ST) { - assert(ST && "Type::setName - Must provide symbol table argument!"); - - if (Name.size()) ST->insert(Name, this); +// Concrete/Abstract TypeDescriptions - We lazily calculate type descriptions +// 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; + +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; } -const Type *Type::getUniqueIDType(unsigned UID) { - assert(UID < UIDMappings.size() && - "Type::getPrimitiveType: UID out of range!"); - return UIDMappings[UID]; -} - -const Type *Type::getPrimitiveType(PrimitiveID IDNumber) { +const Type *Type::getPrimitiveType(TypeID IDNumber) { switch (IDNumber) { case VoidTyID : return VoidTy; case BoolTyID : return BoolTy; @@ -66,7 +64,6 @@ const Type *Type::getPrimitiveType(PrimitiveID IDNumber) { case LongTyID : return LongTy; case FloatTyID : return FloatTy; case DoubleTyID: return DoubleTy; - case TypeTyID : return TypeTy; case LabelTyID : return LabelTy; default: return 0; @@ -81,117 +78,307 @@ bool Type::isLosslesslyConvertibleTo(const Type *Ty) const { if ((!isPrimitiveType() && !isa(this)) || (!isa(Ty) && !Ty->isPrimitiveType())) return false; - if (getPrimitiveID() == Ty->getPrimitiveID()) + 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 (getPrimitiveID()) { + 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: - case Type::LongTyID: - case Type::PointerTyID: - return Ty == Type::ULongTy || Ty == Type::LongTy || isa(Ty); + 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 } } -// getPrimitiveSize - Return the basic size of this type if it is a primative -// type. These are fixed by LLVM and are not target dependant. This will +/// 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; + } +} + +/// 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 (getPrimitiveID()) { -#define HANDLE_PRIM_TYPE(TY,SIZE) case TY##TyID: return SIZE; -#include "llvm/Type.def" + 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; + } +} + +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::DoubleTyID: return 64; default: return 0; } } +/// isSizedDerivedType - Derived types like structures and arrays are sized +/// 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 (const ArrayType *ATy = dyn_cast(this)) + return ATy->getElementType()->isSized(); -bool StructType::indexValid(const Value *V) const { - if (!isa(V)) return false; - if (V->getType() != Type::UByteTy) return false; - unsigned Idx = cast(V)->getValue(); - return Idx < ETypes.size(); + if (const PackedType *PTy = dyn_cast(this)) + return PTy->getElementType()->isSized(); + + 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; + + return true; } -// 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(isa(V) && "Structure index must be a constant!!"); - assert(V->getType() == Type::UByteTy && "Structure index must be ubyte!"); - unsigned Idx = cast(V)->getValue(); - assert(Idx < ETypes.size() && "Structure index out of range!"); - assert(indexValid(V) && "Invalid structure index!"); // Duplicate check +/// getForwardedTypeInternal - This method is used to implement the union-find +/// algorithm for when a type is being forwarded to another type. +const Type *Type::getForwardedTypeInternal() const { + assert(ForwardType && "This type is not being forwarded to another type!"); + + // Check to see if the forwarded type has been forwarded on. If so, collapse + // the forwarding links. + const Type *RealForwardedType = ForwardType->getForwardedType(); + if (!RealForwardedType) + return ForwardType; // No it's not forwarded again + + // Yes, it is forwarded again. First thing, add the reference to the new + // forward type. + if (RealForwardedType->isAbstract()) + cast(RealForwardedType)->addRef(); + + // Now drop the old reference. This could cause ForwardType to get deleted. + cast(ForwardType)->dropRef(); + + // Return the updated type. + ForwardType = RealForwardedType; + return ForwardType; +} - return ETypes[Idx]; +void Type::refineAbstractType(const DerivedType *OldTy, const Type *NewTy) { + abort(); +} +void Type::typeBecameConcrete(const DerivedType *AbsTy) { + abort(); } -//===----------------------------------------------------------------------===// -// Auxilliary classes -//===----------------------------------------------------------------------===// -// -// These classes are used to implement specialized behavior for each different -// type. +// getTypeDescription - This is a recursive function that walks a type hierarchy +// calculating the description for a type. // -struct SignedIntType : public Type { - SignedIntType(const std::string &Name, PrimitiveID id) : Type(Name, id) {} +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) + return I->second; + std::string Desc = "opaque"; + 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; + } - // isSigned - Return whether a numeric type is signed. - virtual bool isSigned() const { return 1; } + // Check to see if the Type is already on the stack... + unsigned Slot = 0, CurSize = TypeStack.size(); + while (Slot < CurSize && TypeStack[Slot] != Ty) ++Slot; // Scan for type - // isInteger - Equivalent to isSigned() || isUnsigned, but with only a single - // virtual function invocation. + // This is another base case for the recursion. In this case, we know + // that we have looped back to a type that we have previously visited. + // Generate the appropriate upreference to handle this. // - virtual bool isInteger() const { return 1; } -}; + if (Slot < CurSize) + return "\\" + utostr(CurSize-Slot); // Here's the upreference + + // Recursive case: derived types... + std::string Result; + TypeStack.push_back(Ty); // Add us to the stack.. + + switch (Ty->getTypeID()) { + case Type::FunctionTyID: { + const FunctionType *FTy = cast(Ty); + Result = getTypeDescription(FTy->getReturnType(), TypeStack) + " ("; + for (FunctionType::param_iterator I = FTy->param_begin(), + E = FTy->param_end(); I != E; ++I) { + if (I != FTy->param_begin()) + Result += ", "; + Result += getTypeDescription(*I, TypeStack); + } + if (FTy->isVarArg()) { + if (FTy->getNumParams()) Result += ", "; + Result += "..."; + } + Result += ")"; + break; + } + case Type::StructTyID: { + const StructType *STy = cast(Ty); + Result = "{ "; + for (StructType::element_iterator I = STy->element_begin(), + E = STy->element_end(); I != E; ++I) { + if (I != STy->element_begin()) + Result += ", "; + Result += getTypeDescription(*I, TypeStack); + } + Result += " }"; + break; + } + case Type::PointerTyID: { + const PointerType *PTy = cast(Ty); + Result = getTypeDescription(PTy->getElementType(), TypeStack) + " *"; + break; + } + case Type::ArrayTyID: { + const ArrayType *ATy = cast(Ty); + unsigned NumElements = ATy->getNumElements(); + Result = "["; + Result += utostr(NumElements) + " x "; + Result += getTypeDescription(ATy->getElementType(), TypeStack) + "]"; + break; + } + case Type::PackedTyID: { + const PackedType *PTy = cast(Ty); + unsigned NumElements = PTy->getNumElements(); + Result = "<"; + Result += utostr(NumElements) + " x "; + Result += getTypeDescription(PTy->getElementType(), TypeStack) + ">"; + break; + } + default: + Result = ""; + assert(0 && "Unhandled type in getTypeDescription!"); + } + + TypeStack.pop_back(); // Remove self from stack... -struct UnsignedIntType : public Type { - UnsignedIntType(const std::string &N, PrimitiveID id) : Type(N, id) {} + return Result; +} - // isUnsigned - Return whether a numeric type is signed. - virtual bool isUnsigned() const { return 1; } - // isInteger - Equivalent to isSigned() || isUnsigned, but with only a single - // virtual function invocation. - // - virtual bool isInteger() const { return 1; } -}; -struct OtherType : public Type { - OtherType(const std::string &N, PrimitiveID id) : Type(N, id) {} -}; +static const std::string &getOrCreateDesc(std::map&Map, + const Type *Ty) { + std::map::iterator I = Map.find(Ty); + if (I != Map.end()) return I->second; + + std::vector TypeStack; + std::string Result = getTypeDescription(Ty, TypeStack); + return Map[Ty] = Result; +} + + +const std::string &Type::getDescription() const { + if (isAbstract()) + return getOrCreateDesc(AbstractTypeDescriptions, this); + else + return getOrCreateDesc(ConcreteTypeDescriptions, this); +} -static struct TypeType : public Type { - TypeType() : Type("type", TypeTyID) {} -} TheTypeTy; // Implement the type that is global. + +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(); + return false; +} + +// 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]; +} //===----------------------------------------------------------------------===// // Static 'Type' data //===----------------------------------------------------------------------===// -static OtherType TheVoidTy ("void" , Type::VoidTyID); -static OtherType TheBoolTy ("bool" , Type::BoolTyID); -static SignedIntType TheSByteTy ("sbyte" , Type::SByteTyID); -static UnsignedIntType TheUByteTy ("ubyte" , Type::UByteTyID); -static SignedIntType TheShortTy ("short" , Type::ShortTyID); -static UnsignedIntType TheUShortTy("ushort", Type::UShortTyID); -static SignedIntType TheIntTy ("int" , Type::IntTyID); -static UnsignedIntType TheUIntTy ("uint" , Type::UIntTyID); -static SignedIntType TheLongTy ("long" , Type::LongTyID); -static UnsignedIntType TheULongTy ("ulong" , Type::ULongTyID); -static OtherType TheFloatTy ("float" , Type::FloatTyID); -static OtherType TheDoubleTy("double", Type::DoubleTyID); -static OtherType TheLabelTy ("label" , Type::LabelTyID); +namespace { + struct PrimType : public Type { + PrimType(const char *S, TypeID ID) : Type(S, ID) {} + }; +} + +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; @@ -205,7 +392,6 @@ Type *Type::LongTy = &TheLongTy; Type *Type::ULongTy = &TheULongTy; Type *Type::FloatTy = &TheFloatTy; Type *Type::DoubleTy = &TheDoubleTy; -Type *Type::TypeTy = &TheTypeTy; Type *Type::LabelTy = &TheLabelTy; @@ -214,153 +400,163 @@ Type *Type::LabelTy = &TheLabelTy; //===----------------------------------------------------------------------===// FunctionType::FunctionType(const Type *Result, - const std::vector &Params, - bool IsVarArgs) : DerivedType(FunctionTyID), - ResultType(PATypeHandle(Result, this)), - isVarArgs(IsVarArgs) { - ParamTys.reserve(Params.size()); - for (unsigned i = 0; i < Params.size(); ++i) - ParamTys.push_back(PATypeHandle(Params[i], this)); - - setDerivedTypeProperties(); + const std::vector &Params, + bool IsVarArgs) : DerivedType(FunctionTyID), + isVarArgs(IsVarArgs) { + assert((Result->isFirstClassType() || Result == Type::VoidTy || + isa(Result)) && + "LLVM functions cannot return aggregates"); + bool isAbstract = Result->isAbstract(); + ContainedTys.reserve(Params.size()+1); + ContainedTys.push_back(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)); + isAbstract |= Params[i]->isAbstract(); + } + + // Calculate whether or not this type is abstract + setAbstract(isAbstract); } StructType::StructType(const std::vector &Types) : CompositeType(StructTyID) { - ETypes.reserve(Types.size()); + ContainedTys.reserve(Types.size()); + bool isAbstract = false; for (unsigned i = 0; i < Types.size(); ++i) { - assert(Types[i] != Type::VoidTy && "Void type in method prototype!!"); - ETypes.push_back(PATypeHandle(Types[i], this)); + assert(Types[i] != Type::VoidTy && "Void type for structure field!!"); + ContainedTys.push_back(PATypeHandle(Types[i], this)); + isAbstract |= Types[i]->isAbstract(); } - setDerivedTypeProperties(); + + // Calculate whether or not this type is abstract + setAbstract(isAbstract); } -ArrayType::ArrayType(const Type *ElType, unsigned NumEl) +ArrayType::ArrayType(const Type *ElType, uint64_t NumEl) : SequentialType(ArrayTyID, ElType) { NumElements = NumEl; - setDerivedTypeProperties(); + + // Calculate whether or not this type is abstract + setAbstract(ElType->isAbstract()); +} + +PackedType::PackedType(const Type *ElType, unsigned NumEl) + : SequentialType(PackedTyID, ElType) { + NumElements = NumEl; + + 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) { - setDerivedTypeProperties(); + // Calculate whether or not this type is abstract + setAbstract(E->isAbstract()); } OpaqueType::OpaqueType() : DerivedType(OpaqueTyID) { setAbstract(true); - setDescription("opaque"+utostr(getUniqueID())); #ifdef DEBUG_MERGE_TYPES - std::cerr << "Derived new type: " << getDescription() << "\n"; + std::cerr << "Derived new type: " << *this << "\n"; #endif } +// dropAllTypeUses - When this (abstract) type is resolved to be equal to +// another (more concrete) type, we must eliminate all references to other +// types, to avoid some circular reference problems. +void DerivedType::dropAllTypeUses() { + if (!ContainedTys.empty()) { + while (ContainedTys.size() > 1) + ContainedTys.pop_back(); + + // 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; + } +} -//===----------------------------------------------------------------------===// -// Derived Type setDerivedTypeProperties Function -//===----------------------------------------------------------------------===// - -// getTypeProps - This is a recursive function that walks a type hierarchy -// calculating the description for a type and whether or not it is abstract or -// recursive. Worst case it will have to do a lot of traversing if you have -// some whacko opaque types, but in most cases, it will do some simple stuff -// when it hits non-abstract types that aren't recursive. -// -static std::string getTypeProps(const Type *Ty, - std::vector &TypeStack, - bool &isAbstract, bool &isRecursive) { - if (!Ty->isAbstract() && !Ty->isRecursive() && // Base case for the recursion - Ty->getDescription().size()) { - return Ty->getDescription(); // Primitive = leaf type - } else if (isa(Ty)) { // Base case for the recursion - isAbstract = true; // This whole type is abstract! - return Ty->getDescription(); // Opaque = leaf type - } else { - // Check to see if the Type is already on the stack... - unsigned Slot = 0, CurSize = TypeStack.size(); - while (Slot < CurSize && TypeStack[Slot] != Ty) ++Slot; // Scan for type - - // This is another base case for the recursion. In this case, we know - // that we have looped back to a type that we have previously visited. - // Generate the appropriate upreference to handle this. - // - if (Slot < CurSize) { - isRecursive = true; // We know we are recursive - return "\\" + utostr(CurSize-Slot); // Here's the upreference - } else { // Recursive case: abstract derived type... - std::string Result; - TypeStack.push_back(Ty); // Add us to the stack.. - - switch (Ty->getPrimitiveID()) { - case Type::FunctionTyID: { - const FunctionType *MTy = cast(Ty); - Result = getTypeProps(MTy->getReturnType(), TypeStack, - isAbstract, isRecursive)+" ("; - for (FunctionType::ParamTypes::const_iterator - I = MTy->getParamTypes().begin(), - E = MTy->getParamTypes().end(); I != E; ++I) { - if (I != MTy->getParamTypes().begin()) - Result += ", "; - Result += getTypeProps(*I, TypeStack, isAbstract, isRecursive); - } - if (MTy->isVarArg()) { - if (!MTy->getParamTypes().empty()) Result += ", "; - Result += "..."; - } - Result += ")"; - break; - } - case Type::StructTyID: { - const StructType *STy = cast(Ty); - Result = "{ "; - for (StructType::ElementTypes::const_iterator - I = STy->getElementTypes().begin(), - E = STy->getElementTypes().end(); I != E; ++I) { - if (I != STy->getElementTypes().begin()) - Result += ", "; - Result += getTypeProps(*I, TypeStack, isAbstract, isRecursive); - } - Result += " }"; - break; - } - case Type::PointerTyID: { - const PointerType *PTy = cast(Ty); - Result = getTypeProps(PTy->getElementType(), TypeStack, - isAbstract, isRecursive) + " *"; - break; - } - case Type::ArrayTyID: { - const ArrayType *ATy = cast(Ty); - unsigned NumElements = ATy->getNumElements(); - Result = "["; - Result += utostr(NumElements) + " x "; - Result += getTypeProps(ATy->getElementType(), TypeStack, - isAbstract, isRecursive) + "]"; - break; - } - default: - assert(0 && "Unhandled case in getTypeProps!"); - Result = ""; - } +/// TypePromotionGraph and graph traits - this is designed to allow us to do +/// efficient SCC processing of type graphs. This is the exact same as +/// GraphTraits, except that we pretend that concrete types have no +/// children to avoid processing them. +struct TypePromotionGraph { + Type *Ty; + TypePromotionGraph(Type *T) : Ty(T) {} +}; - TypeStack.pop_back(); // Remove self from stack... - return Result; +namespace llvm { + template <> struct GraphTraits { + typedef Type NodeType; + typedef Type::subtype_iterator ChildIteratorType; + + static inline NodeType *getEntryNode(TypePromotionGraph G) { return G.Ty; } + static inline ChildIteratorType child_begin(NodeType *N) { + if (N->isAbstract()) + return N->subtype_begin(); + else // No need to process children of concrete types. + return N->subtype_end(); } - } + static inline ChildIteratorType child_end(NodeType *N) { + return N->subtype_end(); + } + }; } -// setDerivedTypeProperties - This function is used to calculate the -// isAbstract, isRecursive, and the Description settings for a type. The -// getTypeProps function does all the dirty work. +// PromoteAbstractToConcrete - This is a recursive function that walks a type +// graph calculating whether or not a type is abstract. // -void DerivedType::setDerivedTypeProperties() { - std::vector TypeStack; - bool isAbstract = false, isRecursive = false; - - setDescription(getTypeProps(this, TypeStack, isAbstract, isRecursive)); - setAbstract(isAbstract); - setRecursive(isRecursive); +void Type::PromoteAbstractToConcrete() { + if (!isAbstract()) return; + + scc_iterator SI = scc_begin(TypePromotionGraph(this)); + scc_iterator SE = scc_end (TypePromotionGraph(this)); + + for (; SI != SE; ++SI) { + std::vector &SCC = *SI; + + // Concrete types are leaves in the tree. Since an SCC will either be all + // abstract or all concrete, we only need to check one type. + if (SCC[0]->isAbstract()) { + if (isa(SCC[0])) + return; // Not going to be concrete, sorry. + + // If all of the children of all of the types in this SCC are concrete, + // then this SCC is now concrete as well. If not, neither this SCC, nor + // any parent SCCs will be concrete, so we might as well just exit. + for (unsigned i = 0, e = SCC.size(); i != e; ++i) + for (Type::subtype_iterator CI = SCC[i]->subtype_begin(), + E = SCC[i]->subtype_end(); CI != E; ++CI) + if ((*CI)->isAbstract()) + // If the child type is in our SCC, it doesn't make the entire SCC + // abstract unless there is a non-SCC abstract type. + if (std::find(SCC.begin(), SCC.end(), *CI) == SCC.end()) + return; // Not going to be concrete, sorry. + + // Okay, we just discovered this whole SCC is now concrete, mark it as + // such! + for (unsigned i = 0, e = SCC.size(); i != e; ++i) { + assert(SCC[i]->isAbstract() && "Why are we processing concrete types?"); + + SCC[i]->setAbstract(false); + } + + for (unsigned i = 0, e = SCC.size(); i != e; ++i) { + assert(!SCC[i]->isAbstract() && "Concrete type became abstract?"); + // The type just became concrete, notify all users! + cast(SCC[i])->notifyUsesThatTypeBecameConcrete(); + } + } + } } @@ -375,39 +571,56 @@ void DerivedType::setDerivedTypeProperties() { // that assumes that two graphs are the same until proven otherwise. // static bool TypesEqual(const Type *Ty, const Type *Ty2, - std::map &EqTypes) { + std::map &EqTypes) { if (Ty == Ty2) return true; - if (Ty->getPrimitiveID() != Ty2->getPrimitiveID()) return false; - if (Ty->isPrimitiveType()) return true; + if (Ty->getTypeID() != Ty2->getTypeID()) return false; if (isa(Ty)) - return false; // Two nonequal opaque types are never equal + return false; // Two unequal opaque types are never equal - std::map::iterator It = EqTypes.find(Ty); - if (It != EqTypes.end()) + std::map::iterator It = EqTypes.lower_bound(Ty); + if (It != EqTypes.end() && It->first == Ty) return It->second == Ty2; // Looping back on a type, check for equality // Otherwise, add the mapping to the table to make sure we don't get // recursion on the types... - EqTypes.insert(std::make_pair(Ty, Ty2)); - - // Iterate over the types and make sure the the contents are equivalent... - Type::subtype_iterator I = Ty ->subtype_begin(), IE = Ty ->subtype_end(); - Type::subtype_iterator I2 = Ty2->subtype_begin(), IE2 = Ty2->subtype_end(); - for (; I != IE && I2 != IE2; ++I, ++I2) - if (!TypesEqual(*I, *I2, EqTypes)) return false; + EqTypes.insert(It, std::make_pair(Ty, Ty2)); // Two really annoying special cases that breaks an otherwise nice simple // algorithm is the fact that arraytypes have sizes that differentiates types, - // and that method types can be varargs or not. Consider this now. - if (const ArrayType *ATy = dyn_cast(Ty)) { - if (ATy->getNumElements() != cast(Ty2)->getNumElements()) - return false; - } else if (const FunctionType *MTy = dyn_cast(Ty)) { - if (MTy->isVarArg() != cast(Ty2)->isVarArg()) + // 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); + } else if (const StructType *STy = dyn_cast(Ty)) { + const StructType *STy2 = cast(Ty2); + if (STy->getNumElements() != STy2->getNumElements()) return false; + for (unsigned i = 0, e = STy2->getNumElements(); i != e; ++i) + if (!TypesEqual(STy->getElementType(i), STy2->getElementType(i), EqTypes)) + return false; + return true; + } else if (const ArrayType *ATy = dyn_cast(Ty)) { + const ArrayType *ATy2 = cast(Ty2); + return ATy->getNumElements() == ATy2->getNumElements() && + TypesEqual(ATy->getElementType(), ATy2->getElementType(), EqTypes); + } else if (const PackedType *PTy = dyn_cast(Ty)) { + const PackedType *PTy2 = cast(Ty2); + return PTy->getNumElements() == PTy2->getNumElements() && + TypesEqual(PTy->getElementType(), PTy2->getElementType(), EqTypes); + } else if (const FunctionType *FTy = dyn_cast(Ty)) { + const FunctionType *FTy2 = cast(Ty2); + if (FTy->isVarArg() != FTy2->isVarArg() || + FTy->getNumParams() != FTy2->getNumParams() || + !TypesEqual(FTy->getReturnType(), FTy2->getReturnType(), EqTypes)) return false; + for (unsigned i = 0, e = FTy2->getNumParams(); i != e; ++i) + if (!TypesEqual(FTy->getParamType(i), FTy2->getParamType(i), EqTypes)) + return false; + return true; + } else { + assert(0 && "Unknown derived type!"); + return false; } - - return I == IE && I2 == IE2; // Types equal if both iterators are done } static bool TypesEqual(const Type *Ty, const Type *Ty2) { @@ -415,128 +628,256 @@ static bool TypesEqual(const Type *Ty, const Type *Ty2) { return TypesEqual(Ty, Ty2, EqTypes); } +// AbstractTypeHasCycleThrough - Return true there is a path from CurTy to +// TargetTy in the type graph. We know that Ty is an abstract type, so if we +// ever reach a non-abstract type, we know that we don't need to search the +// subgraph. +static bool AbstractTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy, + std::set &VisitedTypes) { + if (TargetTy == CurTy) return true; + if (!CurTy->isAbstract()) return false; + + if (!VisitedTypes.insert(CurTy).second) + return false; // Already been here. + + for (Type::subtype_iterator I = CurTy->subtype_begin(), + E = CurTy->subtype_end(); I != E; ++I) + if (AbstractTypeHasCycleThrough(TargetTy, *I, VisitedTypes)) + return true; + return false; +} + +static bool ConcreteTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy, + std::set &VisitedTypes) { + if (TargetTy == CurTy) return true; + + if (!VisitedTypes.insert(CurTy).second) + return false; // Already been here. + + for (Type::subtype_iterator I = CurTy->subtype_begin(), + E = CurTy->subtype_end(); I != E; ++I) + if (ConcreteTypeHasCycleThrough(TargetTy, *I, VisitedTypes)) + return true; + return false; +} + +/// TypeHasCycleThroughItself - Return true if the specified type has a cycle +/// back to itself. +static bool TypeHasCycleThroughItself(const Type *Ty) { + std::set VisitedTypes; + + if (Ty->isAbstract()) { // Optimized case for abstract types. + for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); + I != E; ++I) + if (AbstractTypeHasCycleThrough(Ty, *I, VisitedTypes)) + return true; + } else { + for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); + I != E; ++I) + if (ConcreteTypeHasCycleThrough(Ty, *I, VisitedTypes)) + return true; + } + return false; +} //===----------------------------------------------------------------------===// // Derived Type Factory Functions //===----------------------------------------------------------------------===// +namespace llvm { +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; + +public: + 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); + } + + /// 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... +// our map if an abstract type gets refined somehow. // +namespace llvm { template -class TypeMap : public AbstractTypeUser { - typedef std::map > MapTy; - MapTy Map; +class TypeMap : public TypeMapBase { + std::map Map; public: + typedef typename std::map::iterator iterator; ~TypeMap() { print("ON EXIT"); } inline TypeClass *get(const ValType &V) { - typename std::map >::iterator I - = Map.find(V); - // TODO: FIXME: When Types are not CONST. - return (I != Map.end()) ? (TypeClass*)I->second.get() : 0; + iterator I = Map.find(V); + return I != Map.end() ? cast((Type*)I->second.get()) : 0; } - inline void add(const ValType &V, TypeClass *T) { - Map.insert(std::make_pair(V, PATypeHandle(T, this))); + inline void add(const ValType &V, TypeClass *Ty) { + Map.insert(std::make_pair(V, Ty)); + + // If this type has a cycle, remember it. + TypesByHash.insert(std::make_pair(ValType::hashTypeStructure(Ty), Ty)); print("add"); } - - // containsEquivalent - Return true if the typemap contains a type that is - // structurally equivalent to the specified type. - // - inline const TypeClass *containsEquivalent(const TypeClass *Ty) { - for (typename MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I) - if (I->second.get() != Ty && TypesEqual(Ty, I->second.get())) - return (TypeClass*)I->second.get(); // FIXME TODO when types not const - return 0; + + 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 is called when one of the contained abstract - // types gets refined... this simply removes the abstract type from our table. - // We expect that whoever refined the type will add it back to the table, - // corrected. - // - virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) { + /// 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 << "Removing Old type from Tab: " << (void*)OldTy << ", " - << OldTy->getDescription() << " replacement == " << (void*)NewTy - << ", " << NewTy->getDescription() << "\n"; + std::cerr << "RefineAbstractType(" << (void*)OldType << "[" << *OldType + << "], " << (void*)NewType << " [" << *NewType << "])\n"; #endif - for (typename MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I) - if (I->second == OldTy) { - // Check to see if the type just became concrete. If so, remove self - // from user list. - I->second.removeUserFromConcrete(); - I->second = cast(NewTy); + + // 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. + PATypeHolder TyHolder = Ty; + + // 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!"); + + // 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] = NewType; + 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 (!TypeHasCycleThroughItself(Ty)) { + typename std::map::iterator I; + bool Inserted; + + tie(I, Inserted) = Map.insert(std::make_pair(ValType::get(Ty), Ty)); + if (!Inserted) { + assert(OldType != NewType); + // Refined to a different type altogether? + RemoveFromTypesByHash(OldTypeHash, Ty); + + // We already have this type in the table. Get rid of the newly refined + // type. + TypeClass *NewTy = cast((Type*)I->second.get()); + 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); + Entry = E; + for (; I != E; ++I) { + 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)) { + TypeClass *NewTy = cast((Type*)I->second.get()); + + 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; + } + TypesByHash.erase(Entry); + Ty->refineAbstractTypeTo(NewTy); + return; + } + } + } + + // 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)); + } - void remove(const ValType &OldVal) { - typename MapTy::iterator I = Map.find(OldVal); - assert(I != Map.end() && "TypeMap::remove, element not found!"); - Map.erase(I); + // If the hash codes differ, update TypesByHash + if (NewTypeHash != OldTypeHash) { + RemoveFromTypesByHash(OldTypeHash, 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! 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"; unsigned i = 0; - for (MapTy::const_iterator I = Map.begin(), E = Map.end(); I != E; ++I) - std::cerr << " " << (++i) << ". " << I->second << " " - << I->second->getDescription() << "\n"; + 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"; #endif } void dump() const { print("dump output"); } }; - - -// ValTypeBase - This is the base class that is used by the various -// instantiations of TypeMap. This class is an AbstractType user that notifies -// the underlying TypeMap when it gets modified. -// -template -class ValTypeBase : public AbstractTypeUser { - TypeMap &MyTable; -protected: - inline ValTypeBase(TypeMap &tab) : MyTable(tab) {} - - // Subclass should override this... to update self as usual - virtual void doRefinement(const DerivedType *OldTy, const Type *NewTy) = 0; - - // typeBecameConcrete - This callback occurs when a contained type refines - // to itself, but becomes concrete in the process. Our subclass should remove - // itself from the ATU list of the specified type. - // - virtual void typeBecameConcrete(const DerivedType *Ty) = 0; - - virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) { - assert(OldTy == NewTy || OldTy->isAbstract()); - - if (!OldTy->isAbstract()) - typeBecameConcrete(OldTy); - - TypeMap &Table = MyTable; // Copy MyTable reference - ValType Tmp(*(ValType*)this); // Copy this. - PATypeHandle OldType(Table.get(*(ValType*)this), this); - Table.remove(*(ValType*)this); // Destroy's this! - - // Refine temporary to new state... - if (OldTy != NewTy) - Tmp.doRefinement(OldTy, NewTy); - - // FIXME: when types are not const! - Table.add((ValType&)Tmp, (TypeClass*)OldType.get()); - } - - void dump() const { - std::cerr << "ValTypeBase instance!\n"; - } -}; - +} //===----------------------------------------------------------------------===// @@ -545,61 +886,59 @@ protected: // FunctionValType - Define a class to hold the key that goes into the TypeMap // -class FunctionValType : public ValTypeBase { - PATypeHandle RetTy; - std::vector > ArgTypes; +namespace llvm { +class FunctionValType { + const Type *RetTy; + std::vector ArgTypes; bool isVarArg; public: FunctionValType(const Type *ret, const std::vector &args, - bool IVA, TypeMap &Tab) - : ValTypeBase(Tab), RetTy(ret, this), - isVarArg(IVA) { + bool IVA) : RetTy(ret), isVarArg(IVA) { for (unsigned i = 0; i < args.size(); ++i) - ArgTypes.push_back(PATypeHandle(args[i], this)); + ArgTypes.push_back(args[i]); } - // We *MUST* have an explicit copy ctor so that the TypeHandles think that - // this FunctionValType owns them, not the old one! - // - FunctionValType(const FunctionValType &MVT) - : ValTypeBase(MVT), RetTy(MVT.RetTy, this), - isVarArg(MVT.isVarArg) { - ArgTypes.reserve(MVT.ArgTypes.size()); - for (unsigned i = 0; i < MVT.ArgTypes.size(); ++i) - ArgTypes.push_back(PATypeHandle(MVT.ArgTypes[i], this)); + 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 - virtual void doRefinement(const DerivedType *OldType, const Type *NewType) { + 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; } - virtual void typeBecameConcrete(const DerivedType *Ty) { - if (RetTy == Ty) RetTy.removeUserFromConcrete(); - - for (unsigned i = 0; i < ArgTypes.size(); ++i) - if (ArgTypes[i] == Ty) ArgTypes[i].removeUserFromConcrete(); - } - inline bool operator<(const FunctionValType &MTV) const { - if (RetTy.get() < MTV.RetTy.get()) return true; - if (RetTy.get() > MTV.RetTy.get()) return false; + if (RetTy < MTV.RetTy) return true; + if (RetTy > MTV.RetTy) return false; if (ArgTypes < MTV.ArgTypes) return true; - return (ArgTypes == MTV.ArgTypes) && isVarArg < MTV.isVarArg; + return ArgTypes == MTV.ArgTypes && isVarArg < MTV.isVarArg; } }; +} // Define the actual map itself now... static TypeMap FunctionTypes; +FunctionValType FunctionValType::get(const FunctionType *FT) { + // Build up a FunctionValType + std::vector ParamTypes; + ParamTypes.reserve(FT->getNumParams()); + for (unsigned i = 0, e = FT->getNumParams(); i != e; ++i) + ParamTypes.push_back(FT->getParamType(i)); + return FunctionValType(FT->getReturnType(), ParamTypes, FT->isVarArg()); +} + + // FunctionType::get - The factory function for the FunctionType class... -FunctionType *FunctionType::get(const Type *ReturnType, +FunctionType *FunctionType::get(const Type *ReturnType, const std::vector &Params, bool isVarArg) { - FunctionValType VT(ReturnType, Params, isVarArg, FunctionTypes); + FunctionValType VT(ReturnType, Params, isVarArg); FunctionType *MT = FunctionTypes.get(VT); if (MT) return MT; @@ -614,44 +953,40 @@ FunctionType *FunctionType::get(const Type *ReturnType, //===----------------------------------------------------------------------===// // Array Type Factory... // -class ArrayValType : public ValTypeBase { - PATypeHandle ValTy; - unsigned Size; +namespace llvm { +class ArrayValType { + const Type *ValTy; + uint64_t Size; public: - ArrayValType(const Type *val, int sz, TypeMap &Tab) - : ValTypeBase(Tab), ValTy(val, this), Size(sz) {} + ArrayValType(const Type *val, uint64_t sz) : ValTy(val), Size(sz) {} - // We *MUST* have an explicit copy ctor so that the ValTy thinks that this - // ArrayValType owns it, not the old one! - // - ArrayValType(const ArrayValType &AVT) - : ValTypeBase(AVT), ValTy(AVT.ValTy, this), - Size(AVT.Size) {} + static ArrayValType get(const ArrayType *AT) { + return ArrayValType(AT->getElementType(), AT->getNumElements()); + } + + static unsigned hashTypeStructure(const ArrayType *AT) { + return (unsigned)AT->getNumElements(); + } // Subclass should override this... to update self as usual - virtual void doRefinement(const DerivedType *OldType, const Type *NewType) { + void doRefinement(const DerivedType *OldType, const Type *NewType) { assert(ValTy == OldType); ValTy = NewType; } - virtual void typeBecameConcrete(const DerivedType *Ty) { - assert(ValTy == Ty && - "Contained type became concrete but we're not using it!"); - ValTy.removeUserFromConcrete(); - } - inline bool operator<(const ArrayValType &MTV) const { if (Size < MTV.Size) return true; - return Size == MTV.Size && ValTy.get() < MTV.ValTy.get(); + return Size == MTV.Size && ValTy < MTV.ValTy; } }; - +} static TypeMap ArrayTypes; -ArrayType *ArrayType::get(const Type *ElementType, unsigned NumElements) { + +ArrayType *ArrayType::get(const Type *ElementType, uint64_t NumElements) { assert(ElementType && "Can't get array of null types!"); - ArrayValType AVT(ElementType, NumElements, ArrayTypes); + ArrayValType AVT(ElementType, NumElements); ArrayType *AT = ArrayTypes.get(AVT); if (AT) return AT; // Found a match, return it! @@ -659,59 +994,103 @@ ArrayType *ArrayType::get(const Type *ElementType, unsigned NumElements) { ArrayTypes.add(AVT, AT = new ArrayType(ElementType, NumElements)); #ifdef DEBUG_MERGE_TYPES - std::cerr << "Derived new type: " << AT->getDescription() << "\n"; + std::cerr << "Derived new type: " << *AT << "\n"; #endif return AT; } + +//===----------------------------------------------------------------------===// +// Packed Type Factory... +// +namespace llvm { +class PackedValType { + const Type *ValTy; + unsigned Size; +public: + PackedValType(const Type *val, int sz) : ValTy(val), Size(sz) {} + + static PackedValType get(const PackedType *PT) { + return PackedValType(PT->getElementType(), PT->getNumElements()); + } + + static unsigned hashTypeStructure(const PackedType *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 { + if (Size < MTV.Size) return true; + return Size == MTV.Size && ValTy < MTV.ValTy; + } +}; +} +static TypeMap PackedTypes; + + +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!"); + + PackedValType PVT(ElementType, NumElements); + PackedType *PT = PackedTypes.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)); + +#ifdef DEBUG_MERGE_TYPES + std::cerr << "Derived new type: " << *PT << "\n"; +#endif + return PT; +} + //===----------------------------------------------------------------------===// // Struct Type Factory... // +namespace llvm { // StructValType - Define a class to hold the key that goes into the TypeMap // -class StructValType : public ValTypeBase { - std::vector > ElTypes; +class StructValType { + std::vector ElTypes; public: - StructValType(const std::vector &args, - TypeMap &Tab) - : ValTypeBase(Tab) { - ElTypes.reserve(args.size()); - for (unsigned i = 0, e = args.size(); i != e; ++i) - ElTypes.push_back(PATypeHandle(args[i], this)); + StructValType(const std::vector &args) : ElTypes(args) {} + + static StructValType get(const StructType *ST) { + std::vector ElTypes; + ElTypes.reserve(ST->getNumElements()); + for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) + ElTypes.push_back(ST->getElementType(i)); + + return StructValType(ElTypes); } - // We *MUST* have an explicit copy ctor so that the TypeHandles think that - // this StructValType owns them, not the old one! - // - StructValType(const StructValType &SVT) - : ValTypeBase(SVT){ - ElTypes.reserve(SVT.ElTypes.size()); - for (unsigned i = 0, e = SVT.ElTypes.size(); i != e; ++i) - ElTypes.push_back(PATypeHandle(SVT.ElTypes[i], this)); + static unsigned hashTypeStructure(const StructType *ST) { + return ST->getNumElements(); } // Subclass should override this... to update self as usual - virtual void doRefinement(const DerivedType *OldType, const Type *NewType) { + void doRefinement(const DerivedType *OldType, const Type *NewType) { for (unsigned i = 0; i < ElTypes.size(); ++i) if (ElTypes[i] == OldType) ElTypes[i] = NewType; } - virtual void typeBecameConcrete(const DerivedType *Ty) { - for (unsigned i = 0, e = ElTypes.size(); i != e; ++i) - if (ElTypes[i] == Ty) - ElTypes[i].removeUserFromConcrete(); - } - inline bool operator<(const StructValType &STV) const { return ElTypes < STV.ElTypes; } }; +} static TypeMap StructTypes; StructType *StructType::get(const std::vector &ETypes) { - StructValType STV(ETypes, StructTypes); + StructValType STV(ETypes); StructType *ST = StructTypes.get(STV); if (ST) return ST; @@ -719,51 +1098,54 @@ StructType *StructType::get(const std::vector &ETypes) { StructTypes.add(STV, ST = new StructType(ETypes)); #ifdef DEBUG_MERGE_TYPES - std::cerr << "Derived new type: " << ST->getDescription() << "\n"; + std::cerr << "Derived new type: " << *ST << "\n"; #endif return ST; } + + //===----------------------------------------------------------------------===// // Pointer Type Factory... // // PointerValType - Define a class to hold the key that goes into the TypeMap // -class PointerValType : public ValTypeBase { - PATypeHandle ValTy; +namespace llvm { +class PointerValType { + const Type *ValTy; public: - PointerValType(const Type *val, TypeMap &Tab) - : ValTypeBase(Tab), ValTy(val, this) {} + PointerValType(const Type *val) : ValTy(val) {} - // We *MUST* have an explicit copy ctor so that the ValTy thinks that this - // PointerValType owns it, not the old one! - // - PointerValType(const PointerValType &PVT) - : ValTypeBase(PVT), ValTy(PVT.ValTy, this) {} + static PointerValType get(const PointerType *PT) { + return PointerValType(PT->getElementType()); + } + + static unsigned hashTypeStructure(const PointerType *PT) { + return 0; + } // Subclass should override this... to update self as usual - virtual void doRefinement(const DerivedType *OldType, const Type *NewType) { + void doRefinement(const DerivedType *OldType, const Type *NewType) { assert(ValTy == OldType); ValTy = NewType; } - virtual void typeBecameConcrete(const DerivedType *Ty) { - assert(ValTy == Ty && - "Contained type became concrete but we're not using it!"); - ValTy.removeUserFromConcrete(); - } - - inline bool operator<(const PointerValType &MTV) const { - return ValTy.get() < MTV.ValTy.get(); + bool operator<(const PointerValType &MTV) const { + return ValTy < MTV.ValTy; } }; +} static TypeMap PointerTypes; PointerType *PointerType::get(const Type *ValueType) { assert(ValueType && "Can't get a pointer to type!"); - PointerValType PVT(ValueType, PointerTypes); + // 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); PointerType *PT = PointerTypes.get(PVT); if (PT) return PT; @@ -772,44 +1154,21 @@ PointerType *PointerType::get(const Type *ValueType) { PointerTypes.add(PVT, PT = new PointerType(ValueType)); #ifdef DEBUG_MERGE_TYPES - std::cerr << "Derived new type: " << PT->getDescription() << "\n"; + std::cerr << "Derived new type: " << *PT << "\n"; #endif return PT; } -void debug_type_tables() { - FunctionTypes.dump(); - ArrayTypes.dump(); - StructTypes.dump(); - PointerTypes.dump(); -} - - //===----------------------------------------------------------------------===// // Derived Type Refinement Functions //===----------------------------------------------------------------------===// -// addAbstractTypeUser - Notify an abstract type that there is a new user of -// it. This function is called primarily by the PATypeHandle class. -// -void DerivedType::addAbstractTypeUser(AbstractTypeUser *U) const { - assert(isAbstract() && "addAbstractTypeUser: Current type not abstract!"); - -#if DEBUG_MERGE_TYPES - std::cerr << " addAbstractTypeUser[" << (void*)this << ", " - << getDescription() << "][" << AbstractTypeUsers.size() - << "] User = " << U << "\n"; -#endif - AbstractTypeUsers.push_back(U); -} - - // removeAbstractTypeUser - Notify an abstract type that a user of the class // no longer has a handle to the type. This function is called primarily by // the PATypeHandle class. When there are no users of the abstract type, it -// is anihilated, because there is no way to get a reference to it ever again. +// 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. @@ -822,15 +1181,15 @@ void DerivedType::removeAbstractTypeUser(AbstractTypeUser *U) const { assert(i < AbstractTypeUsers.size() && "Index out of range!"); // Wraparound? AbstractTypeUsers.erase(AbstractTypeUsers.begin()+i); - + #ifdef DEBUG_MERGE_TYPES std::cerr << " remAbstractTypeUser[" << (void*)this << ", " - << getDescription() << "][" << i << "] User = " << U << "\n"; + << *this << "][" << i << "] User = " << U << "\n"; #endif - - if (AbstractTypeUsers.empty() && isAbstract()) { + + if (AbstractTypeUsers.empty() && getRefCount() == 0 && isAbstract()) { #ifdef DEBUG_MERGE_TYPES - std::cerr << "DELETEing unused abstract type: <" << getDescription() + std::cerr << "DELETEing unused abstract type: <" << *this << ">[" << (void*)this << "]" << "\n"; #endif delete this; // No users of this abstract type! @@ -840,36 +1199,44 @@ void DerivedType::removeAbstractTypeUser(AbstractTypeUser *U) const { // refineAbstractTypeTo - This function is used to 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. +// This causes all users of 'this' to switch to reference the more concrete type +// NewType and for 'this' to be deleted. // void DerivedType::refineAbstractTypeTo(const Type *NewType) { assert(isAbstract() && "refineAbstractTypeTo: Current type is not abstract!"); assert(this != NewType && "Can't refine to myself!"); + assert(ForwardType == 0 && "This type has already been refined!"); + + // The descriptions may be out of date. Conservatively clear them all! + AbstractTypeDescriptions.clear(); #ifdef DEBUG_MERGE_TYPES std::cerr << "REFINING abstract type [" << (void*)this << " " - << getDescription() << "] to [" << (void*)NewType << " " - << NewType->getDescription() << "]!\n"; + << *this << "] to [" << (void*)NewType << " " + << *NewType << "]!\n"; #endif - // Make sure to put the type to be refined to into a holder so that if IT gets // refined, that we will not continue using a dead reference... // PATypeHolder NewTy(NewType); + // Any PATypeHolders referring to this type will now automatically forward to + // the type we are resolved to. + ForwardType = NewType; + if (NewType->isAbstract()) + cast(NewType)->addRef(); + // Add a self use of the current type so that we don't delete ourself until - // after this while loop. We are careful to never invoke refine on ourself, - // so this extra reference shouldn't be a problem. Note that we must only - // remove a single reference at the end, but we must tolerate multiple self - // references because we could be refineAbstractTypeTo'ing recursively on the - // same type. + // after the function exits. // - addAbstractTypeUser(this); + PATypeHolder CurrentTy(this); - // Count the number of self uses. Stop looping when sizeof(list) == NSU. - unsigned NumSelfUses = 0; + // To make the situation simpler, we ask the subclass to remove this type from + // the type map, and to replace any type uses with uses of non-abstract types. + // This dramatically limits the amount of recursive type trouble we can find + // ourselves in. + dropAllTypeUses(); // Iterate over all of the uses of this type, invoking callback. Each user // should remove itself from our use list automatically. We have to check to @@ -877,114 +1244,46 @@ void DerivedType::refineAbstractTypeTo(const Type *NewType) { // will not cause users to drop off of the use list. If we resolve to ourself // we succeed! // - while (AbstractTypeUsers.size() > NumSelfUses && NewTy != this) { + while (!AbstractTypeUsers.empty() && NewTy != this) { AbstractTypeUser *User = AbstractTypeUsers.back(); - if (User == this) { - // Move self use to the start of the list. Increment NSU. - std::swap(AbstractTypeUsers.back(), AbstractTypeUsers[NumSelfUses++]); - } else { - unsigned OldSize = AbstractTypeUsers.size(); + unsigned OldSize = AbstractTypeUsers.size(); #ifdef DEBUG_MERGE_TYPES - std::cerr << " REFINING user " << OldSize-1 << "[" << (void*)User - << "] of abstract type [" << (void*)this << " " - << getDescription() << "] to [" << (void*)NewTy.get() << " " - << NewTy->getDescription() << "]!\n"; + std::cerr << " REFINING user " << OldSize-1 << "[" << (void*)User + << "] of abstract type [" << (void*)this << " " + << *this << "] to [" << (void*)NewTy.get() << " " + << *NewTy << "]!\n"; #endif - User->refineAbstractType(this, NewTy); + User->refineAbstractType(this, NewTy); -#ifdef DEBUG_MERGE_TYPES - if (AbstractTypeUsers.size() == OldSize) { - User->refineAbstractType(this, NewTy); - if (AbstractTypeUsers.back() != User) - std::cerr << "User changed!\n"; - std::cerr << "Top of user list is:\n"; - AbstractTypeUsers.back()->dump(); - - std::cerr <<"\nOld User=\n"; - User->dump(); - } -#endif - assert(AbstractTypeUsers.size() != OldSize && - "AbsTyUser did not remove self from user list!"); - } + assert(AbstractTypeUsers.size() != OldSize && + "AbsTyUser did not remove self from user list!"); } - // Remove a single self use, even though there may be several here. This will - // probably 'delete this', so no instance variables may be used after this - // occurs... - // - assert((NewTy == this || AbstractTypeUsers.back() == this) && - "Only self uses should be left!"); - removeAbstractTypeUser(this); + // If we were successful removing all users from the type, 'this' will be + // deleted when the last PATypeHolder is destroyed or updated from this type. + // This may occur on exit of this function, as the CurrentTy object is + // destroyed. } -// typeIsRefined - Notify AbstractTypeUsers of this type that the current type -// has been refined a bit. The pointer is still valid and still should be -// used, but the subtypes have changed. +// notifyUsesThatTypeBecameConcrete - Notify AbstractTypeUsers of this type that +// the current type has transitioned from being abstract to being concrete. // -void DerivedType::typeIsRefined() { - assert(isRefining >= 0 && isRefining <= 2 && "isRefining out of bounds!"); - if (isRefining == 1) return; // Kill recursion here... - ++isRefining; - +void DerivedType::notifyUsesThatTypeBecameConcrete() { #ifdef DEBUG_MERGE_TYPES - std::cerr << "typeIsREFINED type: " << (void*)this <<" "< Refined; - while (1) { - unsigned i; - for (i = AbstractTypeUsers.size(); i != 0; --i) - if (find(Refined.begin(), Refined.end(), AbstractTypeUsers[i-1]) == - Refined.end()) - break; // Found an unrefined user? - - if (i == 0) break; // Noone to refine left, break out of here! - - AbstractTypeUser *ATU = AbstractTypeUsers[--i]; - Refined.push_back(ATU); // Keep track of which users we have refined! - -#ifdef DEBUG_MERGE_TYPES - std::cerr << " typeIsREFINED user " << i << "[" << ATU - << "] of abstract type [" << (void*)this << " " - << getDescription() << "]\n"; -#endif - ATU->refineAbstractType(this, this); - } + unsigned OldSize = AbstractTypeUsers.size(); + while (!AbstractTypeUsers.empty()) { + AbstractTypeUser *ATU = AbstractTypeUsers.back(); + ATU->typeBecameConcrete(this); - --isRefining; - -#ifndef _NDEBUG - if (!(isAbstract() || AbstractTypeUsers.empty())) - for (unsigned i = 0; i < AbstractTypeUsers.size(); ++i) { - if (AbstractTypeUsers[i] != this) { - // Debugging hook - std::cerr << "FOUND FAILURE\nUser: "; - AbstractTypeUsers[i]->dump(); - std::cerr << "\nCatch:\n"; - AbstractTypeUsers[i]->refineAbstractType(this, this); - assert(0 && "Type became concrete," - " but it still has abstract type users hanging around!"); - } + assert(AbstractTypeUsers.size() < OldSize-- && + "AbstractTypeUser did not remove itself from the use list!"); } -#endif } - + @@ -994,29 +1293,11 @@ void DerivedType::typeIsRefined() { // void FunctionType::refineAbstractType(const DerivedType *OldType, const Type *NewType) { -#ifdef DEBUG_MERGE_TYPES - std::cerr << "FunctionTy::refineAbstractTy(" << (void*)OldType << "[" - << OldType->getDescription() << "], " << (void*)NewType << " [" - << NewType->getDescription() << "])\n"; -#endif - // Find the type element we are refining... - if (ResultType == OldType) { - ResultType.removeUserFromConcrete(); - ResultType = NewType; - } - for (unsigned i = 0, e = ParamTys.size(); i != e; ++i) - if (ParamTys[i] == OldType) { - ParamTys[i].removeUserFromConcrete(); - ParamTys[i] = NewType; - } + FunctionTypes.RefineAbstractType(this, OldType, NewType); +} - const FunctionType *MT = FunctionTypes.containsEquivalent(this); - if (MT && MT != this) { - refineAbstractTypeTo(MT); // Different type altogether... - } else { - setDerivedTypeProperties(); // Update the name and isAbstract - typeIsRefined(); // Same type, different contents... - } +void FunctionType::typeBecameConcrete(const DerivedType *AbsTy) { + FunctionTypes.TypeBecameConcrete(this, AbsTy); } @@ -1025,53 +1306,38 @@ void FunctionType::refineAbstractType(const DerivedType *OldType, // concrete type. // void ArrayType::refineAbstractType(const DerivedType *OldType, - const Type *NewType) { -#ifdef DEBUG_MERGE_TYPES - std::cerr << "ArrayTy::refineAbstractTy(" << (void*)OldType << "[" - << OldType->getDescription() << "], " << (void*)NewType << " [" - << NewType->getDescription() << "])\n"; -#endif + const Type *NewType) { + ArrayTypes.RefineAbstractType(this, OldType, NewType); +} - assert(getElementType() == OldType); - ElementType.removeUserFromConcrete(); - ElementType = NewType; +void ArrayType::typeBecameConcrete(const DerivedType *AbsTy) { + ArrayTypes.TypeBecameConcrete(this, AbsTy); +} - const ArrayType *AT = ArrayTypes.containsEquivalent(this); - if (AT && AT != this) { - refineAbstractTypeTo(AT); // Different type altogether... - } else { - setDerivedTypeProperties(); // Update the name and isAbstract - typeIsRefined(); // Same type, different contents... - } +// 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, + const Type *NewType) { + PackedTypes.RefineAbstractType(this, OldType, NewType); } +void PackedType::typeBecameConcrete(const DerivedType *AbsTy) { + PackedTypes.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 StructType::refineAbstractType(const DerivedType *OldType, - const Type *NewType) { -#ifdef DEBUG_MERGE_TYPES - std::cerr << "StructTy::refineAbstractTy(" << (void*)OldType << "[" - << OldType->getDescription() << "], " << (void*)NewType << " [" - << NewType->getDescription() << "])\n"; -#endif - for (int i = ETypes.size()-1; i >= 0; --i) - if (ETypes[i] == OldType) { - ETypes[i].removeUserFromConcrete(); - - // Update old type to new type in the array... - ETypes[i] = NewType; - } + const Type *NewType) { + StructTypes.RefineAbstractType(this, OldType, NewType); +} - const StructType *ST = StructTypes.containsEquivalent(this); - if (ST && ST != this) { - refineAbstractTypeTo(ST); // Different type altogether... - } else { - setDerivedTypeProperties(); // Update the name and isAbstract - typeIsRefined(); // Same type, different contents... - } +void StructType::typeBecameConcrete(const DerivedType *AbsTy) { + StructTypes.TypeBecameConcrete(this, AbsTy); } // refineAbstractType - Called when a contained type is found to be more @@ -1079,23 +1345,61 @@ void StructType::refineAbstractType(const DerivedType *OldType, // concrete type. // void PointerType::refineAbstractType(const DerivedType *OldType, - const Type *NewType) { -#ifdef DEBUG_MERGE_TYPES - std::cerr << "PointerTy::refineAbstractTy(" << (void*)OldType << "[" - << OldType->getDescription() << "], " << (void*)NewType << " [" - << NewType->getDescription() << "])\n"; -#endif + const Type *NewType) { + PointerTypes.RefineAbstractType(this, OldType, NewType); +} - assert(ElementType == OldType); - ElementType.removeUserFromConcrete(); - ElementType = NewType; +void PointerType::typeBecameConcrete(const DerivedType *AbsTy) { + PointerTypes.TypeBecameConcrete(this, AbsTy); +} - const PointerType *PT = PointerTypes.containsEquivalent(this); - if (PT && PT != this) { - refineAbstractTypeTo(PT); // Different type altogether... - } else { - setDerivedTypeProperties(); // Update the name and isAbstract - typeIsRefined(); // Same type, different contents... +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; } } +namespace llvm { +std::ostream &operator<<(std::ostream &OS, const Type *T) { + if (T == 0) + OS << " value!\n"; + else + T->print(OS); + return OS; +} + +std::ostream &operator<<(std::ostream &OS, const Type &T) { + T.print(OS); + 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