diff options
author | Chris Lattner <sabre@nondot.org> | 2004-11-16 20:30:53 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2004-11-16 20:30:53 +0000 |
commit | 8511c351dce5180d354bc49b45791ae3b2ed8a79 (patch) | |
tree | 41835d2a6e709faacf5142f6266c7ff9353b4d16 /lib/VMCore/Type.cpp | |
parent | a63acbfeab516203849fced87a036f236babcea5 (diff) | |
download | external_llvm-8511c351dce5180d354bc49b45791ae3b2ed8a79.zip external_llvm-8511c351dce5180d354bc49b45791ae3b2ed8a79.tar.gz external_llvm-8511c351dce5180d354bc49b45791ae3b2ed8a79.tar.bz2 |
Make this function work with non-abstract types.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@17905 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/VMCore/Type.cpp')
-rw-r--r-- | lib/VMCore/Type.cpp | 49 |
1 files changed, 35 insertions, 14 deletions
diff --git a/lib/VMCore/Type.cpp b/lib/VMCore/Type.cpp index 02b723f..94e77bf 100644 --- a/lib/VMCore/Type.cpp +++ b/lib/VMCore/Type.cpp @@ -585,40 +585,61 @@ 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, +// AbstractTypeHasCycleThrough - 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 AbstractTypeHasCycleThrough(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); + if (!VisitedTypes.insert(CurTy).second) + return false; // Already been here. for (Type::subtype_iterator I = CurTy->subtype_begin(), E = CurTy->subtype_end(); I != E; ++I) - if (TypeHasCycleThrough(TargetTy, *I, VisitedTypes)) + if (AbstractTypeHasCycleThrough(TargetTy, *I, VisitedTypes)) return true; return false; } +static bool ConcreteTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy, + std::set<const Type*> &VisitedTypes) { + if (TargetTy == CurTy) return true; + + if (!VisitedTypes.insert(CurTy).second) + return false; // Already been here. + + for (Type::subtype_iterator I = CurTy->subtype_begin(), + E = CurTy->subtype_end(); I != E; ++I) + if (ConcreteTypeHasCycleThrough(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) - if (TypeHasCycleThrough(Ty, *I, VisitedTypes)) - return true; + + if (Ty->isAbstract()) { // Optimized case for abstract types. + for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); + I != E; ++I) + if (AbstractTypeHasCycleThrough(Ty, *I, VisitedTypes)) + return true; + } else { + for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); + I != E; ++I) + if (ConcreteTypeHasCycleThrough(Ty, *I, VisitedTypes)) + return true; + } return false; } + + //===----------------------------------------------------------------------===// // Derived Type Factory Functions //===----------------------------------------------------------------------===// |