Remove obsolete method

[oota-llvm.git] / lib / VMCore / Type.cpp

diff --git a/lib/VMCore/Type.cpp b/lib/VMCore/Type.cpp
index 48d3719665be06bfeb7dde2fd2a0128fb8e8ef37..9a40457600df56f017f648d4b139d2b7b56a4298 100644 (file)
--- a/lib/VMCore/Type.cpp
+++ b/lib/VMCore/Type.cpp
@@ -17,15 +17,9 @@
 #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.
@@ -526,17 +520,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 +635,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()) {
@@ -638,8 +651,6 @@ public:
       }
       
     } 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.
@@ -648,11 +659,8 @@ public:
       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());