diff options
author | Chris Lattner <sabre@nondot.org> | 2004-02-09 20:23:44 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2004-02-09 20:23:44 +0000 |
commit | c3b5849e92a92794939b11a8503a67068372852a (patch) | |
tree | 5a0d8ef6b455fff322155200c87ba893bcc0fe00 /lib/VMCore/Type.cpp | |
parent | 026a8ce312e512aee56fd0239f37a7caed1669dd (diff) | |
download | external_llvm-c3b5849e92a92794939b11a8503a67068372852a.zip external_llvm-c3b5849e92a92794939b11a8503a67068372852a.tar.gz external_llvm-c3b5849e92a92794939b11a8503a67068372852a.tar.bz2 |
Speed up type resolution some more. On the testcase in PR224, for example,
this speeds up a release llvm-as from 21.95s to 11.21s, because before it
would do an expensive traversal of the type-graph of every type resolved.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@11242 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/VMCore/Type.cpp')
-rw-r--r-- | lib/VMCore/Type.cpp | 35 |
1 files changed, 27 insertions, 8 deletions
diff --git a/lib/VMCore/Type.cpp b/lib/VMCore/Type.cpp index 48d3719..11b3450 100644 --- a/lib/VMCore/Type.cpp +++ b/lib/VMCore/Type.cpp @@ -526,17 +526,36 @@ static bool TypesEqual(const Type *Ty, const Type *Ty2) { 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; } @@ -622,7 +641,7 @@ public: // 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()) { |