-//===-- Type.cpp - Implement the Type class ----------------------*- C++ -*--=//
+//===-- Type.cpp - Implement the Type class -------------------------------===//
//
// This file implements the Type class for the VMCore library.
//
// 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
TypeStack.pop_back(); // Remove self from stack...
- // In order to reduce the amount of repeated computation, we cache the
- // computed value for later.
- if (Ty->isAbstract())
- return AbstractTypeDescriptions[Ty] = Result;
- else
- return ConcreteTypeDescriptions[Ty] = Result;
+ return Result;
}
if (I != Map.end()) return I->second;
std::vector<const Type *> TypeStack;
- getTypeDescription(Ty, TypeStack);
- assert(Map.count(Ty) && "Type didn't get inserted!!");
- return Map[Ty];
+ return Map[Ty] = getTypeDescription(Ty, TypeStack);
}
OpaqueType::OpaqueType() : DerivedType(OpaqueTyID) {
setAbstract(true);
#ifdef DEBUG_MERGE_TYPES
- std::cerr << "Derived new type: " << getDescription() << "\n";
+ std::cerr << "Derived new type: " << *this << "\n";
#endif
}
-
-
-//===----------------------------------------------------------------------===//
-// Derived Type setDerivedTypeProperties Function
-//===----------------------------------------------------------------------===//
-
// isTypeAbstract - This is a recursive function that walks a type hierarchy
// calculating whether or not a type is abstract. Worst case it will have to do
// a lot of traversing if you have some whacko opaque types, but in most cases,
}
-// setDerivedTypeProperties - This function is used to calculate the isAbstract
-// setting for a type. The getTypeProps function does all the dirty work.
-//
-void DerivedType::setDerivedTypeProperties() {
- // If the type is currently thought to be abstract, rescan all of our subtypes
- // to see if the type has just become concrete!
- if (isAbstract())
- setAbstract(isTypeAbstract());
-}
-
-
//===----------------------------------------------------------------------===//
// Type Structural Equality Testing
//===----------------------------------------------------------------------===//
// 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.
+ // and that function types can be varargs or not. Consider this now.
if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
if (ATy->getNumElements() != cast<ArrayType>(Ty2)->getNumElements())
return false;
typedef std::map<ValType, PATypeHandle> MapTy;
MapTy Map;
public:
+ typedef typename MapTy::iterator iterator;
~TypeMap() { print("ON EXIT"); }
inline TypeClass *get(const ValType &V) {
- typename std::map<ValType, PATypeHandle>::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() ? (TypeClass*)I->second.get() : 0;
}
inline void add(const ValType &V, TypeClass *T) {
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;
+ iterator getEntryForType(TypeClass *Ty) {
+ iterator I = Map.find(ValType::get(Ty));
+ if (I == Map.end()) print("ERROR!");
+ assert(I != Map.end() && "Didn't find type entry!");
+ assert(T->second == Ty && "Type entry wrong?");
+ return I;
+ }
+
+
+ void finishRefinement(TypeClass *Ty) {
+ //const TypeClass *Ty = (const TypeClass*)TyIt->second.get();
+ for (iterator I = Map.begin(), E = Map.end(); I != E; ++I)
+ if (I->second.get() != Ty && TypesEqual(Ty, I->second.get())) {
+ assert(Ty->isAbstract() && "Replacing a non-abstract type?");
+ TypeClass *NewTy = (TypeClass*)I->second.get();
+#if 0
+ //Map.erase(TyIt); // The old entry is now dead!
+#endif
+ // Refined to a different type altogether?
+ Ty->refineAbstractTypeToInternal(NewTy, false);
+ return;
+ }
+
+ // If the type is currently thought to be abstract, rescan all of our
+ // subtypes to see if the type has just become concrete!
+ if (Ty->isAbstract())
+ Ty->setAbstract(Ty->isTypeAbstract());
+
+ // This method may be called with either an abstract or a concrete type.
+ // Concrete types might get refined if a subelement type got refined which
+ // was previously marked as abstract, but was realized to be concrete. This
+ // can happen for recursive types.
+ Ty->typeIsRefined(); // Same type, different contents...
}
// refineAbstractType - This is called when one of the contained abstract
virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
#ifdef DEBUG_MERGE_TYPES
std::cerr << "Removing Old type from Tab: " << (void*)OldTy << ", "
- << OldTy->getDescription() << " replacement == " << (void*)NewTy
- << ", " << NewTy->getDescription() << "\n";
+ << *OldTy << " replacement == " << (void*)NewTy
+ << ", " << *NewTy << "\n";
#endif
- for (typename MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I)
- if (I->second == OldTy) {
+ for (iterator I = Map.begin(), E = Map.end(); I != E; ++I)
+ if (I->second.get() == OldTy) {
// Check to see if the type just became concrete. If so, remove self
// from user list.
I->second.removeUserFromConcrete();
}
void remove(const ValType &OldVal) {
- typename MapTy::iterator I = Map.find(OldVal);
+ iterator I = Map.find(OldVal);
assert(I != Map.end() && "TypeMap::remove, element not found!");
Map.erase(I);
}
+ void remove(iterator I) {
+ assert(I != Map.end() && "Cannot remove invalid iterator pointer!");
+ Map.erase(I);
+ }
+
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 MapTy::const_iterator I = Map.begin(), E = Map.end();
+ I != E; ++I)
+ std::cerr << " " << (++i) << ". " << (void*)I->second.get() << " "
+ << *I->second.get() << "\n";
#endif
}
ArgTypes.push_back(PATypeHandle(MVT.ArgTypes[i], this));
}
+ static FunctionValType get(const FunctionType *FT);
+
// Subclass should override this... to update self as usual
virtual void doRefinement(const DerivedType *OldType, const Type *NewType) {
if (RetTy == OldType) RetTy = NewType;
// Define the actual map itself now...
static TypeMap<FunctionValType, FunctionType> FunctionTypes;
+FunctionValType FunctionValType::get(const FunctionType *FT) {
+ // Build up a FunctionValType
+ std::vector<const Type *> ParamTypes;
+ ParamTypes.reserve(FT->getParamTypes().size());
+ for (unsigned i = 0, e = FT->getParamTypes().size(); i != e; ++i)
+ ParamTypes.push_back(FT->getParamType(i));
+ return FunctionValType(FT->getReturnType(), ParamTypes, FT->isVarArg(),
+ FunctionTypes);
+}
+
+
// FunctionType::get - The factory function for the FunctionType class...
FunctionType *FunctionType::get(const Type *ReturnType,
const std::vector<const Type*> &Params,
return MT;
}
+void FunctionType::dropAllTypeUses(bool inMap) {
+#if 0
+ if (inMap) FunctionTypes.remove(FunctionTypes.getEntryForType(this));
+ // Drop all uses of other types, which might be recursive.
+#endif
+ ResultType = OpaqueType::get();
+ ParamTys.clear();
+}
+
+
//===----------------------------------------------------------------------===//
// Array Type Factory...
//
: ValTypeBase<ArrayValType, ArrayType>(AVT), ValTy(AVT.ValTy, this),
Size(AVT.Size) {}
+ static ArrayValType get(const ArrayType *AT);
+
+
// Subclass should override this... to update self as usual
virtual void doRefinement(const DerivedType *OldType, const Type *NewType) {
assert(ValTy == OldType);
static TypeMap<ArrayValType, ArrayType> ArrayTypes;
+ArrayValType ArrayValType::get(const ArrayType *AT) {
+ return ArrayValType(AT->getElementType(), AT->getNumElements(), ArrayTypes);
+}
+
+
ArrayType *ArrayType::get(const Type *ElementType, unsigned NumElements) {
assert(ElementType && "Can't get array of null types!");
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;
}
+void ArrayType::dropAllTypeUses(bool inMap) {
+#if 0
+ if (inMap) ArrayTypes.remove(ArrayTypes.getEntryForType(this));
+#endif
+ ElementType = OpaqueType::get();
+}
+
+
+
+
//===----------------------------------------------------------------------===//
// Struct Type Factory...
//
ElTypes.push_back(PATypeHandle(SVT.ElTypes[i], this));
}
+ static StructValType get(const StructType *ST);
+
// Subclass should override this... to update self as usual
virtual void doRefinement(const DerivedType *OldType, const Type *NewType) {
for (unsigned i = 0; i < ElTypes.size(); ++i)
static TypeMap<StructValType, StructType> StructTypes;
+StructValType StructValType::get(const StructType *ST) {
+ std::vector<const Type *> ElTypes;
+ ElTypes.reserve(ST->getElementTypes().size());
+ for (unsigned i = 0, e = ST->getElementTypes().size(); i != e; ++i)
+ ElTypes.push_back(ST->getElementTypes()[i]);
+
+ return StructValType(ElTypes, StructTypes);
+}
+
+
+
StructType *StructType::get(const std::vector<const Type*> &ETypes) {
StructValType STV(ETypes, StructTypes);
StructType *ST = StructTypes.get(STV);
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;
}
+void StructType::dropAllTypeUses(bool inMap) {
+#if 0
+ if (inMap) StructTypes.remove(StructTypes.getEntryForType(this));
+#endif
+ ETypes.clear();
+ ETypes.push_back(PATypeHandle(OpaqueType::get(), this));
+}
+
+
+
//===----------------------------------------------------------------------===//
// Pointer Type Factory...
//
PointerValType(const PointerValType &PVT)
: ValTypeBase<PointerValType, PointerType>(PVT), ValTy(PVT.ValTy, this) {}
+ static PointerValType get(const PointerType *PT);
+
// Subclass should override this... to update self as usual
virtual void doRefinement(const DerivedType *OldType, const Type *NewType) {
assert(ValTy == OldType);
static TypeMap<PointerValType, PointerType> PointerTypes;
+PointerValType PointerValType::get(const PointerType *PT) {
+ return PointerValType(PT->getElementType(), PointerTypes);
+}
+
+
PointerType *PointerType::get(const Type *ValueType) {
assert(ValueType && "Can't get a pointer to <null> type!");
PointerValType PVT(ValueType, PointerTypes);
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 PointerType::dropAllTypeUses(bool inMap) {
+#if 0
+ if (inMap) PointerTypes.remove(PointerTypes.getEntryForType(this));
+#endif
+ ElementType = OpaqueType::get();
+}
+
void debug_type_tables() {
FunctionTypes.dump();
ArrayTypes.dump();
#if DEBUG_MERGE_TYPES
std::cerr << " addAbstractTypeUser[" << (void*)this << ", "
- << getDescription() << "][" << AbstractTypeUsers.size()
+ << *this << "][" << AbstractTypeUsers.size()
<< "] User = " << U << "\n";
#endif
AbstractTypeUsers.push_back(U);
#ifdef DEBUG_MERGE_TYPES
std::cerr << " remAbstractTypeUser[" << (void*)this << ", "
- << getDescription() << "][" << i << "] User = " << U << "\n";
+ << *this << "][" << i << "] User = " << U << "\n";
#endif
if (AbstractTypeUsers.empty() && 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!
}
-// 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.
+// refineAbstractTypeToInternal - 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.
//
-void DerivedType::refineAbstractTypeTo(const Type *NewType) {
+void DerivedType::refineAbstractTypeToInternal(const Type *NewType, bool inMap){
assert(isAbstract() && "refineAbstractTypeTo: Current type is not abstract!");
assert(this != NewType && "Can't refine to myself!");
#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
//
addAbstractTypeUser(this);
+ // To make the situation simpler, we ask the subclass to remove this type from
+ // the type map, and to replace any type uses with uses of non-abstract types.
+ // This dramatically limits the amount of recursive type trouble we can find
+ // ourselves in.
+ dropAllTypeUses(inMap);
+
// Count the number of self uses. Stop looping when sizeof(list) == NSU.
unsigned NumSelfUses = 0;
#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";
+ << *this << "] to [" << (void*)NewTy.get() << " "
+ << *NewTy << "]!\n";
#endif
User->refineAbstractType(this, NewTy);
//
assert((NewTy == this || AbstractTypeUsers.back() == this) &&
"Only self uses should be left!");
+
+#if 0
+ assert(AbstractTypeUsers.size() == 1 && "This type should get deleted!");
+#endif
removeAbstractTypeUser(this);
}
++isRefining;
#ifdef DEBUG_MERGE_TYPES
- std::cerr << "typeIsREFINED type: " << (void*)this <<" "<<getDescription()
- << "\n";
+ std::cerr << "typeIsREFINED type: " << (void*)this << " " << *this << "\n";
#endif
// In this loop we have to be very careful not to get into infinite loops and
#ifdef DEBUG_MERGE_TYPES
std::cerr << " typeIsREFINED user " << i << "[" << ATU
<< "] of abstract type [" << (void*)this << " "
- << getDescription() << "]\n";
+ << *this << "]\n";
#endif
ATU->refineAbstractType(this, this);
}
//
void FunctionType::refineAbstractType(const DerivedType *OldType,
const Type *NewType) {
+ assert((isAbstract() || !OldType->isAbstract()) &&
+ "Refining a non-abstract type!");
#ifdef DEBUG_MERGE_TYPES
std::cerr << "FunctionTy::refineAbstractTy(" << (void*)OldType << "["
- << OldType->getDescription() << "], " << (void*)NewType << " ["
- << NewType->getDescription() << "])\n";
+ << *OldType << "], " << (void*)NewType << " ["
+ << *NewType << "])\n";
#endif
+
+ // Look up our current type map entry..
+#if 0
+ TypeMap<FunctionValType, FunctionType>::iterator TMI =
+ FunctionTypes.getEntryForType(this);
+#endif
+
// Find the type element we are refining...
if (ResultType == OldType) {
ResultType.removeUserFromConcrete();
ParamTys[i] = 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...
- }
+ FunctionTypes.finishRefinement(this);
}
//
void ArrayType::refineAbstractType(const DerivedType *OldType,
const Type *NewType) {
+ assert((isAbstract() || !OldType->isAbstract()) &&
+ "Refining a non-abstract type!");
#ifdef DEBUG_MERGE_TYPES
std::cerr << "ArrayTy::refineAbstractTy(" << (void*)OldType << "["
- << OldType->getDescription() << "], " << (void*)NewType << " ["
- << NewType->getDescription() << "])\n";
+ << *OldType << "], " << (void*)NewType << " ["
+ << *NewType << "])\n";
+#endif
+
+#if 0
+ // Look up our current type map entry..
+ TypeMap<ArrayValType, ArrayType>::iterator TMI =
+ ArrayTypes.getEntryForType(this);
#endif
assert(getElementType() == OldType);
ElementType.removeUserFromConcrete();
ElementType = NewType;
- 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...
- }
+ ArrayTypes.finishRefinement(this);
}
//
void StructType::refineAbstractType(const DerivedType *OldType,
const Type *NewType) {
+ assert((isAbstract() || !OldType->isAbstract()) &&
+ "Refining a non-abstract type!");
#ifdef DEBUG_MERGE_TYPES
std::cerr << "StructTy::refineAbstractTy(" << (void*)OldType << "["
- << OldType->getDescription() << "], " << (void*)NewType << " ["
- << NewType->getDescription() << "])\n";
+ << *OldType << "], " << (void*)NewType << " ["
+ << *NewType << "])\n";
#endif
+
+#if 0
+ // Look up our current type map entry..
+ TypeMap<StructValType, StructType>::iterator TMI =
+ StructTypes.getEntryForType(this);
+#endif
+
for (int i = ETypes.size()-1; i >= 0; --i)
if (ETypes[i] == OldType) {
ETypes[i].removeUserFromConcrete();
ETypes[i] = 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...
- }
+ StructTypes.finishRefinement(this);
}
// refineAbstractType - Called when a contained type is found to be more
//
void PointerType::refineAbstractType(const DerivedType *OldType,
const Type *NewType) {
+ assert((isAbstract() || !OldType->isAbstract()) &&
+ "Refining a non-abstract type!");
#ifdef DEBUG_MERGE_TYPES
std::cerr << "PointerTy::refineAbstractTy(" << (void*)OldType << "["
- << OldType->getDescription() << "], " << (void*)NewType << " ["
- << NewType->getDescription() << "])\n";
+ << *OldType << "], " << (void*)NewType << " ["
+ << *NewType << "])\n";
+#endif
+
+#if 0
+ // Look up our current type map entry..
+ TypeMap<PointerValType, PointerType>::iterator TMI =
+ PointerTypes.getEntryForType(this);
#endif
assert(ElementType == OldType);
ElementType.removeUserFromConcrete();
ElementType = NewType;
- 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...
- }
+ PointerTypes.finishRefinement(this);
}