Make the PATypeHolder use a simple union-find implementation to handle

merging of types.  This makes it MUCH more efficient than before, also
making things simpler.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8833 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 94 insertions, 40 deletions

diff --git a/include/llvm/AbstractTypeUser.h b/include/llvm/AbstractTypeUser.h
index 64fcd33..b9e5f1c 100644
--- a/include/llvm/AbstractTypeUser.h
+++ b/include/llvm/AbstractTypeUser.h
@@ -61,9 +61,9 @@ public:
 };
 
 
-// PATypeHandle - Handle to a Type subclass.  This class is used to keep the use
-// list of abstract types up-to-date.
-//
+/// PATypeHandle - Handle to a Type subclass.  This class is used to keep the
+/// use list of abstract types up-to-date.
+///
 class PATypeHandle {
   const Type *Ty;
   AbstractTypeUser * const User;
@@ -123,50 +123,43 @@ public:
 };
 
 
-// PATypeHolder - Holder class for a potentially abstract type.  This functions
-// as both a handle (as above) and an AbstractTypeUser.  It uses the callback to
-// keep its pointer member updated to the current version of the type.
-//
-class PATypeHolder : public AbstractTypeUser {
-  PATypeHandle Handle;
+/// PATypeHolder - Holder class for a potentially abstract type.  This uses
+/// efficient union-find techniques to handle dynamic type resolution.  Unless
+/// you need to do custom processing when types are resolved, you should always
+/// use PATypeHolders in preference to PATypeHandles.
+///
+class PATypeHolder {
+  mutable const Type *Ty;
 public:
-  PATypeHolder(const Type *ty) : Handle(ty, this) {}
-  PATypeHolder(const PATypeHolder &T) : AbstractTypeUser(), Handle(T, this) {}
+  PATypeHolder(const Type *ty) : Ty(ty) {
+    addRef();
+  }
+  PATypeHolder(const PATypeHolder &T) : Ty(T.Ty) {
+    addRef();
+  }
 
-  operator const Type *() const { return Handle; }
-  const Type *get() const { return Handle; }
+  operator const Type *() const { return get(); }
+  const Type *get() const;
 
   // operator-> - Allow user to dereference handle naturally...
-  inline const Type *operator->() const { return Handle; }
-
-  // refineAbstractType - All we do is update our PATypeHandle member to point
-  // to the new type.
-  //
-  virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
-    assert(get() == (const Type*)OldTy && "Can't refine to unknown value!");
-
-    // Check to see if the type just became concrete.  If so, we have to
-    // removeUser to get off its AbstractTypeUser list
-    Handle.removeUserFromConcrete();
-
-    if ((const Type*)OldTy != NewTy)
-      Handle.operator=(NewTy);
-  }
+  const Type *operator->() const { return get(); }
 
   // operator= - Allow assignment to handle
   const Type *operator=(const Type *ty) {
-    return Handle = ty;
-  }
-
-  // operator= - Allow assignment to handle
-  const Type *operator=(const PATypeHandle &T) {
-    return Handle = T;
+    if (Ty != ty) {   // Don't accidentally drop last ref to Ty.
+      dropRef();
+      Ty = ty;
+      addRef();
+    }
+    return get();
   }
   const Type *operator=(const PATypeHolder &H) {
-    return Handle = H;
+    return operator=(H.Ty);
   }
 
-  void dump() const;
+private:
+  void addRef();
+  void dropRef();
 };
 
 #endif
diff --git a/include/llvm/DerivedTypes.h b/include/llvm/DerivedTypes.h
index 73587b4..5ed3045 100644
--- a/include/llvm/DerivedTypes.h
+++ b/include/llvm/DerivedTypes.h
@@ -20,7 +20,14 @@ class StructValType;
 class PointerValType;
 
 class DerivedType : public Type, public AbstractTypeUser {
-  char isRefining;                                   // Used for recursive types
+  /// RefCount - This counts the number of PATypeHolders that are pointing to
+  /// this type.  When this number falls to zero, if the type is abstract and
+  /// has no AbstractTypeUsers, the type is deleted.
+  ///
+  mutable unsigned RefCount;
+  
+  // isRefining - Used for recursive types
+  char isRefining;
 
   // AbstractTypeUsers - Implement a list of the users that need to be notified
   // if I am a type, and I get resolved into a more concrete type.
@@ -29,8 +36,7 @@ class DerivedType : public Type, public AbstractTypeUser {
   mutable std::vector<AbstractTypeUser *> AbstractTypeUsers;
 
 protected:
-  inline DerivedType(PrimitiveID id) : Type("", id) {
-    isRefining = 0;
+  DerivedType(PrimitiveID id) : Type("", id), RefCount(0), isRefining(0) {
   }
   ~DerivedType() {
     assert(AbstractTypeUsers.empty());
@@ -61,7 +67,10 @@ public:
   // addAbstractTypeUser - Notify an abstract type that there is a new user of
   // it.  This function is called primarily by the PATypeHandle class.
   //
-  void addAbstractTypeUser(AbstractTypeUser *U) const;
+  void addAbstractTypeUser(AbstractTypeUser *U) const {
+    assert(isAbstract() && "addAbstractTypeUser: Current type not abstract!");
+    AbstractTypeUsers.push_back(U);
+  }
 
   // removeAbstractTypeUser - Notify an abstract type that a user of the class
   // no longer has a handle to the type.  This function is called primarily by
@@ -80,6 +89,22 @@ public:
     refineAbstractTypeToInternal(NewType, true);
   }
 
+  void addRef() const {
+    assert(isAbstract() && "Cannot add a reference to a non-abstract type!");
+    ++RefCount;
+  }
+
+  void dropRef() const {
+    assert(isAbstract() && "Cannot drop a refernce to a non-abstract type!");
+    assert(RefCount && "No objects are currently referencing this object!");
+
+    // If this is the last PATypeHolder using this object, and there are no
+    // PATypeHandles using it, the type is dead, delete it now.
+    if (--RefCount == 0 && AbstractTypeUsers.empty())
+      delete this;
+  }
+
+
   void dump() const { Value::dump(); }
 
   // Methods for support type inquiry through isa, cast, and dyn_cast:
@@ -453,4 +478,26 @@ inline void PATypeHandle::removeUserFromConcrete() {
     cast<DerivedType>(Ty)->removeAbstractTypeUser(User);
 }
 
+// Define inline methods for PATypeHolder...
+
+inline void PATypeHolder::addRef() {
+  if (Ty->isAbstract())
+    cast<DerivedType>(Ty)->addRef();
+}
+
+inline void PATypeHolder::dropRef() {
+  if (Ty->isAbstract())
+    cast<DerivedType>(Ty)->dropRef();
+}
+
+/// get - This implements the forwarding part of the union-find algorithm for
+/// abstract types.  Before every access to the Type*, we check to see if the
+/// type we are pointing to is forwarding to a new type.  If so, we drop our
+/// reference to the type.
+inline const Type* PATypeHolder::get() const {
+  const Type *NewTy = Ty->getForwardedType();
+  if (!NewTy) return Ty;
+  return *const_cast<PATypeHolder*>(this) = NewTy;
+}
+
 #endif
diff --git a/include/llvm/Type.h b/include/llvm/Type.h
index 30949a6..5900b40 100644
--- a/include/llvm/Type.h
+++ b/include/llvm/Type.h
@@ -73,6 +73,7 @@ private:
   unsigned    UID;       // The unique ID number for this class
   bool        Abstract;  // True if type contains an OpaqueType
 
+  const Type *getForwardedTypeInternal() const;
 protected:
   /// ctor is protected, so only subclasses can create Type objects...
   Type(const std::string &Name, PrimitiveID id);
@@ -90,6 +91,12 @@ protected:
   /// isTypeAbstract - This method is used to calculate the Abstract bit.
   ///
   bool isTypeAbstract();
+
+  /// ForwardType - This field is used to implement the union find scheme for
+  /// abstract types.  When types are refined to other types, this field is set
+  /// to the more refined type.  Only abstract types can be forwarded.
+  mutable const Type *ForwardType;
+
 public:
   virtual void print(std::ostream &O) const;
 
@@ -177,6 +184,13 @@ public:
   ///
   unsigned getPrimitiveSize() const;
 
+  /// getForwaredType - Return the type that this type has been resolved to if
+  /// it has been resolved to anything.  This is used to implement the
+  /// union-find algorithm for type resolution.
+  const Type *getForwardedType() const {
+    if (!ForwardType) return 0;
+    return getForwardedTypeInternal();
+  }
 
   //===--------------------------------------------------------------------===//
   // Type Iteration support