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

20 files changed, 339 insertions, 886 deletions

diff --git a/include/llvm-c/Core.h b/include/llvm-c/Core.h
index 2eccc11aa4..e7818c1e7a 100644
--- a/include/llvm-c/Core.h
+++ b/include/llvm-c/Core.h
@@ -68,13 +68,6 @@ typedef struct LLVMOpaqueModule *LLVMModuleRef;
  */
 typedef struct LLVMOpaqueType *LLVMTypeRef;
 
-/**
- * When building recursive types using LLVMRefineType, LLVMTypeRef values may
- * become invalid; use LLVMTypeHandleRef to resolve this problem. See the
- * llvm::AbstractTypeHolder class.
- */
-typedef struct LLVMOpaqueTypeHandle *LLVMTypeHandleRef;
-
 typedef struct LLVMOpaqueValue *LLVMValueRef;
 typedef struct LLVMOpaqueBasicBlock *LLVMBasicBlockRef;
 typedef struct LLVMOpaqueBuilder *LLVMBuilderRef;
@@ -206,7 +199,6 @@ typedef enum {
   LLVMStructTypeKind,      /**< Structures */
   LLVMArrayTypeKind,       /**< Arrays */
   LLVMPointerTypeKind,     /**< Pointers */
-  LLVMOpaqueTypeKind,      /**< Opaque: type with unknown structure */
   LLVMVectorTypeKind,      /**< SIMD 'packed' format, or other vector type */
   LLVMMetadataTypeKind,    /**< Metadata */
   LLVMX86_MMXTypeKind      /**< X86 MMX */
@@ -320,12 +312,6 @@ void LLVMSetDataLayout(LLVMModuleRef M, const char *Triple);
 const char *LLVMGetTarget(LLVMModuleRef M);
 void LLVMSetTarget(LLVMModuleRef M, const char *Triple);
 
-/** See Module::addTypeName. */
-LLVMBool LLVMAddTypeName(LLVMModuleRef M, const char *Name, LLVMTypeRef Ty);
-void LLVMDeleteTypeName(LLVMModuleRef M, const char *Name);
-LLVMTypeRef LLVMGetTypeByName(LLVMModuleRef M, const char *Name);
-const char *LLVMGetTypeName(LLVMModuleRef M, LLVMTypeRef Ty);
-
 /** See Module::dump. */
 void LLVMDumpModule(LLVMModuleRef M);
 
@@ -418,7 +404,6 @@ unsigned LLVMGetVectorSize(LLVMTypeRef VectorTy);
 /* Operations on other types */
 LLVMTypeRef LLVMVoidTypeInContext(LLVMContextRef C);
 LLVMTypeRef LLVMLabelTypeInContext(LLVMContextRef C);
-LLVMTypeRef LLVMOpaqueTypeInContext(LLVMContextRef C);
 LLVMTypeRef LLVMX86MMXTypeInContext(LLVMContextRef C);
 
 LLVMTypeRef LLVMVoidType(void);
@@ -426,13 +411,6 @@ LLVMTypeRef LLVMLabelType(void);
 LLVMTypeRef LLVMOpaqueType(void);
 LLVMTypeRef LLVMX86MMXType(void);
 
-/* Operations on type handles */
-LLVMTypeHandleRef LLVMCreateTypeHandle(LLVMTypeRef PotentiallyAbstractTy);
-void LLVMRefineType(LLVMTypeRef AbstractTy, LLVMTypeRef ConcreteTy);
-LLVMTypeRef LLVMResolveTypeHandle(LLVMTypeHandleRef TypeHandle);
-void LLVMDisposeTypeHandle(LLVMTypeHandleRef TypeHandle);
-
-
 /*===-- Values ------------------------------------------------------------===*/
 
 /* The bulk of LLVM's object model consists of values, which comprise a very
@@ -1117,7 +1095,6 @@ namespace llvm {
   DEFINE_SIMPLE_CONVERSION_FUNCTIONS(Module,             LLVMModuleRef        )
   DEFINE_SIMPLE_CONVERSION_FUNCTIONS(BasicBlock,         LLVMBasicBlockRef    )
   DEFINE_SIMPLE_CONVERSION_FUNCTIONS(IRBuilder<>,        LLVMBuilderRef       )
-  DEFINE_SIMPLE_CONVERSION_FUNCTIONS(PATypeHolder,       LLVMTypeHandleRef    )
   DEFINE_SIMPLE_CONVERSION_FUNCTIONS(MemoryBuffer,       LLVMMemoryBufferRef  )
   DEFINE_SIMPLE_CONVERSION_FUNCTIONS(LLVMContext,        LLVMContextRef       )
   DEFINE_SIMPLE_CONVERSION_FUNCTIONS(Use,                LLVMUseRef           )
diff --git a/include/llvm-c/Transforms/IPO.h b/include/llvm-c/Transforms/IPO.h
index d16e858bca..89b129869c 100644
--- a/include/llvm-c/Transforms/IPO.h
+++ b/include/llvm-c/Transforms/IPO.h
@@ -30,9 +30,6 @@ void LLVMAddConstantMergePass(LLVMPassManagerRef PM);
 /** See llvm::createDeadArgEliminationPass function. */
 void LLVMAddDeadArgEliminationPass(LLVMPassManagerRef PM);
 
-/** See llvm::createDeadTypeEliminationPass function. */
-void LLVMAddDeadTypeEliminationPass(LLVMPassManagerRef PM);
-
 /** See llvm::createFunctionAttrsPass function. */
 void LLVMAddFunctionAttrsPass(LLVMPassManagerRef PM);
 
diff --git a/include/llvm/AbstractTypeUser.h b/include/llvm/AbstractTypeUser.h
deleted file mode 100644
index 81f5c5c768..0000000000
--- a/include/llvm/AbstractTypeUser.h
+++ /dev/null
@@ -1,205 +0,0 @@
-//===-- llvm/AbstractTypeUser.h - AbstractTypeUser Interface ----*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file declares the AbstractTypeUser class.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ABSTRACT_TYPE_USER_H
-#define LLVM_ABSTRACT_TYPE_USER_H
-
-#if !defined(LLVM_TYPE_H) && !defined(LLVM_VALUE_H)
-#error Do not include this file directly.  Include Type.h instead.
-#error Some versions of GCC (e.g. 3.4 and 4.1) can not handle the inlined method
-#error PATypeHolder::dropRef() correctly otherwise.
-#endif
-
-// This is the "master" include for <cassert> Whether this file needs it or not,
-// it must always include <cassert> for the files which include
-// llvm/AbstractTypeUser.h
-//
-// In this way, most every LLVM source file will have access to the assert()
-// macro without having to #include <cassert> directly.
-//
-#include <cassert>
-
-namespace llvm {
-
-class Value;
-class Type;
-class DerivedType;
-template<typename T> struct simplify_type;
-
-/// The AbstractTypeUser class is an interface to be implemented by classes who
-/// could possibly use an abstract type.  Abstract types are denoted by the
-/// isAbstract flag set to true in the Type class.  These are classes that
-/// contain an Opaque type in their structure somewhere.
-///
-/// Classes must implement this interface so that they may be notified when an
-/// abstract type is resolved.  Abstract types may be resolved into more 
-/// concrete types through: linking, parsing, and bitcode reading.  When this 
-/// happens, all of the users of the type must be updated to reference the new,
-/// more concrete type.  They are notified through the AbstractTypeUser 
-/// interface.
-///
-/// In addition to this, AbstractTypeUsers must keep the use list of the
-/// potentially abstract type that they reference up-to-date.  To do this in a
-/// nice, transparent way, the PATypeHandle class is used to hold "Potentially
-/// Abstract Types", and keep the use list of the abstract types up-to-date.
-/// @brief LLVM Abstract Type User Representation
-class AbstractTypeUser {
-protected:
-  virtual ~AbstractTypeUser();                        // Derive from me
-
-  /// setType - It's normally not possible to change a Value's type in place,
-  /// but an AbstractTypeUser subclass that knows what its doing can be
-  /// permitted to do so with care.
-  void setType(Value *V, const Type *NewTy);
-
-public:
-
-  /// refineAbstractType - The callback method invoked when an abstract type is
-  /// resolved to another type.  An object must override this method to update
-  /// its internal state to reference NewType instead of OldType.
-  ///
-  virtual void refineAbstractType(const DerivedType *OldTy,
-                                  const Type *NewTy) = 0;
-
-  /// The other case which AbstractTypeUsers must be aware of is when a type
-  /// makes the transition from being abstract (where it has clients on its
-  /// AbstractTypeUsers list) to concrete (where it does not).  This method
-  /// notifies ATU's when this occurs for a type.
-  ///
-  virtual void typeBecameConcrete(const DerivedType *AbsTy) = 0;
-
-  // for debugging...
-  virtual void dump() const = 0;
-};
-
-
-/// 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;
-
-  // These functions are defined at the bottom of Type.h.  See the comment there
-  // for justification.
-  void addUser();
-  void removeUser();
-public:
-  // ctor - Add use to type if abstract.  Note that Ty must not be null
-  inline PATypeHandle(const Type *ty, AbstractTypeUser *user)
-    : Ty(ty), User(user) {
-    addUser();
-  }
-
-  // ctor - Add use to type if abstract.
-  inline PATypeHandle(const PATypeHandle &T) : Ty(T.Ty), User(T.User) {
-    addUser();
-  }
-
-  // dtor - Remove reference to type...
-  inline ~PATypeHandle() { removeUser(); }
-
-  // Automatic casting operator so that the handle may be used naturally
-  inline operator Type *() const { return const_cast<Type*>(Ty); }
-  inline Type *get() const { return const_cast<Type*>(Ty); }
-
-  // operator= - Allow assignment to handle
-  inline Type *operator=(const Type *ty) {
-    if (Ty != ty) {   // Ensure we don't accidentally drop last ref to Ty
-      removeUser();
-      Ty = ty;
-      addUser();
-    }
-    return get();
-  }
-
-  // operator= - Allow assignment to handle
-  inline const Type *operator=(const PATypeHandle &T) {
-    return operator=(T.Ty);
-  }
-
-  inline bool operator==(const Type *ty) {
-    return Ty == ty;
-  }
-
-  // operator-> - Allow user to dereference handle naturally...
-  inline const Type *operator->() const { return Ty; }
-};
-
-
-/// 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;
-  void destroy();
-public:
-  PATypeHolder() : Ty(0) {}
-  PATypeHolder(const Type *ty) : Ty(ty) {
-    addRef();
-  }
-  PATypeHolder(const PATypeHolder &T) : Ty(T.Ty) {
-    addRef();
-  }
-
-  ~PATypeHolder() { dropRef(); }
-
-  operator Type *() const { return get(); }
-  Type *get() const;
-
-  // operator-> - Allow user to dereference handle naturally...
-  Type *operator->() const { return get(); }
-
-  // operator= - Allow assignment to handle
-  Type *operator=(const Type *ty) {
-    if (Ty != ty) {   // Don't accidentally drop last ref to Ty.
-      dropRef();
-      Ty = ty;
-      addRef();
-    }
-    return get();
-  }
-  Type *operator=(const PATypeHolder &H) {
-    return operator=(H.Ty);
-  }
-
-  /// getRawType - This should only be used to implement the vmcore library.
-  ///
-  const Type *getRawType() const { return Ty; }
-
-private:
-  void addRef();
-  void dropRef();
-  friend class TypeMapBase;
-};
-
-// simplify_type - Allow clients to treat uses just like values when using
-// casting operators.
-template<> struct simplify_type<PATypeHolder> {
-  typedef const Type* SimpleType;
-  static SimpleType getSimplifiedValue(const PATypeHolder &Val) {
-    return static_cast<SimpleType>(Val.get());
-  }
-};
-template<> struct simplify_type<const PATypeHolder> {
-  typedef const Type* SimpleType;
-  static SimpleType getSimplifiedValue(const PATypeHolder &Val) {
-    return static_cast<SimpleType>(Val.get());
-  }
-};
-  
-} // End llvm namespace
-
-#endif
diff --git a/include/llvm/Bitcode/LLVMBitCodes.h b/include/llvm/Bitcode/LLVMBitCodes.h
index d3fee54f42..df68bd5ddd 100644
--- a/include/llvm/Bitcode/LLVMBitCodes.h
+++ b/include/llvm/Bitcode/LLVMBitCodes.h
@@ -29,13 +29,23 @@ namespace bitc {
 
     // Module sub-block id's.
     PARAMATTR_BLOCK_ID,
-    TYPE_BLOCK_ID,
+    
+    /// TYPE_BLOCK_ID_OLD - This is the type descriptor block in LLVM 2.9 and
+    /// earlier, replaced with TYPE_BLOCK_ID2.  FIXME: Remove in LLVM 3.1.
+    TYPE_BLOCK_ID_OLD,
+    
     CONSTANTS_BLOCK_ID,
     FUNCTION_BLOCK_ID,
-    TYPE_SYMTAB_BLOCK_ID,
+    
+    /// TYPE_SYMTAB_BLOCK_ID_OLD - This type descriptor is from LLVM 2.9 and
+    /// earlier bitcode files.  FIXME: Remove in LLVM 3.1
+    TYPE_SYMTAB_BLOCK_ID_OLD,
+    
     VALUE_SYMTAB_BLOCK_ID,
     METADATA_BLOCK_ID,
-    METADATA_ATTACHMENT_ID
+    METADATA_ATTACHMENT_ID,
+    
+    TYPE_BLOCK_ID_NEW
   };
 
 
@@ -72,31 +82,38 @@ namespace bitc {
 
   /// TYPE blocks have codes for each type primitive they use.
   enum TypeCodes {
-    TYPE_CODE_NUMENTRY =  1,   // NUMENTRY: [numentries]
+    TYPE_CODE_NUMENTRY =  1,    // NUMENTRY: [numentries]
 
     // Type Codes
-    TYPE_CODE_VOID     =  2,   // VOID
-    TYPE_CODE_FLOAT    =  3,   // FLOAT
-    TYPE_CODE_DOUBLE   =  4,   // DOUBLE
-    TYPE_CODE_LABEL    =  5,   // LABEL
-    TYPE_CODE_OPAQUE   =  6,   // OPAQUE
-    TYPE_CODE_INTEGER  =  7,   // INTEGER: [width]
-    TYPE_CODE_POINTER  =  8,   // POINTER: [pointee type]
-    TYPE_CODE_FUNCTION =  9,   // FUNCTION: [vararg, retty, paramty x N]
-    TYPE_CODE_STRUCT   = 10,   // STRUCT: [ispacked, eltty x N]
-    TYPE_CODE_ARRAY    = 11,   // ARRAY: [numelts, eltty]
-    TYPE_CODE_VECTOR   = 12,   // VECTOR: [numelts, eltty]
+    TYPE_CODE_VOID     =  2,    // VOID
+    TYPE_CODE_FLOAT    =  3,    // FLOAT
+    TYPE_CODE_DOUBLE   =  4,    // DOUBLE
+    TYPE_CODE_LABEL    =  5,    // LABEL
+    TYPE_CODE_OPAQUE   =  6,    // OPAQUE
+    TYPE_CODE_INTEGER  =  7,    // INTEGER: [width]
+    TYPE_CODE_POINTER  =  8,    // POINTER: [pointee type]
+    TYPE_CODE_FUNCTION =  9,    // FUNCTION: [vararg, retty, paramty x N]
+    
+    // FIXME: This is the encoding used for structs in LLVM 2.9 and earlier.
+    // REMOVE this in LLVM 3.1
+    TYPE_CODE_STRUCT_OLD = 10,  // STRUCT: [ispacked, eltty x N]
+    TYPE_CODE_ARRAY    = 11,    // ARRAY: [numelts, eltty]
+    TYPE_CODE_VECTOR   = 12,    // VECTOR: [numelts, eltty]
 
     // These are not with the other floating point types because they're
     // a late addition, and putting them in the right place breaks
     // binary compatibility.
-    TYPE_CODE_X86_FP80 = 13,   // X86 LONG DOUBLE
-    TYPE_CODE_FP128    = 14,   // LONG DOUBLE (112 bit mantissa)
-    TYPE_CODE_PPC_FP128= 15,   // PPC LONG DOUBLE (2 doubles)
+    TYPE_CODE_X86_FP80 = 13,    // X86 LONG DOUBLE
+    TYPE_CODE_FP128    = 14,    // LONG DOUBLE (112 bit mantissa)
+    TYPE_CODE_PPC_FP128= 15,    // PPC LONG DOUBLE (2 doubles)
 
-    TYPE_CODE_METADATA = 16,   // METADATA
+    TYPE_CODE_METADATA = 16,    // METADATA
 
-    TYPE_CODE_X86_MMX = 17     // X86 MMX
+    TYPE_CODE_X86_MMX = 17,     // X86 MMX
+    
+    TYPE_CODE_STRUCT_ANON = 18, // STRUCT_ANON: [ispacked, eltty x N]
+    TYPE_CODE_STRUCT_NAME = 19, // STRUCT_NAME: [strchr x N]
+    TYPE_CODE_STRUCT_NAMED = 20 // STRUCT_NAMED: [ispacked, eltty x N]
   };
 
   // The type symbol table only has one code (TST_ENTRY_CODE).
diff --git a/include/llvm/Constants.h b/include/llvm/Constants.h
index 1afbb8a96d..3f0efd9cee 100644
--- a/include/llvm/Constants.h
+++ b/include/llvm/Constants.h
@@ -912,10 +912,18 @@ public:
   Constant *getWithOperandReplaced(unsigned OpNo, Constant *Op) const;
   
   /// getWithOperands - This returns the current constant expression with the
-  /// operands replaced with the specified values.  The specified operands must
-  /// match count and type with the existing ones.
-  Constant *getWithOperands(ArrayRef<Constant*> Ops) const;
-  
+  /// operands replaced with the specified values.  The specified array must
+  /// have the same number of operands as our current one.
+  Constant *getWithOperands(ArrayRef<Constant*> Ops) const {
+    return getWithOperands(Ops, getType());
+  }
+
+  /// getWithOperands - This returns the current constant expression with the
+  /// operands replaced with the specified values and with the specified result
+  /// type.  The specified array must have the same number of operands as our
+  /// current one.
+  Constant *getWithOperands(ArrayRef<Constant*> Ops, const Type *Ty) const;
+
   virtual void destroyConstant();
   virtual void replaceUsesOfWithOnConstant(Value *From, Value *To, Use *U);
 
diff --git a/include/llvm/DefaultPasses.h b/include/llvm/DefaultPasses.h
index e2e58a5b98..2e4145b5eb 100644
--- a/include/llvm/DefaultPasses.h
+++ b/include/llvm/DefaultPasses.h
@@ -29,7 +29,6 @@ extern unsigned char ConstantMergeID;
 extern unsigned char CorrelatedValuePropagationID;
 extern unsigned char DeadArgEliminationID;
 extern unsigned char DeadStoreEliminationID;
-extern unsigned char DeadTypeEliminationID;
 extern unsigned char EarlyCSEID;
 extern unsigned char FunctionAttrsID;
 extern unsigned char FunctionInliningID;
diff --git a/include/llvm/DerivedTypes.h b/include/llvm/DerivedTypes.h
index fe9f5f8099..1cefcb298d 100644
--- a/include/llvm/DerivedTypes.h
+++ b/include/llvm/DerivedTypes.h
@@ -24,51 +24,16 @@
 namespace llvm {
 
 class Value;
-template<class ValType, class TypeClass> class TypeMap;
-class FunctionValType;
-class ArrayValType;
-class StructValType;
-class PointerValType;
-class VectorValType;
-class IntegerValType;
 class APInt;
 class LLVMContext;
 template<typename T> class ArrayRef;
+class StringRef;
 
 class DerivedType : public Type {
-  friend class Type;
-
 protected:
   explicit DerivedType(LLVMContext &C, TypeID id) : Type(C, id) {}
-
-  /// notifyUsesThatTypeBecameConcrete - Notify AbstractTypeUsers of this type
-  /// that the current type has transitioned from being abstract to being
-  /// concrete.
-  ///
-  void notifyUsesThatTypeBecameConcrete();
-
-  /// dropAllTypeUses - When this (abstract) type is resolved to be equal to
-  /// another (more concrete) type, we must eliminate all references to other
-  /// types, to avoid some circular reference problems.
-  ///
-  void dropAllTypeUses();
-
 public:
 
-  //===--------------------------------------------------------------------===//
-  // Abstract Type handling methods - These types have special lifetimes, which
-  // are managed by (add|remove)AbstractTypeUser. See comments in
-  // AbstractTypeUser.h for more information.
-
-  /// refineAbstractTypeTo - This function is used to when it is discovered that
-  /// the 'this' abstract type is actually equivalent to the NewType specified.
-  /// This causes all users of 'this' to switch to reference the more concrete
-  /// type NewType and for 'this' to be deleted.
-  ///
-  void refineAbstractTypeTo(const Type *NewType);
-
-  void dump() const { Type::dump(); }
-
   // Methods for support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const DerivedType *) { return true; }
   static inline bool classof(const Type *T) {
@@ -88,7 +53,6 @@ protected:
       DerivedType(C, IntegerTyID) {
     setSubclassData(NumBits);
   }
-  friend class TypeMap<IntegerValType, IntegerType>;
 public:
   /// This enum is just used to hold constants we need for IntegerType.
   enum {
@@ -103,7 +67,7 @@ public:
   /// that instance will be returned. Otherwise a new one will be created. Only
   /// one instance with a given NumBits value is ever created.
   /// @brief Get or create an IntegerType instance.
-  static const IntegerType *get(LLVMContext &C, unsigned NumBits);
+  static IntegerType *get(LLVMContext &C, unsigned NumBits);
 
   /// @brief Get the number of bits in this IntegerType
   unsigned getBitWidth() const { return getSubclassData(); }
@@ -143,11 +107,9 @@ public:
 /// FunctionType - Class to represent function types
 ///
 class FunctionType : public DerivedType {
-  friend class TypeMap<FunctionValType, FunctionType>;
   FunctionType(const FunctionType &);                   // Do not implement
   const FunctionType &operator=(const FunctionType &);  // Do not implement
-  FunctionType(const Type *Result, ArrayRef<const Type*> Params,
-               bool IsVarArgs);
+  FunctionType(const Type *Result, ArrayRef<Type*> Params, bool IsVarArgs);
 
 public:
   /// FunctionType::get - This static method is the primary way of constructing
@@ -155,6 +117,8 @@ public:
   ///
   static FunctionType *get(const Type *Result,
                            ArrayRef<const Type*> Params, bool isVarArg);
+  static FunctionType *get(const Type *Result,
+                           ArrayRef<Type*> Params, bool isVarArg);
 
   /// FunctionType::get - Create a FunctionType taking no parameters.
   ///
@@ -169,24 +133,20 @@ public:
   static bool isValidArgumentType(const Type *ArgTy);
 
   bool isVarArg() const { return getSubclassData(); }
-  const Type *getReturnType() const { return ContainedTys[0]; }
+  Type *getReturnType() const { return ContainedTys[0]; }
 
   typedef Type::subtype_iterator param_iterator;
   param_iterator param_begin() const { return ContainedTys + 1; }
   param_iterator param_end() const { return &ContainedTys[NumContainedTys]; }
 
   // Parameter type accessors.
-  const Type *getParamType(unsigned i) const { return ContainedTys[i+1]; }
+  Type *getParamType(unsigned i) const { return ContainedTys[i+1]; }
 
   /// getNumParams - Return the number of fixed parameters this function type
   /// requires.  This does not consider varargs.
   ///
   unsigned getNumParams() const { return NumContainedTys - 1; }
 
-  // Implement the AbstractTypeUser interface.
-  virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy);
-  virtual void typeBecameConcrete(const DerivedType *AbsTy);
-
   // Methods for support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const FunctionType *) { return true; }
   static inline bool classof(const Type *T) {
@@ -205,8 +165,8 @@ public:
   /// getTypeAtIndex - Given an index value into the type, return the type of
   /// the element.
   ///
-  const Type *getTypeAtIndex(const Value *V) const;
-  const Type *getTypeAtIndex(unsigned Idx) const;
+  Type *getTypeAtIndex(const Value *V) const;
+  Type *getTypeAtIndex(unsigned Idx) const;
   bool indexValid(const Value *V) const;
   bool indexValid(unsigned Idx) const;
 
@@ -222,18 +182,49 @@ public:
 
 
 /// StructType - Class to represent struct types, both normal and packed.
+/// Besides being optionally packed, structs can be either "anonymous" or may
+/// have an identity.  Anonymous structs are uniqued by structural equivalence,
+/// but types are each unique when created, and optionally have a name.
 ///
 class StructType : public CompositeType {
-  friend class TypeMap<StructValType, StructType>;
   StructType(const StructType &);                   // Do not implement
   const StructType &operator=(const StructType &);  // Do not implement
-  StructType(LLVMContext &C, ArrayRef<const Type*> Types, bool isPacked);
+  StructType(LLVMContext &C)
+    : CompositeType(C, StructTyID), SymbolTableEntry(0) {}
+  enum {
+    // This is the contents of the SubClassData field.
+    SCDB_HasBody = 1,
+    SCDB_Packed = 2,
+    SCDB_IsAnonymous = 4
+  };
+  
+  /// SymbolTableEntry - For a named struct that actually has a name, this is a
+  /// pointer to the symbol table entry (maintained by LLVMContext) for the
+  /// struct.  This is null if the type is an anonymous struct or if it is
+  /// 
+  void *SymbolTableEntry;
 public:
+  /// StructType::createNamed - This creates a named struct with no body
+  /// specified.  If the name is empty, it creates an unnamed struct, which has
+  /// a unique identity but no actual name.
+  static StructType *createNamed(LLVMContext &Context, StringRef Name);
+  
+  static StructType *createNamed(StringRef Name, ArrayRef<Type*> Elements,
+                                 bool isPacked = false);
+  static StructType *createNamed(LLVMContext &Context, StringRef Name,
+                                 ArrayRef<Type*> Elements,
+                                 bool isPacked = false);
+  static StructType *createNamed(StringRef Name, Type *elt1, ...) END_WITH_NULL;
+
   /// StructType::get - This static method is the primary way to create a
   /// StructType.
   ///
+  /// FIXME: Remove the 'const Type*' version of this when types are pervasively
+  /// de-constified.
   static StructType *get(LLVMContext &Context, ArrayRef<const Type*> Elements,
                          bool isPacked = false);
+  static StructType *get(LLVMContext &Context, ArrayRef<Type*> Elements,
+                         bool isPacked = false);
 
   /// StructType::get - Create an empty structure type.
   ///
@@ -245,11 +236,37 @@ public:
   /// element type.
   static StructType *get(const Type *elt1, ...) END_WITH_NULL;
 
+  bool isPacked() const { return (getSubclassData() & SCDB_Packed) != 0; }
+  
+  /// isAnonymous - Return true if this type is uniqued by structural
+  /// equivalence, false if it has an identity.
+  bool isAnonymous() const {return (getSubclassData() & SCDB_IsAnonymous) != 0;}
+  
+  /// isOpaque - Return true if this is a type with an identity that has no body
+  /// specified yet.  These prints as 'opaque' in .ll files.
+  bool isOpaque() const { return (getSubclassData() & SCDB_HasBody) == 0; }
+  
+  /// hasName - Return true if this is a named struct that has a non-empty name.
+  bool hasName() const { return SymbolTableEntry != 0; }
+  
+  /// getName - Return the name for this struct type if it has an identity.
+  /// This may return an empty string for an unnamed struct type.  Do not call
+  /// this on an anonymous type.
+  StringRef getName() const;
+  
+  /// setName - Change the name of this type to the specified name, or to a name
+  /// with a suffix if there is a collision.  Do not call this on an anonymous
+  /// type.
+  void setName(StringRef Name);
+
+  /// setBody - Specify a body for an opaque type.
+  void setBody(ArrayRef<Type*> Elements, bool isPacked = false);
+  void setBody(Type *elt1, ...) END_WITH_NULL;
+  
   /// isValidElementType - Return true if the specified type is valid as a
   /// element type.
   static bool isValidElementType(const Type *ElemTy);
-
-  bool isPacked() const { return getSubclassData() != 0 ? true : false; }
+  
 
   // Iterator access to the elements.
   typedef Type::subtype_iterator element_iterator;
@@ -258,22 +275,15 @@ public:
 
   /// isLayoutIdentical - Return true if this is layout identical to the
   /// specified struct.
-  bool isLayoutIdentical(const StructType *Other) const {
-    return this == Other;
-  }
-  
+  bool isLayoutIdentical(const StructType *Other) const;  
   
   // Random access to the elements
   unsigned getNumElements() const { return NumContainedTys; }
-  const Type *getElementType(unsigned N) const {
+  Type *getElementType(unsigned N) const {
     assert(N < NumContainedTys && "Element number out of range!");
     return ContainedTys[N];
   }
 
-  // Implement the AbstractTypeUser interface.
-  virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy);
-  virtual void typeBecameConcrete(const DerivedType *AbsTy);
-
   // Methods for support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const StructType *) { return true; }
   static inline bool classof(const Type *T) {
@@ -290,21 +300,19 @@ public:
 /// components out in memory identically.
 ///
 class SequentialType : public CompositeType {
-  PATypeHandle ContainedType;       ///< Storage for the single contained type.
+  Type *ContainedType;               ///< Storage for the single contained type.
   SequentialType(const SequentialType &);                  // Do not implement!
   const SequentialType &operator=(const SequentialType &); // Do not implement!
 
-  // avoiding warning: 'this' : used in base member initializer list
-  SequentialType *this_() { return this; }
 protected:
-  SequentialType(TypeID TID, const Type *ElType)
-    : CompositeType(ElType->getContext(), TID), ContainedType(ElType, this_()) {
+  SequentialType(TypeID TID, Type *ElType)
+    : CompositeType(ElType->getContext(), TID), ContainedType(ElType) {
     ContainedTys = &ContainedType;
     NumContainedTys = 1;
   }
 
 public:
-  const Type *getElementType() const { return ContainedTys[0]; }
+  Type *getElementType() const { return ContainedTys[0]; }
 
   // Methods for support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const SequentialType *) { return true; }
@@ -319,12 +327,11 @@ public:
 /// ArrayType - Class to represent array types.
 ///
 class ArrayType : public SequentialType {
-  friend class TypeMap<ArrayValType, ArrayType>;
   uint64_t NumElements;
 
   ArrayType(const ArrayType &);                   // Do not implement
   const ArrayType &operator=(const ArrayType &);  // Do not implement
-  ArrayType(const Type *ElType, uint64_t NumEl);
+  ArrayType(Type *ElType, uint64_t NumEl);
 public:
   /// ArrayType::get - This static method is the primary way to construct an
   /// ArrayType
@@ -337,10 +344,6 @@ public:
 
   uint64_t getNumElements() const { return NumElements; }
 
-  // Implement the AbstractTypeUser interface.
-  virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy);
-  virtual void typeBecameConcrete(const DerivedType *AbsTy);
-
   // Methods for support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const ArrayType *) { return true; }
   static inline bool classof(const Type *T) {
@@ -351,12 +354,11 @@ public:
 /// VectorType - Class to represent vector types.
 ///
 class VectorType : public SequentialType {
-  friend class TypeMap<VectorValType, VectorType>;
   unsigned NumElements;
 
   VectorType(const VectorType &);                   // Do not implement
   const VectorType &operator=(const VectorType &);  // Do not implement
-  VectorType(const Type *ElType, unsigned NumEl);
+  VectorType(Type *ElType, unsigned NumEl);
 public:
   /// VectorType::get - This static method is the primary way to construct an
   /// VectorType.
@@ -369,7 +371,7 @@ public:
   ///
   static VectorType *getInteger(const VectorType *VTy) {
     unsigned EltBits = VTy->getElementType()->getPrimitiveSizeInBits();
-    const Type *EltTy = IntegerType::get(VTy->getContext(), EltBits);
+    Type *EltTy = IntegerType::get(VTy->getContext(), EltBits);
     return VectorType::get(EltTy, VTy->getNumElements());
   }
 
@@ -379,7 +381,7 @@ public:
   ///
   static VectorType *getExtendedElementVectorType(const VectorType *VTy) {
     unsigned EltBits = VTy->getElementType()->getPrimitiveSizeInBits();
-    const Type *EltTy = IntegerType::get(VTy->getContext(), EltBits * 2);
+    Type *EltTy = IntegerType::get(VTy->getContext(), EltBits * 2);
     return VectorType::get(EltTy, VTy->getNumElements());
   }
 
@@ -391,7 +393,7 @@ public:
     unsigned EltBits = VTy->getElementType()->getPrimitiveSizeInBits();
     assert((EltBits & 1) == 0 &&
            "Cannot truncate vector element with odd bit-width");
-    const Type *EltTy = IntegerType::get(VTy->getContext(), EltBits / 2);
+    Type *EltTy = IntegerType::get(VTy->getContext(), EltBits / 2);
     return VectorType::get(EltTy, VTy->getNumElements());
   }
 
@@ -407,10 +409,6 @@ public:
     return NumElements * getElementType()->getPrimitiveSizeInBits();
   }
 
-  // Implement the AbstractTypeUser interface.
-  virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy);