#include "Support/DepthFirstIterator.h"
#include "Support/StringExtras.h"
#include "Support/STLExtras.h"
-#include "Support/Statistic.h"
#include <algorithm>
-
using namespace llvm;
-static Statistic<> NumSlowTypes("type", "num slow types");
-static Statistic<> NumTypeEqualsCalls("type", "num typeequals calls");
-static Statistic<> NumTypeEquals("type", "num types actually equal");
-
// DEBUG_MERGE_TYPES - Enable this #define to see how and when derived types are
// created and later destroyed, all in an effort to make sure that there is only
// a single canonical version of a type.
//
//#define DEBUG_MERGE_TYPES 1
+AbstractTypeUser::~AbstractTypeUser() {}
//===----------------------------------------------------------------------===//
// Type Class Implementation
static std::map<const Type*, std::string> AbstractTypeDescriptions;
Type::Type(const std::string &name, PrimitiveID id)
- : Value(Type::TypeTy, Value::TypeVal), ForwardType(0) {
+ : Value(Type::TypeTy, Value::TypeVal), RefCount(0), ForwardType(0) {
if (!name.empty())
ConcreteTypeDescriptions[this] = name;
ID = id;
}
}
+/// getUnsignedVersion - If this is an integer type, return the unsigned
+/// variant of this type. For example int -> uint.
+const Type *Type::getUnsignedVersion() const {
+ switch (getPrimitiveID()) {
+ 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 (getPrimitiveID()) {
+ 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.
bool StructType::indexValid(const Value *V) const {
// Structure indexes require unsigned integer constants.
- if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(V))
- return CU->getValue() < ContainedTys.size();
+ if (V->getType() == Type::UIntTy)
+ if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(V))
+ return CU->getValue() < ContainedTys.size();
return false;
}
// element. For a structure type, this must be a constant value...
//
const Type *StructType::getTypeAtIndex(const Value *V) const {
- assert(isa<Constant>(V) && "Structure index must be a constant!!");
+ assert(indexValid(V) && "Invalid structure index!");
unsigned Idx = cast<ConstantUInt>(V)->getValue();
- assert(Idx < ContainedTys.size() && "Structure index out of range!");
- assert(indexValid(V) && "Invalid structure index!"); // Duplicate check
return ContainedTys[Idx];
}
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!!");
+ assert(Types[i] != Type::VoidTy && "Void type for structure field!!");
ContainedTys.push_back(PATypeHandle(Types[i], this));
isAbstract |= Types[i]->isAbstract();
}
return TypesEqual(Ty, Ty2, EqTypes);
}
+// TypeHasCycleThrough - 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 TypeHasCycleThrough(const Type *TargetTy, const Type *CurTy,
+ std::set<const Type*> &VisitedTypes) {
+ if (TargetTy == CurTy) return true;
+ if (!CurTy->isAbstract()) return false;
+
+ std::set<const Type*>::iterator VTI = VisitedTypes.lower_bound(CurTy);
+ if (VTI != VisitedTypes.end() && *VTI == CurTy)
+ return false;
+ VisitedTypes.insert(VTI, CurTy);
+
+ for (Type::subtype_iterator I = CurTy->subtype_begin(),
+ E = CurTy->subtype_end(); I != E; ++I)
+ if (TypeHasCycleThrough(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) {
+ assert(Ty->isAbstract() && "This code assumes that Ty was abstract!");
std::set<const Type*> VisitedTypes;
- for (Type::subtype_iterator I = Ty->subtype_begin(),
- E = Ty->subtype_end(); I != E; ++I)
- for (df_ext_iterator<const Type *, std::set<const Type*> >
- DFI = df_ext_begin(I->get(), VisitedTypes),
- E = df_ext_end(I->get(), VisitedTypes); DFI != E; ++DFI)
- if (*DFI == Ty)
- return true; // Found a cycle through ty!
+ for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
+ I != E; ++I)
+ if (TypeHasCycleThrough(Ty, *I, VisitedTypes))
+ return true;
return false;
}
// 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.
- bool TypeHasCycle = TypeHasCycleThroughItself(Ty);
+ bool TypeHasCycle = Ty->isAbstract() && TypeHasCycleThroughItself(Ty);
if (!TypeHasCycle) {
iterator I = Map.find(ValType::get(Ty));
if (I != Map.end()) {
}
} else {
- ++NumSlowTypes;
-
// 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.
tie(I, E) = TypesByHash.equal_range(TypeHash);
Entry = E;
for (; I != E; ++I) {
- ++NumTypeEqualsCalls;
if (I->second != Ty) {
if (TypesEqual(Ty, I->second)) {
- ++NumTypeEquals;
-
assert(Ty->isAbstract() && "Replacing a non-abstract type?");
TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get());
<< *this << "][" << i << "] User = " << U << "\n";
#endif
- if (AbstractTypeUsers.empty() && RefCount == 0 && isAbstract()) {
+ if (AbstractTypeUsers.empty() && getRefCount() == 0 && isAbstract()) {
#ifdef DEBUG_MERGE_TYPES
std::cerr << "DELETEing unused abstract type: <" << *this
<< ">[" << (void*)this << "]" << "\n";