From 3787c95e865259feeb008eefcdf7ca65b3e9c320 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Wed, 16 Nov 2005 06:09:47 +0000 Subject: [PATCH] * Fix DerivedType::dropAllTypeUses to not change the number of types in a type when it gets refined. This allows us to hash on this crucial value. * Fix several issues in TypeMap::RefineAbstractType that prevent it from handling hash values that change correctly. * Define hashTypeStructure to not always return 0. :) This last part (which depends on the first two) speeds up gccld time on eon from 3.78s to 2.75s with a release build (a 28% speedup!). This resolves PR474. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@24372 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/VMCore/Type.cpp | 87 +++++++++++++++++++++++++++++++++------------ 1 file changed, 65 insertions(+), 22 deletions(-) diff --git a/lib/VMCore/Type.cpp b/lib/VMCore/Type.cpp index ba8830912ca..59467c2122a 100644 --- a/lib/VMCore/Type.cpp +++ b/lib/VMCore/Type.cpp @@ -471,14 +471,17 @@ OpaqueType::OpaqueType() : DerivedType(OpaqueTyID) { // 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; + + // Change the rest of the types to be intty's. It doesn't matter what we + // pick so long as it doesn't point back to this type. We choose something + // concrete to avoid overhead for adding to AbstracTypeUser lists and stuff. + for (unsigned i = 1, e = ContainedTys.size(); i != e; ++i) + ContainedTys[i] = Type::IntTy; } } @@ -680,6 +683,37 @@ static bool TypeHasCycleThroughItself(const Type *Ty) { return false; } +/// getSubElementHash - Generate a hash value for all of the SubType's of this +/// type. The hash value is guaranteed to be zero if any of the subtypes are +/// an opaque type. Otherwise we try to mix them in as well as possible, but do +/// not look at the subtype's subtype's. +static unsigned getSubElementHash(const Type *Ty) { + unsigned HashVal = 0; + for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); + I != E; ++I) { + HashVal *= 32; + const Type *SubTy = I->get(); + HashVal += SubTy->getTypeID(); + switch (SubTy->getTypeID()) { + default: break; + case Type::OpaqueTyID: return 0; // Opaque -> hash = 0 no matter what. + case Type::FunctionTyID: + HashVal ^= cast(SubTy)->getNumParams()*2 + + cast(SubTy)->isVarArg(); + break; + case Type::ArrayTyID: + HashVal ^= cast(SubTy)->getNumElements(); + break; + case Type::PackedTyID: + HashVal ^= cast(SubTy)->getNumElements(); + break; + case Type::StructTyID: + HashVal ^= cast(SubTy)->getNumElements(); + break; + } + } + return HashVal ? HashVal : 1; // Do not return zero unless opaque subty. +} //===----------------------------------------------------------------------===// // Derived Type Factory Functions @@ -697,12 +731,18 @@ protected: 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.lower_bound(Hash); + for (; I != TypesByHash.end() && I->first == Hash; ++I) { + if (I->second == Ty) { + TypesByHash.erase(I); + return; + } } - TypesByHash.erase(I); + + // This must be do to an opaque type that was resolved. Switch down to hash + // code of zero. + assert(Hash && "Didn't find type entry!"); + RemoveFromTypesByHash(0, Ty); } /// TypeBecameConcrete - When Ty gets a notification that TheType just became @@ -803,7 +843,6 @@ public: 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); @@ -819,7 +858,7 @@ public: // gets refined to the pre-existing type. // std::multimap::iterator I, E, Entry; - tie(I, E) = TypesByHash.equal_range(OldTypeHash); + tie(I, E) = TypesByHash.equal_range(NewTypeHash); Entry = E; for (; I != E; ++I) { if (I->second == Ty) { @@ -829,16 +868,23 @@ public: 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??"); + // Remove the old entry form TypesByHash. If the hash values differ + // now, remove it from the old place. Otherwise, continue scanning + // withing this hashcode to reduce work. + if (NewTypeHash != OldTypeHash) { + RemoveFromTypesByHash(OldTypeHash, Ty); + } else { + 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; } - Entry = I; + TypesByHash.erase(Entry); } - TypesByHash.erase(Entry); Ty->refineAbstractTypeTo(NewTy); return; } @@ -1122,7 +1168,7 @@ public: } static unsigned hashTypeStructure(const PointerType *PT) { - return 0; + return getSubElementHash(PT); } // Subclass should override this... to update self as usual @@ -1284,9 +1330,6 @@ void DerivedType::notifyUsesThatTypeBecameConcrete() { } } - - - // 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. -- 2.34.1