From 8511c351dce5180d354bc49b45791ae3b2ed8a79 Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Tue, 16 Nov 2004 20:30:53 +0000
Subject: 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
---
 lib/VMCore/Type.cpp | 49 +++++++++++++++++++++++++++++++++++--------------
 1 file changed, 35 insertions(+), 14 deletions(-)

(limited to 'lib/VMCore/Type.cpp')

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
 //===----------------------------------------------------------------------===//
-- 
cgit v1.1