X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FType.cpp;h=4990700370f3c873b49d853f78b447778a674145;hb=8e637a9383fc0d37e4afd55f47a22fb45d15ac59;hp=fb4063a5ca54446f010dcfa1e3e10a7ead2cfce5;hpb=56c5acbe9600f33a3d7260ef68211203cf675279;p=oota-llvm.git diff --git a/lib/VMCore/Type.cpp b/lib/VMCore/Type.cpp index fb4063a5ca5..4990700370f 100644 --- a/lib/VMCore/Type.cpp +++ b/lib/VMCore/Type.cpp @@ -5,9 +5,19 @@ //===----------------------------------------------------------------------===// #include "llvm/DerivedTypes.h" -#include "llvm/Support/StringExtras.h" #include "llvm/SymbolTable.h" -#include "llvm/Support/STLExtras.h" +#include "llvm/Constants.h" +#include "Support/StringExtras.h" +#include "Support/STLExtras.h" +#include +#include + +using std::vector; +using std::string; +using std::map; +using std::swap; +using std::make_pair; +using std::cerr; // 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 @@ -24,11 +34,16 @@ static unsigned CurUID = 0; static vector UIDMappings; +void PATypeHolder::dump() const { + cerr << "PATypeHolder(" << (void*)this << ")\n"; +} + + Type::Type(const string &name, PrimitiveID id) : Value(Type::TypeTy, Value::TypeVal) { setDescription(name); ID = id; - Abstract = false; + Abstract = Recursive = false; UID = CurUID++; // Assign types UID's as they are created UIDMappings.push_back(this); } @@ -67,6 +82,68 @@ const Type *Type::getPrimitiveType(PrimitiveID IDNumber) { } } +// isLosslesslyConvertableTo - Return true if this type can be converted to +// 'Ty' without any reinterpretation of bits. For example, uint to int. +// +bool Type::isLosslesslyConvertableTo(const Type *Ty) const { + if (this == Ty) return true; + if ((!isPrimitiveType() && !isa(this)) || + (!isa(Ty) && !Ty->isPrimitiveType())) return false; + + if (getPrimitiveID() == Ty->getPrimitiveID()) + 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()) { + 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); + 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 +// 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" + default: return 0; + } +} + + +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(); +} + +// 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 + + return ETypes[Idx]; +} + + //===----------------------------------------------------------------------===// // Auxilliary classes //===----------------------------------------------------------------------===// @@ -74,36 +151,28 @@ const Type *Type::getPrimitiveType(PrimitiveID IDNumber) { // These classes are used to implement specialized behavior for each different // type. // -class SignedIntType : public Type { - int Size; -public: - SignedIntType(const string &Name, PrimitiveID id, int size) : Type(Name, id) { - Size = size; - } +struct SignedIntType : public Type { + SignedIntType(const string &Name, PrimitiveID id) : Type(Name, id) {} // isSigned - Return whether a numeric type is signed. virtual bool isSigned() const { return 1; } - // isIntegral - Equivalent to isSigned() || isUnsigned, but with only a single + // isInteger - Equivalent to isSigned() || isUnsigned, but with only a single // virtual function invocation. // - virtual bool isIntegral() const { return 1; } + virtual bool isInteger() const { return 1; } }; -class UnsignedIntType : public Type { - uint64_t Size; -public: - UnsignedIntType(const string &N, PrimitiveID id, int size) : Type(N, id) { - Size = size; - } +struct UnsignedIntType : public Type { + UnsignedIntType(const string &N, PrimitiveID id) : Type(N, id) {} // isUnsigned - Return whether a numeric type is signed. virtual bool isUnsigned() const { return 1; } - // isIntegral - Equivalent to isSigned() || isUnsigned, but with only a single + // isInteger - Equivalent to isSigned() || isUnsigned, but with only a single // virtual function invocation. // - virtual bool isIntegral() const { return 1; } + virtual bool isInteger() const { return 1; } }; static struct TypeType : public Type { @@ -117,14 +186,14 @@ static struct TypeType : public Type { Type *Type::VoidTy = new Type("void" , VoidTyID), *Type::BoolTy = new Type("bool" , BoolTyID), - *Type::SByteTy = new SignedIntType("sbyte" , SByteTyID, 1), - *Type::UByteTy = new UnsignedIntType("ubyte" , UByteTyID, 1), - *Type::ShortTy = new SignedIntType("short" , ShortTyID, 2), - *Type::UShortTy = new UnsignedIntType("ushort", UShortTyID, 2), - *Type::IntTy = new SignedIntType("int" , IntTyID, 4), - *Type::UIntTy = new UnsignedIntType("uint" , UIntTyID, 4), - *Type::LongTy = new SignedIntType("long" , LongTyID, 8), - *Type::ULongTy = new UnsignedIntType("ulong" , ULongTyID, 8), + *Type::SByteTy = new SignedIntType("sbyte" , SByteTyID), + *Type::UByteTy = new UnsignedIntType("ubyte" , UByteTyID), + *Type::ShortTy = new SignedIntType("short" , ShortTyID), + *Type::UShortTy = new UnsignedIntType("ushort", UShortTyID), + *Type::IntTy = new SignedIntType("int" , IntTyID), + *Type::UIntTy = new UnsignedIntType("uint" , UIntTyID), + *Type::LongTy = new SignedIntType("long" , LongTyID), + *Type::ULongTy = new UnsignedIntType("ulong" , ULongTyID), *Type::FloatTy = new Type("float" , FloatTyID), *Type::DoubleTy = new Type("double", DoubleTyID), *Type::TypeTy = &TheTypeType, @@ -135,8 +204,9 @@ Type *Type::VoidTy = new Type("void" , VoidTyID), // Derived Type Constructors //===----------------------------------------------------------------------===// -MethodType::MethodType(const Type *Result, const vector &Params, - bool IsVarArgs) : DerivedType("", MethodTyID), +FunctionType::FunctionType(const Type *Result, + const vector &Params, + bool IsVarArgs) : DerivedType(FunctionTyID), ResultType(PATypeHandle(Result, this)), isVarArgs(IsVarArgs) { ParamTys.reserve(Params.size()); @@ -146,14 +216,8 @@ MethodType::MethodType(const Type *Result, const vector &Params, setDerivedTypeProperties(); } -ArrayType::ArrayType(const Type *ElType, int NumEl) - : DerivedType("", ArrayTyID), ElementType(PATypeHandle(ElType, this)) { - NumElements = NumEl; - setDerivedTypeProperties(); -} - StructType::StructType(const vector &Types) - : DerivedType("", StructTyID) { + : CompositeType(StructTyID) { ETypes.reserve(Types.size()); for (unsigned i = 0; i < Types.size(); ++i) { assert(Types[i] != Type::VoidTy && "Void type in method prototype!!"); @@ -162,12 +226,17 @@ StructType::StructType(const vector &Types) setDerivedTypeProperties(); } -PointerType::PointerType(const Type *E) : DerivedType("", PointerTyID), - ValueType(PATypeHandle(E, this)) { +ArrayType::ArrayType(const Type *ElType, unsigned NumEl) + : SequentialType(ArrayTyID, ElType) { + NumElements = NumEl; + setDerivedTypeProperties(); +} + +PointerType::PointerType(const Type *E) : SequentialType(PointerTyID, E) { setDerivedTypeProperties(); } -OpaqueType::OpaqueType() : DerivedType("", OpaqueTyID) { +OpaqueType::OpaqueType() : DerivedType(OpaqueTyID) { setAbstract(true); setDescription("opaque"+utostr(getUniqueID())); #ifdef DEBUG_MERGE_TYPES @@ -213,11 +282,11 @@ static string getTypeProps(const Type *Ty, vector &TypeStack, TypeStack.push_back(Ty); // Add us to the stack.. switch (Ty->getPrimitiveID()) { - case Type::MethodTyID: { - const MethodType *MTy = cast(Ty); + case Type::FunctionTyID: { + const FunctionType *MTy = cast(Ty); Result = getTypeProps(MTy->getReturnType(), TypeStack, isAbstract, isRecursive)+" ("; - for (MethodType::ParamTypes::const_iterator + for (FunctionType::ParamTypes::const_iterator I = MTy->getParamTypes().begin(), E = MTy->getParamTypes().end(); I != E; ++I) { if (I != MTy->getParamTypes().begin()) @@ -246,15 +315,15 @@ static string getTypeProps(const Type *Ty, vector &TypeStack, } case Type::PointerTyID: { const PointerType *PTy = cast(Ty); - Result = getTypeProps(PTy->getValueType(), TypeStack, + Result = getTypeProps(PTy->getElementType(), TypeStack, isAbstract, isRecursive) + " *"; break; } case Type::ArrayTyID: { const ArrayType *ATy = cast(Ty); - int NumElements = ATy->getNumElements(); + unsigned NumElements = ATy->getNumElements(); Result = "["; - if (NumElements != -1) Result += itostr(NumElements) + " x "; + Result += utostr(NumElements) + " x "; Result += getTypeProps(ATy->getElementType(), TypeStack, isAbstract, isRecursive) + "]"; break; @@ -300,16 +369,16 @@ static bool TypesEqual(const Type *Ty, const Type *Ty2, if (Ty == Ty2) return true; if (Ty->getPrimitiveID() != Ty2->getPrimitiveID()) return false; if (Ty->isPrimitiveType()) return true; + if (isa(Ty)) + return false; // Two nonequal opaque types are never equal - if (Ty != Ty2) { - map::iterator I = EqTypes.find(Ty); - if (I != EqTypes.end()) - return I->second == Ty2; // Looping back on a type, check for equality + map::iterator It = EqTypes.find(Ty); + if (It != EqTypes.end()) + return It->second == Ty2; // Looping back on a type, check for equality - // Otherwise, add the mapping to the table to make sure we don't get - // recursion on the types... - EqTypes.insert(make_pair(Ty, Ty2)); - } + // Otherwise, add the mapping to the table to make sure we don't get + // recursion on the types... + EqTypes.insert(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(); @@ -323,12 +392,11 @@ static bool TypesEqual(const Type *Ty, const Type *Ty2, if (const ArrayType *ATy = dyn_cast(Ty)) { if (ATy->getNumElements() != cast(Ty2)->getNumElements()) return false; - } else if (const MethodType *MTy = dyn_cast(Ty)) { - if (MTy->isVarArg() != cast(Ty2)->isVarArg()) + } else if (const FunctionType *MTy = dyn_cast(Ty)) { + if (MTy->isVarArg() != cast(Ty2)->isVarArg()) return false; } - return I == IE && I2 == IE2; // Types equal if both iterators are done } @@ -352,11 +420,10 @@ class TypeMap : public AbstractTypeUser { typedef map > MapTy; MapTy Map; public: - ~TypeMap() { print("ON EXIT"); } inline TypeClass *get(const ValType &V) { - map >::iterator I = Map.find(V); + typename map >::iterator I = Map.find(V); // TODO: FIXME: When Types are not CONST. return (I != Map.end()) ? (TypeClass*)I->second.get() : 0; } @@ -370,7 +437,7 @@ public: // structurally equivalent to the specified type. // inline const TypeClass *containsEquivalent(const TypeClass *Ty) { - for (MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I) + 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; @@ -382,36 +449,37 @@ public: // corrected. // virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) { - if (OldTy == NewTy) return; #ifdef DEBUG_MERGE_TYPES cerr << "Removing Old type from Tab: " << (void*)OldTy << ", " << OldTy->getDescription() << " replacement == " << (void*)NewTy << ", " << NewTy->getDescription() << endl; #endif - for (MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I) + for (typename MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I) if (I->second == OldTy) { - Map.erase(I); - print("refineAbstractType after"); - return; + // Check to see if the type just became concrete. If so, remove self + // from user list. + I->second.removeUserFromConcrete(); + I->second = cast(NewTy); } - assert(0 && "Abstract type not found in table!"); } void remove(const ValType &OldVal) { - MapTy::iterator I = Map.find(OldVal); + typename MapTy::iterator I = Map.find(OldVal); assert(I != Map.end() && "TypeMap::remove, element not found!"); Map.erase(I); } - void print(const char *Arg) { + void print(const char *Arg) const { #ifdef DEBUG_MERGE_TYPES cerr << "TypeMap<>::" << Arg << " table contents:\n"; unsigned i = 0; - for (MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I) + for (MapTy::const_iterator I = Map.begin(), E = Map.end(); I != E; ++I) cerr << " " << (++i) << ". " << I->second << " " << I->second->getDescription() << endl; #endif } + + void dump() const { print("dump output"); } }; @@ -427,47 +495,63 @@ protected: // 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) { - if (OldTy == NewTy) return; + 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... - Tmp.doRefinement(OldTy, NewTy); + if (OldTy != NewTy) + Tmp.doRefinement(OldTy, NewTy); + // FIXME: when types are not const! Table.add((ValType&)Tmp, (TypeClass*)OldType.get()); } + + void dump() const { + cerr << "ValTypeBase instance!\n"; + } }; //===----------------------------------------------------------------------===// -// Method Type Factory and Value Class... +// Function Type Factory and Value Class... // -// MethodValType - Define a class to hold the key that goes into the TypeMap +// FunctionValType - Define a class to hold the key that goes into the TypeMap // -class MethodValType : public ValTypeBase { +class FunctionValType : public ValTypeBase { PATypeHandle RetTy; vector > ArgTypes; bool isVarArg; public: - MethodValType(const Type *ret, const vector &args, - bool IVA, TypeMap &Tab) - : ValTypeBase(Tab), RetTy(ret, this), + FunctionValType(const Type *ret, const vector &args, + bool IVA, TypeMap &Tab) + : ValTypeBase(Tab), RetTy(ret, this), isVarArg(IVA) { for (unsigned i = 0; i < args.size(); ++i) ArgTypes.push_back(PATypeHandle(args[i], this)); } // We *MUST* have an explicit copy ctor so that the TypeHandles think that - // this MethodValType owns them, not the old one! + // this FunctionValType owns them, not the old one! // - MethodValType(const MethodValType &MVT) - : ValTypeBase(MVT), RetTy(MVT.RetTy, this), + 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) @@ -477,11 +561,18 @@ public: // Subclass should override this... to update self as usual virtual void doRefinement(const DerivedType *OldType, const Type *NewType) { if (RetTy == OldType) RetTy = NewType; - for (unsigned i = 0; i < ArgTypes.size(); ++i) + for (unsigned i = 0, e = ArgTypes.size(); i != e; ++i) if (ArgTypes[i] == OldType) ArgTypes[i] = NewType; } - inline bool operator<(const MethodValType &MTV) const { + 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; @@ -491,17 +582,17 @@ public: }; // Define the actual map itself now... -static TypeMap MethodTypes; - -// MethodType::get - The factory function for the MethodType class... -MethodType *MethodType::get(const Type *ReturnType, - const vector &Params, - bool isVarArg) { - MethodValType VT(ReturnType, Params, isVarArg, MethodTypes); - MethodType *MT = MethodTypes.get(VT); +static TypeMap FunctionTypes; + +// FunctionType::get - The factory function for the FunctionType class... +FunctionType *FunctionType::get(const Type *ReturnType, + const vector &Params, + bool isVarArg) { + FunctionValType VT(ReturnType, Params, isVarArg, FunctionTypes); + FunctionType *MT = FunctionTypes.get(VT); if (MT) return MT; - MethodTypes.add(VT, MT = new MethodType(ReturnType, Params, isVarArg)); + FunctionTypes.add(VT, MT = new FunctionType(ReturnType, Params, isVarArg)); #ifdef DEBUG_MERGE_TYPES cerr << "Derived new type: " << MT << endl; @@ -514,7 +605,7 @@ MethodType *MethodType::get(const Type *ReturnType, // class ArrayValType : public ValTypeBase { PATypeHandle ValTy; - int Size; + unsigned Size; public: ArrayValType(const Type *val, int sz, TypeMap &Tab) : ValTypeBase(Tab), ValTy(val, this), Size(sz) {} @@ -528,7 +619,14 @@ public: // Subclass should override this... to update self as usual virtual void doRefinement(const DerivedType *OldType, const Type *NewType) { - if (ValTy == OldType) ValTy = 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 { @@ -539,7 +637,7 @@ public: static TypeMap ArrayTypes; -ArrayType *ArrayType::get(const Type *ElementType, int NumElements = -1) { +ArrayType *ArrayType::get(const Type *ElementType, unsigned NumElements) { assert(ElementType && "Can't get array of null types!"); ArrayValType AVT(ElementType, NumElements, ArrayTypes); @@ -567,7 +665,8 @@ public: StructValType(const vector &args, TypeMap &Tab) : ValTypeBase(Tab) { - for (unsigned i = 0; i < args.size(); ++i) + ElTypes.reserve(args.size()); + for (unsigned i = 0, e = args.size(); i != e; ++i) ElTypes.push_back(PATypeHandle(args[i], this)); } @@ -577,7 +676,7 @@ public: StructValType(const StructValType &SVT) : ValTypeBase(SVT){ ElTypes.reserve(SVT.ElTypes.size()); - for (unsigned i = 0; i < SVT.ElTypes.size(); ++i) + for (unsigned i = 0, e = SVT.ElTypes.size(); i != e; ++i) ElTypes.push_back(PATypeHandle(SVT.ElTypes[i], this)); } @@ -587,6 +686,12 @@ public: 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; } @@ -628,7 +733,14 @@ public: // Subclass should override this... to update self as usual virtual void doRefinement(const DerivedType *OldType, const Type *NewType) { - if (ValTy == OldType) ValTy = 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 { @@ -654,12 +766,32 @@ PointerType *PointerType::get(const Type *ValueType) { 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 + cerr << " addAbstractTypeUser[" << (void*)this << ", " << getDescription() + << "][" << AbstractTypeUsers.size() << "] User = " << U << endl; +#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 @@ -670,28 +802,27 @@ void DerivedType::removeAbstractTypeUser(AbstractTypeUser *U) const { // front. Also, it is likely that there will be a stack like behavior to // users that register and unregister users. // - for (unsigned i = AbstractTypeUsers.size(); i > 0; --i) { - if (AbstractTypeUsers[i-1] == U) { - AbstractTypeUsers.erase(AbstractTypeUsers.begin()+i-1); + unsigned i; + for (i = AbstractTypeUsers.size(); AbstractTypeUsers[i-1] != U; --i) + assert(i != 0 && "AbstractTypeUser not in user list!"); + + --i; // Convert to be in range 0 <= i < size() + assert(i < AbstractTypeUsers.size() && "Index out of range!"); // Wraparound? + + AbstractTypeUsers.erase(AbstractTypeUsers.begin()+i); #ifdef DEBUG_MERGE_TYPES - cerr << " removeAbstractTypeUser[" << (void*)this << ", " - << getDescription() << "][" << AbstractTypeUsers.size() - << "] User = " << U << endl; + cerr << " remAbstractTypeUser[" << (void*)this << ", " + << getDescription() << "][" << i << "] User = " << U << endl; #endif - - if (AbstractTypeUsers.empty()) { + + if (AbstractTypeUsers.empty() && isAbstract()) { #ifdef DEBUG_MERGE_TYPES - cerr << "DELETEing unused abstract type: " << getDescription() - << " " << (void*)this << endl; + cerr << "DELETEing unused abstract type: <" << getDescription() + << ">[" << (void*)this << "]" << endl; #endif - delete this; // No users of this abstract type! - } - return; - } + delete this; // No users of this abstract type! } - assert(isAbstract() && "removeAbstractTypeUser: Type not abstract!"); - assert(0 && "AbstractTypeUser not in user list!"); } @@ -714,7 +845,7 @@ void DerivedType::refineAbstractTypeTo(const Type *NewType) { // 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); + PATypeHolder NewTy(NewType); // 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, @@ -729,9 +860,12 @@ void DerivedType::refineAbstractTypeTo(const Type *NewType) { unsigned NumSelfUses = 0; // Iterate over all of the uses of this type, invoking callback. Each user - // should remove itself from our use list automatically. + // should remove itself from our use list automatically. We have to check to + // make sure that NewTy doesn't _become_ 'this'. If it does, resolving types + // will not cause users to drop off of the use list. If we resolve to ourself + // we succeed! // - while (AbstractTypeUsers.size() > NumSelfUses) { + while (AbstractTypeUsers.size() > NumSelfUses && NewTy != this) { AbstractTypeUser *User = AbstractTypeUsers.back(); if (User == this) { @@ -740,12 +874,25 @@ void DerivedType::refineAbstractTypeTo(const Type *NewType) { } else { unsigned OldSize = AbstractTypeUsers.size(); #ifdef DEBUG_MERGE_TYPES - cerr << " REFINING user " << OldSize-1 << " of abstract type [" + cerr << " REFINING user " << OldSize-1 << "[" << (void*)User + << "] of abstract type [" << (void*)this << " " << getDescription() << "] to [" << (void*)NewTy.get() << " " << NewTy->getDescription() << "]!\n"; #endif - AbstractTypeUsers.back()->refineAbstractType(this, NewTy); + User->refineAbstractType(this, NewTy); +#ifdef DEBUG_MERGE_TYPES + if (AbstractTypeUsers.size() == OldSize) { + User->refineAbstractType(this, NewTy); + if (AbstractTypeUsers.back() != User) + cerr << "User changed!\n"; + cerr << "Top of user list is:\n"; + AbstractTypeUsers.back()->dump(); + + cerr <<"\nOld User=\n"; + User->dump(); + } +#endif assert(AbstractTypeUsers.size() != OldSize && "AbsTyUser did not remove self from user list!"); } @@ -754,37 +901,74 @@ void DerivedType::refineAbstractTypeTo(const Type *NewType) { // 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(AbstractTypeUsers.back() == this && "Only self uses should be left!"); + // + assert((NewTy == this || AbstractTypeUsers.back() == this) && + "Only self uses should be left!"); removeAbstractTypeUser(this); } - // 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. // void DerivedType::typeIsRefined() { assert(isRefining >= 0 && isRefining <= 2 && "isRefining out of bounds!"); - if (isRefining == 2) return; // Kill recursion here... + if (isRefining == 1) return; // Kill recursion here... ++isRefining; #ifdef DEBUG_MERGE_TYPES - 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 - cerr << " typeIsREFINED user " << i << " of abstract type [" + cerr << " typeIsREFINED user " << i << "[" << ATU << "] of abstract type [" << (void*)this << " " << getDescription() << "]\n"; #endif ATU->refineAbstractType(this, this); - - // If the user didn't remove itself from the list, continue... - if (AbstractTypeUsers.size() > i && AbstractTypeUsers[i] == ATU) - ++i; } --isRefining; + +#ifndef _NDEBUG + if (!(isAbstract() || AbstractTypeUsers.empty())) + for (unsigned i = 0; i < AbstractTypeUsers.size(); ++i) { + if (AbstractTypeUsers[i] != this) { + // Debugging hook + cerr << "FOUND FAILURE\nUser: "; + AbstractTypeUsers[i]->dump(); + cerr << "\nCatch:\n"; + AbstractTypeUsers[i]->refineAbstractType(this, this); + assert(0 && "Type became concrete," + " but it still has abstract type users hanging around!"); + } + } +#endif } @@ -794,45 +978,31 @@ void DerivedType::typeIsRefined() { // concrete - this could potentially change us from an abstract type to a // concrete type. // -void MethodType::refineAbstractType(const DerivedType *OldType, - const Type *NewType) { +void FunctionType::refineAbstractType(const DerivedType *OldType, + const Type *NewType) { #ifdef DEBUG_MERGE_TYPES - cerr << "MethodTy::refineAbstractTy(" << (void*)OldType << "[" + cerr << "FunctionTy::refineAbstractTy(" << (void*)OldType << "[" << OldType->getDescription() << "], " << (void*)NewType << " [" << NewType->getDescription() << "])\n"; #endif - - if (OldType == ResultType) { + // Find the type element we are refining... + if (ResultType == OldType) { + ResultType.removeUserFromConcrete(); ResultType = NewType; - } else { - unsigned i; - for (i = 0; i < ParamTys.size(); ++i) - if (OldType == ParamTys[i]) { - ParamTys[i] = NewType; - break; - } - assert(i != ParamTys.size() && "Did not contain oldtype!"); } + for (unsigned i = 0, e = ParamTys.size(); i != e; ++i) + if (ParamTys[i] == OldType) { + ParamTys[i].removeUserFromConcrete(); + ParamTys[i] = NewType; + } - - // Notify everyone that I have changed! - if (const MethodType *MTy = MethodTypes.containsEquivalent(this)) { -#ifndef _NDEBUG - // Calculate accurate name for debugging purposes - vector TypeStack; - bool isAbstract = false, isRecursive = false; - setDescription(getTypeProps(this, TypeStack, isAbstract, isRecursive)); -#endif - -#ifdef DEBUG_MERGE_TYPES - cerr << "Type " << (void*)this << " equilivant to existing " << (void*)MTy - << " - destroying!\n"; -#endif - refineAbstractTypeTo(MTy); // Different type altogether... - return; + 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... } - setDerivedTypeProperties(); // Update the name and isAbstract - typeIsRefined(); } @@ -847,27 +1017,18 @@ void ArrayType::refineAbstractType(const DerivedType *OldType, << OldType->getDescription() << "], " << (void*)NewType << " [" << NewType->getDescription() << "])\n"; #endif - assert(OldType == ElementType && "Cannot refine from OldType!"); - ElementType = NewType; - // Notify everyone that I have changed! - if (const ArrayType *ATy = ArrayTypes.containsEquivalent(this)) { -#ifndef _NDEBUG - // Calculate accurate name for debugging purposes - vector TypeStack; - bool isAbstract = false, isRecursive = false; - setDescription(getTypeProps(this, TypeStack, isAbstract, isRecursive)); -#endif + assert(getElementType() == OldType); + ElementType.removeUserFromConcrete(); + ElementType = NewType; -#ifdef DEBUG_MERGE_TYPES - cerr << "Type " << (void*)this << " equilivant to existing " << (void*)ATy - << " - destroying!\n"; -#endif - refineAbstractTypeTo(ATy); // Different type altogether... - return; + 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... } - setDerivedTypeProperties(); // Update the name and isAbstract - typeIsRefined(); // Same type, different contents... } @@ -882,40 +1043,21 @@ void StructType::refineAbstractType(const DerivedType *OldType, << OldType->getDescription() << "], " << (void*)NewType << " [" << NewType->getDescription() << "])\n"; #endif + for (unsigned i = 0, e = ETypes.size(); i != e; ++i) + if (ETypes[i] == OldType) { + ETypes[i].removeUserFromConcrete(); - if (OldType != NewType) { - unsigned i; - for (i = 0; i < ETypes.size(); ++i) - if (OldType == ETypes[i]) { - ETypes[i] = NewType; - break; - } - assert(i != ETypes.size() && "Did not contain oldtype!"); - } - - vector ElTypes( - map_iterator(ETypes.begin(), mem_fun_ref(&PATypeHandle::get)), - map_iterator(ETypes.end() , mem_fun_ref(&PATypeHandle::get))); - - - // Notify everyone that I have changed! - if (const StructType *STy = StructTypes.containsEquivalent(this)) { -#ifndef _NDEBUG - // Calculate accurate name for debugging purposes - vector TypeStack; - bool isAbstract = false, isRecursive = false; - setDescription(getTypeProps(this, TypeStack, isAbstract, isRecursive)); -#endif + // Update old type to new type in the array... + ETypes[i] = NewType; + } -#ifdef DEBUG_MERGE_TYPES - cerr << "Type " << (void*)this << " equilivant to existing " << (void*)STy - << " - destroying!\n"; -#endif - refineAbstractTypeTo(STy); // Different type altogether... - return; + 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... } - setDerivedTypeProperties(); // Update the name and isAbstract - typeIsRefined(); // Same type, different contents... } // refineAbstractType - Called when a contained type is found to be more @@ -929,26 +1071,17 @@ void PointerType::refineAbstractType(const DerivedType *OldType, << OldType->getDescription() << "], " << (void*)NewType << " [" << NewType->getDescription() << "])\n"; #endif - assert(OldType == ValueType && "Cannot refine from OldType!"); - ValueType = NewType; - // Notify everyone that I have changed! - if (const PointerType *PTy = PointerTypes.containsEquivalent(this)) { -#ifndef _NDEBUG - // Calculate accurate name for debugging purposes - vector TypeStack; - bool isAbstract = false, isRecursive = false; - setDescription(getTypeProps(this, TypeStack, isAbstract, isRecursive)); -#endif + assert(ElementType == OldType); + ElementType.removeUserFromConcrete(); + ElementType = NewType; -#ifdef DEBUG_MERGE_TYPES - cerr << "Type " << (void*)this << " equilivant to existing " << (void*)PTy - << " - destroying!\n"; -#endif - refineAbstractTypeTo(PTy); // Different type altogether... - return; + 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... } - setDerivedTypeProperties(); // Update the name and isAbstract - typeIsRefined(); // Same type, different contents... }