Land the long talked about "type system rewrite" patch. This

patch brings numerous advantages to LLVM.  One way to look at it
is through diffstat:
 109 files changed, 3005 insertions(+), 5906 deletions(-)

Removing almost 3K lines of code is a good thing.  Other advantages
include:

1. Value::getType() is a simple load that can be CSE'd, not a mutating
   union-find operation.
2. Types a uniqued and never move once created, defining away PATypeHolder.
3. Structs can be "named" now, and their name is part of the identity that
   uniques them.  This means that the compiler doesn't merge them structurally
   which makes the IR much less confusing.
4. Now that there is no way to get a cycle in a type graph without a named
   struct type, "upreferences" go away.
5. Type refinement is completely gone, which should make LTO much MUCH faster
   in some common cases with C++ code.
6. Types are now generally immutable, so we can use "Type *" instead 
   "const Type *" everywhere.

Downsides of this patch are that it removes some functions from the C API,
so people using those will have to upgrade to (not yet added) new API.  
"LLVM 3.0" is the right time to do this.

There are still some cleanups pending after this, this patch is large enough
as-is.




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

1 files changed, 88 insertions, 244 deletions

diff --git a/include/llvm/Type.h b/include/llvm/Type.h
index 61101548a5..da11d98e26 100644
--- a/include/llvm/Type.h
+++ b/include/llvm/Type.h
@@ -15,19 +15,17 @@
 #ifndef LLVM_TYPE_H
 #define LLVM_TYPE_H
 
-#include "llvm/AbstractTypeUser.h"
 #include "llvm/Support/Casting.h"
-#include <vector>
 
 namespace llvm {
 
 class DerivedType;
 class PointerType;
 class IntegerType;
-class TypeMapBase;
 class raw_ostream;
 class Module;
 class LLVMContext;
+class LLVMContextImpl;
 template<class GraphType> struct GraphTraits;
 
 /// The instances of the Type class are immutable: once they are created,
@@ -35,29 +33,10 @@ template<class GraphType> struct GraphTraits;
 /// type is ever created.  Thus seeing if two types are equal is a matter of
 /// doing a trivial pointer comparison. To enforce that no two equal instances
 /// are created, Type instances can only be created via static factory methods 
-/// in class Type and in derived classes.
+/// in class Type and in derived classes.  Once allocated, Types are never
+/// free'd.
 /// 
-/// Once allocated, Types are never free'd, unless they are an abstract type
-/// that is resolved to a more concrete type.
-/// 
-/// Types themself don't have a name, and can be named either by:
-/// - using SymbolTable instance, typically from some Module,
-/// - using convenience methods in the Module class (which uses module's 
-///    SymbolTable too).
-///
-/// Opaque types are simple derived types with no state.  There may be many
-/// different Opaque type objects floating around, but two are only considered
-/// identical if they are pointer equals of each other.  This allows us to have
-/// two opaque types that end up resolving to different concrete types later.
-///
-/// Opaque types are also kinda weird and scary and different because they have
-/// to keep a list of uses of the type.  When, through linking, parsing, or
-/// bitcode reading, they become resolved, they need to find and update all
-/// users of the unknown type, causing them to reference a new, more concrete
-/// type.  Opaque types are deleted when their use list dwindles to zero users.
-///
-/// @brief Root of type hierarchy
-class Type : public AbstractTypeUser {
+class Type {
 public:
   //===--------------------------------------------------------------------===//
   /// Definitions of all of the base types for the Type system.  Based on this
@@ -85,8 +64,7 @@ public:
     StructTyID,      ///< 11: Structures
     ArrayTyID,       ///< 12: Arrays
     PointerTyID,     ///< 13: Pointers
-    OpaqueTyID,      ///< 14: Opaque: type with unknown structure
-    VectorTyID,      ///< 15: SIMD 'packed' format, or other vector type
+    VectorTyID,      ///< 14: SIMD 'packed' format, or other vector type
 
     NumTypeIDs,                         // Must remain as last defined ID
     LastPrimitiveTyID = X86_MMXTyID,
@@ -94,86 +72,42 @@ public:
   };
 
 private:
-  TypeID   ID : 8;    // The current base type of this type.
-  bool     Abstract : 1;  // True if type contains an OpaqueType
-  unsigned SubclassData : 23; //Space for subclasses to store data
-
-  /// 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.  This is only sensical for
-  /// derived types.
-  ///
-  mutable unsigned RefCount;
-
   /// Context - This refers to the LLVMContext in which this type was uniqued.
   LLVMContext &Context;
-  friend class LLVMContextImpl;
 
-  const Type *getForwardedTypeInternal() const;
-
-  // When the last reference to a forwarded type is removed, it is destroyed.
-  void destroy() const;
+  TypeID   ID : 8;            // The current base type of this type.
+  unsigned SubclassData : 24; // Space for subclasses to store data
 
 protected:
-  explicit Type(LLVMContext &C, TypeID id) :
-                             ID(id), Abstract(false), SubclassData(0),
-                             RefCount(0), Context(C),
-                             ForwardType(0), NumContainedTys(0),
-                             ContainedTys(0) {}
-  virtual ~Type() {
-    assert(AbstractTypeUsers.empty() && "Abstract types remain");
-  }
-
-  /// Types can become nonabstract later, if they are refined.
-  ///
-  inline void setAbstract(bool Val) { Abstract = Val; }
-
-  unsigned getRefCount() const { return RefCount; }
+  friend class LLVMContextImpl;
+  explicit Type(LLVMContext &C, TypeID tid)
+    : Context(C), ID(tid), SubclassData(0),
+      NumContainedTys(0), ContainedTys(0) {}
+  ~Type() {}
 
   unsigned getSubclassData() const { return SubclassData; }
-  void setSubclassData(unsigned val) { SubclassData = val; }
-
-  /// 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;
-
-
-  /// 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.
-  ///
-  mutable std::vector<AbstractTypeUser *> AbstractTypeUsers;
+  void setSubclassData(unsigned val) {
+    SubclassData = val;
+    // Ensure we don't have any accidental truncation.
+    assert(SubclassData == val && "Subclass data too large for field");
+  }
 
-  /// NumContainedTys - Keeps track of how many PATypeHandle instances there
-  /// are at the end of this type instance for the list of contained types. It
-  /// is the subclasses responsibility to set this up. Set to 0 if there are no
-  /// contained types in this type.
+  /// NumContainedTys - Keeps track of how many Type*'s there are in the
+  /// ContainedTys list.
   unsigned NumContainedTys;
 
-  /// ContainedTys - A pointer to the array of Types (PATypeHandle) contained 
-  /// by this Type.  For example, this includes the arguments of a function 
-  /// type, the elements of a structure, the pointee of a pointer, the element
-  /// type of an array, etc.  This pointer may be 0 for types that don't 
-  /// contain other types (Integer, Double, Float).  In general, the subclass 
-  /// should arrange for space for the PATypeHandles to be included in the 
-  /// allocation of the type object and set this pointer to the address of the 
-  /// first element. This allows the Type class to manipulate the ContainedTys 
-  /// without understanding the subclass's placement for this array.  keeping 
-  /// it here also allows the subtype_* members to be implemented MUCH more 
-  /// efficiently, and dynamically very few types do not contain any elements.
-  PATypeHandle *ContainedTys;
+  /// ContainedTys - A pointer to the array of Types contained by this Type.
+  /// For example, this includes the arguments of a function type, the elements
+  /// of a structure, the pointee of a pointer, the element type of an array,
+  /// etc.  This pointer may be 0 for types that don't contain other types
+  /// (Integer, Double, Float).
+  Type * const *ContainedTys;
 
 public:
   void print(raw_ostream &O) const;
-
-  /// @brief Debugging support: print to stderr
   void dump() const;
 
-  /// @brief Debugging support: print to stderr (use type names from context
-  /// module).
-  void dump(const Module *Context) const;
-
-  /// getContext - Fetch the LLVMContext in which this type was uniqued.
+  /// getContext - Return the LLVMContext in which this type was uniqued.
   LLVMContext &getContext() const { return Context; }
 
   //===--------------------------------------------------------------------===//
@@ -205,8 +139,10 @@ public:
 
   /// isFloatingPointTy - Return true if this is one of the five floating point
   /// types
-  bool isFloatingPointTy() const { return ID == FloatTyID || ID == DoubleTyID ||
-      ID == X86_FP80TyID || ID == FP128TyID || ID == PPC_FP128TyID; }
+  bool isFloatingPointTy() const {
+    return ID == FloatTyID || ID == DoubleTyID ||
+      ID == X86_FP80TyID || ID == FP128TyID || ID == PPC_FP128TyID;
+  }
 
   /// isX86_MMXTy - Return true if this is X86 MMX.
   bool isX86_MMXTy() const { return ID == X86_MMXTyID; }
@@ -249,19 +185,10 @@ public:
   ///
   bool isPointerTy() const { return ID == PointerTyID; }
 
-  /// isOpaqueTy - True if this is an instance of OpaqueType.
-  ///
-  bool isOpaqueTy() const { return ID == OpaqueTyID; }
-
   /// isVectorTy - True if this is an instance of VectorType.
   ///
   bool isVectorTy() const { return ID == VectorTyID; }
 
-  /// isAbstract - True if the type is either an Opaque type, or is a derived
-  /// type that includes an opaque type somewhere in it.
-  ///
-  inline bool isAbstract() const { return Abstract; }
-
   /// canLosslesslyBitCastTo - Return true if this type could be converted 
   /// with a lossless BitCast to type 'Ty'. For example, i8* to i32*. BitCasts 
   /// are valid for types of the same size only where no re-interpretation of 
@@ -276,24 +203,22 @@ public:
   /// Here are some useful little methods to query what type derived types are
   /// Note that all other types can just compare to see if this == Type::xxxTy;
   ///
-  inline bool isPrimitiveType() const { return ID <= LastPrimitiveTyID; }
-  inline bool isDerivedType()   const { return ID >= FirstDerivedTyID; }
+  bool isPrimitiveType() const { return ID <= LastPrimitiveTyID; }
+  bool isDerivedType()   const { return ID >= FirstDerivedTyID; }
 
   /// isFirstClassType - Return true if the type is "first class", meaning it
   /// is a valid type for a Value.
   ///
-  inline bool isFirstClassType() const {
-    // There are more first-class kinds than non-first-class kinds, so a
-    // negative test is simpler than a positive one.
-    return ID != FunctionTyID && ID != VoidTyID && ID != OpaqueTyID;
+  bool isFirstClassType() const {
+    return ID != FunctionTyID && ID != VoidTyID;
   }
 
   /// isSingleValueType - Return true if the type is a valid type for a
-  /// virtual register in codegen.  This includes all first-class types
-  /// except struct and array types.
+  /// register in codegen.  This includes all first-class types except struct
+  /// and array types.
   ///
-  inline bool isSingleValueType() const {
-    return (ID != VoidTyID && ID <= LastPrimitiveTyID) ||
+  bool isSingleValueType() const {
+    return (ID != VoidTyID && isPrimitiveType()) ||
             ID == IntegerTyID || ID == PointerTyID || ID == VectorTyID;
   }
 
@@ -302,7 +227,7 @@ public:
   /// extractvalue instruction. This includes struct and array types, but
   /// does not include vector types.
   ///
-  inline bool isAggregateType() const {
+  bool isAggregateType() const {
     return ID == StructTyID || ID == ArrayTyID;
   }
 
@@ -319,9 +244,8 @@ public:
     // it doesn't have a size.
     if (ID != StructTyID && ID != ArrayTyID && ID != VectorTyID)
       return false;
-    // If it is something that can have a size and it's concrete, it definitely
-    // has a size, otherwise we have to try harder to decide.
-    return !isAbstract() || isSizedDerivedType();
+    // Otherwise we have to try harder to decide.
+    return isSizedDerivedType();
   }
 
   /// getPrimitiveSizeInBits - Return the basic size of this type if it is a
@@ -346,23 +270,14 @@ public:
   /// have a stable mantissa (e.g. ppc long double), this method returns -1.
   int getFPMantissaWidth() const;
 
-  /// getForwardedType - 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, and shouldn't be used by general
-  /// purpose clients.
-  const Type *getForwardedType() const {
-    if (!ForwardType) return 0;
-    return getForwardedTypeInternal();
-  }
-
   /// getScalarType - If this is a vector type, return the element type,
-  /// otherwise return this.
+  /// otherwise return 'this'.
   const Type *getScalarType() const;
 
   //===--------------------------------------------------------------------===//
-  // Type Iteration support
+  // Type Iteration support.
   //
-  typedef PATypeHandle *subtype_iterator;
+  typedef Type * const *subtype_iterator;
   subtype_iterator subtype_begin() const { return ContainedTys; }
   subtype_iterator subtype_end() const { return &ContainedTys[NumContainedTys];}
 
@@ -370,9 +285,9 @@ public:
   /// (defined a the end of the file).  For derived types, this returns the
   /// types 'contained' in the derived type.
   ///
-  const Type *getContainedType(unsigned i) const {
+  Type *getContainedType(unsigned i) const {
     assert(i < NumContainedTys && "Index out of range!");
-    return ContainedTys[i].get();
+    return ContainedTys[i];
   }
 
   /// getNumContainedTypes - Return the number of types in the derived type.
@@ -385,140 +300,77 @@ public:
   //
 
   /// getPrimitiveType - Return a type based on an identifier.
-  static const Type *getPrimitiveType(LLVMContext &C, TypeID IDNumber);
+  static Type *getPrimitiveType(LLVMContext &C, TypeID IDNumber);
 
   //===--------------------------------------------------------------------===//
-  // These are the builtin types that are always available...
+  // These are the builtin types that are always available.
   //
-  static const Type *getVoidTy(LLVMContext &C);
-  static const Type *getLabelTy(LLVMContext &C);
-  static const Type *getFloatTy(LLVMContext &C);
-  static const Type *getDoubleTy(LLVMContext &C);
-  static const Type *getMetadataTy(LLVMContext &C);
-  static const Type *getX86_FP80Ty(LLVMContext &C);
-  static const Type *getFP128Ty(LLVMContext &C);
-  static const Type *getPPC_FP128Ty(LLVMContext &C);
-  static const Type *getX86_MMXTy(LLVMContext &C);
-  static const IntegerType *getIntNTy(LLVMContext &C, unsigned N);
-  static const IntegerType *getInt1Ty(LLVMContext &C);
-  static const IntegerType *getInt8Ty(LLVMContext &C);
-  static const IntegerType *getInt16Ty(LLVMContext &C);
-  static const IntegerType *getInt32Ty(LLVMContext &C);
-  static const IntegerType *getInt64Ty(LLVMContext &C);
+  static Type *getVoidTy(LLVMContext &C);
+  static Type *getLabelTy(LLVMContext &C);
+  static Type *getFloatTy(LLVMContext &C);
+  static Type *getDoubleTy(LLVMContext &C);
+  static Type *getMetadataTy(LLVMContext &C);
+  static Type *getX86_FP80Ty(LLVMContext &C);
+  static Type *getFP128Ty(LLVMContext &C);
+  static Type *getPPC_FP128Ty(LLVMContext &C);
+  static Type *getX86_MMXTy(LLVMContext &C);
+  static IntegerType *getIntNTy(LLVMContext &C, unsigned N);
+  static IntegerType *getInt1Ty(LLVMContext &C);
+  static IntegerType *getInt8Ty(LLVMContext &C);
+  static IntegerType *getInt16Ty(LLVMContext &C);
+  static IntegerType *getInt32Ty(LLVMContext &C);
+  static IntegerType *getInt64Ty(LLVMContext &C);
 
   //===--------------------------------------------------------------------===//
   // Convenience methods for getting pointer types with one of the above builtin
   // types as pointee.
   //
-  static const PointerType *getFloatPtrTy(LLVMContext &C, unsigned AS = 0);
-  static const PointerType *getDoublePtrTy(LLVMContext &C, unsigned AS = 0);
-  static const PointerType *getX86_FP80PtrTy(LLVMContext &C, unsigned AS = 0);
-  static const PointerType *getFP128PtrTy(LLVMContext &C, unsigned AS = 0);
-  static const PointerType *getPPC_FP128PtrTy(LLVMContext &C, unsigned AS = 0);
-  static const PointerType *getX86_MMXPtrTy(LLVMContext &C, unsigned AS = 0);
-  static const PointerType *getIntNPtrTy(LLVMContext &C, unsigned N,
-                                         unsigned AS = 0);
-  static const PointerType *getInt1PtrTy(LLVMContext &C, unsigned AS = 0);
-  static const PointerType *getInt8PtrTy(LLVMContext &C, unsigned AS = 0);
-  static const PointerType *getInt16PtrTy(LLVMContext &C, unsigned AS = 0);
-  static const PointerType *getInt32PtrTy(LLVMContext &C, unsigned AS = 0);
-  static const PointerType *getInt64PtrTy(LLVMContext &C, unsigned AS = 0);
+  static PointerType *getFloatPtrTy(LLVMContext &C, unsigned AS = 0);
+  static PointerType *getDoublePtrTy(LLVMContext &C, unsigned AS = 0);
+  static PointerType *getX86_FP80PtrTy(LLVMContext &C, unsigned AS = 0);
+  static PointerType *getFP128PtrTy(LLVMContext &C, unsigned AS = 0);
+  static PointerType *getPPC_FP128PtrTy(LLVMContext &C, unsigned AS = 0);
+  static PointerType *getX86_MMXPtrTy(LLVMContext &C, unsigned AS = 0);
+  static PointerType *getIntNPtrTy(LLVMContext &C, unsigned N, unsigned AS = 0);
+  static PointerType *getInt1PtrTy(LLVMContext &C, unsigned AS = 0);
+  static PointerType *getInt8PtrTy(LLVMContext &C, unsigned AS = 0);
+  static PointerType *getInt16PtrTy(LLVMContext &C, unsigned AS = 0);
+  static PointerType *getInt32PtrTy(LLVMContext &C, unsigned AS = 0);
+  static PointerType *getInt64PtrTy(LLVMContext &C, unsigned AS = 0);
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const Type *) { return true; }
 
-  void addRef() const {
-    assert(isAbstract() && "Cannot add a reference to a non-abstract type!");
-    ++RefCount;
-  }
-
-  void dropRef() const {
-    assert(isAbstract() && "Cannot drop a reference 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())
-      this->destroy();
-  }
-  
-  /// 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;
-  
-  /// 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
-  /// the PATypeHandle class.  When there are no users of the abstract type, it
-  /// is annihilated, because there is no way to get a reference to it ever
-  /// again.
-  ///
-  void removeAbstractTypeUser(AbstractTypeUser *U) const;
-
   /// getPointerTo - Return a pointer to the current type.  This is equivalent
   /// to PointerType::get(Foo, AddrSpace).
-  const PointerType *getPointerTo(unsigned AddrSpace = 0) const;
+  PointerType *getPointerTo(unsigned AddrSpace = 0) const;
 
 private:
   /// isSizedDerivedType - Derived types like structures and arrays are sized
   /// iff all of the members of the type are sized as well.  Since asking for
   /// their size is relatively uncommon, move this operation out of line.
   bool isSizedDerivedType() const;
-
-  virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy);
-  virtual void typeBecameConcrete(const DerivedType *AbsTy);
-
-protected:
-  // PromoteAbstractToConcrete - This is an internal method used to calculate
-  // change "Abstract" from true to false when types are refined.
-  void PromoteAbstractToConcrete();
-  friend class TypeMapBase;
 };
 
-//===----------------------------------------------------------------------===//
-// Define some inline methods for the AbstractTypeUser.h:PATypeHandle class.
-// These are defined here because they MUST be inlined, yet are dependent on
-// the definition of the Type class.
-//
-inline void PATypeHandle::addUser() {
-  assert(Ty && "Type Handle has a null type!");
-  if (Ty->isAbstract())
-    Ty->addAbstractTypeUser(User);
-}
-inline void PATypeHandle::removeUser() {
-  if (Ty->isAbstract())
-    Ty->removeAbstractTypeUser(User);
-}
-
-// Define inline methods for PATypeHolder.
-
-/// 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 Type *PATypeHolder::get() const {
-  if (Ty == 0) return 0;
-  const Type *NewTy = Ty->getForwardedType();
-  if (!NewTy) return const_cast<Type*>(Ty);
-  return *const_cast<PATypeHolder*>(this) = NewTy;
-}
-
-inline void PATypeHolder::addRef() {
-  if (Ty && Ty->isAbstract())
-    Ty->addRef();
-}
-
-inline void PATypeHolder::dropRef() {
-  if (Ty && Ty->isAbstract())
-    Ty->dropRef();
+// Printing of types.
+static inline raw_ostream &operator<<(raw_ostream &OS, const Type &T) {
+  T.print(OS);
+  return OS;
 }
 
+// allow isa<PointerType>(x) to work without DerivedTypes.h included.
+template <> struct isa_impl<PointerType, Type> {
+  static inline bool doit(const Type &Ty) {
+    return Ty.getTypeID() == Type::PointerTyID;
+  }
+};
 
+  
 //===----------------------------------------------------------------------===//
 // Provide specializations of GraphTraits to be able to treat a type as a
 // graph of sub types.
 
+
 template <> struct GraphTraits<Type*> {
   typedef Type NodeType;
   typedef Type::subtype_iterator ChildIteratorType;
@@ -545,14 +397,6 @@ template <> struct GraphTraits<const Type*> {
   }
 };
 
-template <> struct isa_impl<PointerType, Type> {
-  static inline bool doit(const Type &Ty) {
-    return Ty.getTypeID() == Type::PointerTyID;
-  }
-};
-
-raw_ostream &operator<<(raw_ostream &OS, const Type &T);
-
 } // End llvm namespace
 
 #endif