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

19 files changed, 703 insertions, 2251 deletions

diff --git a/lib/VMCore/AsmWriter.cpp b/lib/VMCore/AsmWriter.cpp
index 496f500..18776dd 100644
--- a/lib/VMCore/AsmWriter.cpp
+++ b/lib/VMCore/AsmWriter.cpp
@@ -26,8 +26,7 @@
 #include "llvm/Operator.h"
 #include "llvm/Module.h"
 #include "llvm/ValueSymbolTable.h"
-#include "llvm/TypeSymbolTable.h"
-#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/STLExtras.h"
@@ -137,72 +136,57 @@ static void PrintLLVMName(raw_ostream &OS, const Value *V) {
 /// TypePrinting - Type printing machinery.
 namespace {
 class TypePrinting {
-  DenseMap<const Type *, std::string> TypeNames;
   TypePrinting(const TypePrinting &);   // DO NOT IMPLEMENT
   void operator=(const TypePrinting&);  // DO NOT IMPLEMENT
 public:
-  TypePrinting() {}
-  ~TypePrinting() {}
-  
-  void clear() {
-    TypeNames.clear();
-  }
-  
-  void print(const Type *Ty, raw_ostream &OS, bool IgnoreTopLevelName = false);
+
+  /// NamedTypes - The named types that are used by the current module.
+  std::vector<StructType*> NamedTypes;
   
-  void printAtLeastOneLevel(const Type *Ty, raw_ostream &OS) {
-    print(Ty, OS, true);
-  }
+  /// NumberedTypes - The numbered types, along with their value.
+  DenseMap<StructType*, unsigned> NumberedTypes;
   
-  /// hasTypeName - Return true if the type has a name in TypeNames, false
-  /// otherwise.
-  bool hasTypeName(const Type *Ty) const {
-    return TypeNames.count(Ty);
-  }
 
+  TypePrinting() {}
+  ~TypePrinting() {}
   
-  /// addTypeName - Add a name for the specified type if it doesn't already have
-  /// one.  This name will be printed instead of the structural version of the
-  /// type in order to make the output more concise.
-  void addTypeName(const Type *Ty, const std::string &N) {
-    TypeNames.insert(std::make_pair(Ty, N));
-  }
+  void incorporateTypes(const Module &M);
   
-private:
-  void CalcTypeName(const Type *Ty, SmallVectorImpl<const Type *> &TypeStack,
-                    raw_ostream &OS, bool IgnoreTopLevelName = false);
+  void print(Type *Ty, raw_ostream &OS);
+  
+  void printStructBody(StructType *Ty, raw_ostream &OS);
 };
 } // end anonymous namespace.
 
-/// CalcTypeName - Write the specified type to the specified raw_ostream, making
-/// use of type names or up references to shorten the type name where possible.
-void TypePrinting::CalcTypeName(const Type *Ty,
-                                SmallVectorImpl<const Type *> &TypeStack,
-                                raw_ostream &OS, bool IgnoreTopLevelName) {
-  // Check to see if the type is named.
-  if (!IgnoreTopLevelName) {
-    DenseMap<const Type *, std::string> &TM = TypeNames;
-    DenseMap<const Type *, std::string>::iterator I = TM.find(Ty);
-    if (I != TM.end()) {
-      OS << I->second;
-      return;
-    }
-  }
-
-  // Check to see if the Type is already on the stack...
-  unsigned Slot = 0, CurSize = TypeStack.size();
-  while (Slot < CurSize && TypeStack[Slot] != Ty) ++Slot; // Scan for type
 
-  // This is another base case for the recursion.  In this case, we know
-  // that we have looped back to a type that we have previously visited.
-  // Generate the appropriate upreference to handle this.
-  if (Slot < CurSize) {
-    OS << '\\' << unsigned(CurSize-Slot);     // Here's the upreference
-    return;
+void TypePrinting::incorporateTypes(const Module &M) {
+  M.findUsedStructTypes(NamedTypes);
+  
+  // The list of struct types we got back includes all the struct types, split
+  // the unnamed ones out to a numbering and remove the anonymous structs.
+  unsigned NextNumber = 0;
+  
+  std::vector<StructType*>::iterator NextToUse = NamedTypes.begin(), I, E;
+  for (I = NamedTypes.begin(), E = NamedTypes.end(); I != E; ++I) {
+    StructType *STy = *I;
+    
+    // Ignore anonymous types.
+    if (STy->isAnonymous())
+      continue;
+    
+    if (STy->getName().empty())
+      NumberedTypes[STy] = NextNumber++;
+    else
+      *NextToUse++ = STy;
   }
+    
+  NamedTypes.erase(NextToUse, NamedTypes.end());
+}
 
-  TypeStack.push_back(Ty);    // Recursive case: Add us to the stack..
 
+/// CalcTypeName - Write the specified type to the specified raw_ostream, making
+/// use of type names or up references to shorten the type name where possible.
+void TypePrinting::print(Type *Ty, raw_ostream &OS) {
   switch (Ty->getTypeID()) {
   case Type::VoidTyID:      OS << "void"; break;
   case Type::FloatTyID:     OS << "float"; break;
@@ -215,257 +199,100 @@ void TypePrinting::CalcTypeName(const Type *Ty,
   case Type::X86_MMXTyID:   OS << "x86_mmx"; break;
   case Type::IntegerTyID:
     OS << 'i' << cast<IntegerType>(Ty)->getBitWidth();
-    break;
+    return;
 
   case Type::FunctionTyID: {
-    const FunctionType *FTy = cast<FunctionType>(Ty);
-    CalcTypeName(FTy->getReturnType(), TypeStack, OS);
+    FunctionType *FTy = cast<FunctionType>(Ty);
+    print(FTy->getReturnType(), OS);
     OS << " (";
     for (FunctionType::param_iterator I = FTy->param_begin(),
          E = FTy->param_end(); I != E; ++I) {
       if (I != FTy->param_begin())
         OS << ", ";
-      CalcTypeName(*I, TypeStack, OS);
+      print(*I, OS);
     }
     if (FTy->isVarArg()) {
       if (FTy->getNumParams()) OS << ", ";
       OS << "...";
     }
     OS << ')';
-    break;
+    return;
   }
   case Type::StructTyID: {
-    const StructType *STy = cast<StructType>(Ty);
-    if (STy->isPacked())
-      OS << '<';
-    OS << '{';
-    for (StructType::element_iterator I = STy->element_begin(),
-         E = STy->element_end(); I != E; ++I) {
-      OS << ' ';
-      CalcTypeName(*I, TypeStack, OS);
-      if (llvm::next(I) == STy->element_end())
-        OS << ' ';
-      else
-        OS << ',';
-    }
-    OS << '}';
-    if (STy->isPacked())
-      OS << '>';
-    break;
+    StructType *STy = cast<StructType>(Ty);
+    
+    if (STy->isAnonymous())
+      return printStructBody(STy, OS);
+
+    if (!STy->getName().empty())
+      return PrintLLVMName(OS, STy->getName(), LocalPrefix);
+    
+    DenseMap<StructType*, unsigned>::iterator I = NumberedTypes.find(STy);
+    if (I != NumberedTypes.end())
+      OS << '%' << I->second;
+    else  // Not enumerated, print the hex address.
+      OS << "%\"type 0x" << STy << '\"';
+    return;
   }
   case Type::PointerTyID: {
-    const PointerType *PTy = cast<PointerType>(Ty);
-    CalcTypeName(PTy->getElementType(), TypeStack, OS);
+    PointerType *PTy = cast<PointerType>(Ty);
+    print(PTy->getElementType(), OS);
     if (unsigned AddressSpace = PTy->getAddressSpace())
       OS << " addrspace(" << AddressSpace << ')';
     OS << '*';
-    break;
+    return;
   }
   case Type::ArrayTyID: {
-    const ArrayType *ATy = cast<ArrayType>(Ty);
+    ArrayType *ATy = cast<ArrayType>(Ty);
     OS << '[' << ATy->getNumElements() << " x ";
-    CalcTypeName(ATy->getElementType(), TypeStack, OS);
+    print(ATy->getElementType(), OS);
     OS << ']';
-    break;
+    return;
   }
   case Type::VectorTyID: {
-    const VectorType *PTy = cast<VectorType>(Ty);
+    VectorType *PTy = cast<VectorType>(Ty);
     OS << "<" << PTy->getNumElements() << " x ";
-    CalcTypeName(PTy->getElementType(), TypeStack, OS);
+    print(PTy->getElementType(), OS);
     OS << '>';
-    break;
+    return;
   }
-  case Type::OpaqueTyID:
-    OS << "opaque";
-    break;
   default:
     OS << "<unrecognized-type>";
-    break;
+    return;
   }
-
-  TypeStack.pop_back();       // Remove self from stack.
 }
 
-/// printTypeInt - The internal guts of printing out a type that has a
-/// potentially named portion.
-///
-void TypePrinting::print(const Type *Ty, raw_ostream &OS,
-                         bool IgnoreTopLevelName) {
-  // Check to see if the type is named.
-  if (!IgnoreTopLevelName) {
-    DenseMap<const Type*, std::string>::iterator I = TypeNames.find(Ty);
-    if (I != TypeNames.end()) {
-      OS << I->second;
-      return;
-    }
+void TypePrinting::printStructBody(StructType *STy, raw_ostream &OS) {
+  if (STy->isOpaque()) {
+    OS << "opaque";
+    return;
   }
-
-  // Otherwise we have a type that has not been named but is a derived type.
-  // Carefully recurse the type hierarchy to print out any contained symbolic
-  // names.
-  SmallVector<const Type *, 16> TypeStack;
-  std::string TypeName;
-
-  raw_string_ostream TypeOS(TypeName);
-  CalcTypeName(Ty, TypeStack, TypeOS, IgnoreTopLevelName);
-  OS << TypeOS.str();
-
-  // Cache type name for later use.
-  if (!IgnoreTopLevelName)
-    TypeNames.insert(std::make_pair(Ty, TypeOS.str()));
-}
-
-namespace {
-  class TypeFinder {
-    // To avoid walking constant expressions multiple times and other IR
-    // objects, we keep several helper maps.
-    DenseSet<const Value*> VisitedConstants;
-    DenseSet<const Type*> VisitedTypes;
-
-    TypePrinting &TP;
-    std::vector<const Type*> &NumberedTypes;
-  public:
-    TypeFinder(TypePrinting &tp, std::vector<const Type*> &numberedTypes)
-      : TP(tp), NumberedTypes(numberedTypes) {}
-
-    void Run(const Module &M) {
-      // Get types from the type symbol table.  This gets opaque types referened
-      // only through derived named types.
-      const TypeSymbolTable &ST = M.getTypeSymbolTable();
-      for (TypeSymbolTable::const_iterator TI = ST.begin(), E = ST.end();
-           TI != E; ++TI)
-        IncorporateType(TI->second);
-
-      // Get types from global variables.
-      for (Module::const_global_iterator I = M.global_begin(),
-           E = M.global_end(); I != E; ++I) {
-        IncorporateType(I->getType());
-        if (I->hasInitializer())
-          IncorporateValue(I->getInitializer());
-      }
-
-      // Get types from aliases.
-      for (Module::const_alias_iterator I = M.alias_begin(),
-           E = M.alias_end(); I != E; ++I) {
-        IncorporateType(I->getType());
-        IncorporateValue(I->getAliasee());
-      }
-
-      // Get types from functions.
-      for (Module::const_iterator FI = M.begin(), E = M.end(); FI != E; ++FI) {
-        IncorporateType(FI->getType());
-
-        for (Function::const_iterator BB = FI->begin(), E = FI->end();
-             BB != E;++BB)
-          for (BasicBlock::const_iterator II = BB->begin(),
-               E = BB->end(); II != E; ++II) {
-            const Instruction &I = *II;
-            // Incorporate the type of the instruction and all its operands.
-            IncorporateType(I.getType());
-            for (User::const_op_iterator OI = I.op_begin(), OE = I.op_end();
-                 OI != OE; ++OI)
-              IncorporateValue(*OI);
-          }
-      }
-    }
-
-  private:
-    void IncorporateType(const Type *Ty) {
-      // Check to see if we're already visited this type.
-      if (!VisitedTypes.insert(Ty).second)
-        return;
-
-      // If this is a structure or opaque type, add a name for the type.
-      if (((Ty->isStructTy() && cast<StructType>(Ty)->getNumElements())
-            || Ty->isOpaqueTy()) && !TP.hasTypeName(Ty)) {
-        TP.addTypeName(Ty, "%"+utostr(unsigned(NumberedTypes.size())));
-        NumberedTypes.push_back(Ty);
-      }
-
-      // Recursively walk all contained types.
-      for (Type::subtype_iterator I = Ty->subtype_begin(),
-           E = Ty->subtype_end(); I != E; ++I)
-        IncorporateType(*I);
-    }
-
-    /// IncorporateValue - This method is used to walk operand lists finding
-    /// types hiding in constant expressions and other operands that won't be
-    /// walked in other ways.  GlobalValues, basic blocks, instructions, and
-    /// inst operands are all explicitly enumerated.
-    void IncorporateValue(const Value *V) {
-      if (V == 0 || !isa<Constant>(V) || isa<GlobalValue>(V)) return;
-
-      // Already visited?
-      if (!VisitedConstants.insert(V).second)
-        return;
-
-      // Check this type.
-      IncorporateType(V->getType());
-
-      // Look in operands for types.
-      const Constant *C = cast<Constant>(V);
-      for (Constant::const_op_iterator I = C->op_begin(),
-           E = C->op_end(); I != E;++I)
-        IncorporateValue(*I);
-    }
-  };
-} // end anonymous namespace
-
-
-/// AddModuleTypesToPrinter - Add all of the symbolic type names for types in
-/// the specified module to the TypePrinter and all numbered types to it and the
-/// NumberedTypes table.
-static void AddModuleTypesToPrinter(TypePrinting &TP,
-                                    std::vector<const Type*> &NumberedTypes,
-                                    const Module *M) {
-  if (M == 0) return;
-
-  // If the module has a symbol table, take all global types and stuff their
-  // names into the TypeNames map.
-  const TypeSymbolTable &ST = M->getTypeSymbolTable();
-  for (TypeSymbolTable::const_iterator TI = ST.begin(), E = ST.end();
-       TI != E; ++TI) {
-    const Type *Ty = cast<Type>(TI->second);
-
-    // As a heuristic, don't insert pointer to primitive types, because
-    // they are used too often to have a single useful name.
-    if (const PointerType *PTy = dyn_cast<PointerType>(Ty)) {
-      const Type *PETy = PTy->getElementType();
-      if ((PETy->isPrimitiveType() || PETy->isIntegerTy()) &&
-          !PETy->isOpaqueTy())
-        continue;
+  
+  if (STy->isPacked())
+    OS << '<';
+  
+  if (STy->getNumElements() == 0) {
+    OS << "{}";
+  } else {
+    StructType::element_iterator I = STy->element_begin();
+    OS << "{ ";
+    print(*I++, OS);
+    for (StructType::element_iterator E = STy->element_end(); I != E; ++I) {
+      OS << ", ";
+      print(*I, OS);
     }
-
-    // Likewise don't insert primitives either.
-    if (Ty->isIntegerTy() || Ty->isPrimitiveType())
-      continue;
-
-    // Get the name as a string and insert it into TypeNames.
-    std::string NameStr;
-    raw_string_ostream NameROS(NameStr);
-    formatted_raw_ostream NameOS(NameROS);
-    PrintLLVMName(NameOS, TI->first, LocalPrefix);
-    NameOS.flush();
-    TP.addTypeName(Ty, NameStr);
+  
+    OS << " }";
   }
-
-  // Walk the entire module to find references to unnamed structure and opaque
-  // types.  This is required for correctness by opaque types (because multiple
-  // uses of an unnamed opaque type needs to be referred to by the same ID) and
-  // it shrinks complex recursive structure types substantially in some cases.
-  TypeFinder(TP, NumberedTypes).Run(*M);
+  if (STy->isPacked())
+    OS << '>';
 }
 
 
-/// WriteTypeSymbolic - This attempts to write the specified type as a symbolic
-/// type, iff there is an entry in the modules symbol table for the specified
-/// type or one of it's component types.
-///
+
 void llvm::WriteTypeSymbolic(raw_ostream &OS, const Type *Ty, const Module *M) {
-  TypePrinting Printer;
-  std::vector<const Type*> NumberedTypes;
-  AddModuleTypesToPrinter(Printer, NumberedTypes, M);
-  Printer.print(Ty, OS);
+  // FIXME: remove this function.
+  OS << *Ty;
 }
 
 //===----------------------------------------------------------------------===//
@@ -986,7 +813,7 @@ static void WriteConstantInternal(raw_ostream &Out, const Constant *CV,
     // As a special case, print the array as a string if it is an array of
     // i8 with ConstantInt values.
     //
-    const Type *ETy = CA->getType()->getElementType();
+    Type *ETy = CA->getType()->getElementType();
     if (CA->isString()) {
       Out << "c\"";
       PrintEscapedString(CA->getAsString(), Out);
@@ -1043,7 +870,7 @@ static void WriteConstantInternal(raw_ostream &Out, const Constant *CV,
   }
 
   if (const ConstantVector *CP = dyn_cast<ConstantVector>(CV)) {
-    const Type *ETy = CP->getType()->getElementType();
+    Type *ETy = CP->getType()->getElementType();
     assert(CP->getNumOperands() > 0 &&
            "Number of operands for a PackedConst must be > 0");
     Out << '<';
@@ -1241,8 +1068,8 @@ void llvm::WriteAsOperand(raw_ostream &Out, const Value *V,
   if (Context == 0) Context = getModuleFromVal(V);
 
   TypePrinting TypePrinter;
-  std::vector<const Type*> NumberedTypes;
-  AddModuleTypesToPrinter(TypePrinter, NumberedTypes, Context);
+  if (Context)
+    TypePrinter.incorporateTypes(*Context);
   if (PrintType) {
     TypePrinter.print(V->getType(), Out);
     Out << ' ';
@@ -1259,14 +1086,14 @@ class AssemblyWriter {
   const Module *TheModule;
   TypePrinting TypePrinter;
   AssemblyAnnotationWriter *AnnotationWriter;
-  std::vector<const Type*> NumberedTypes;
   
 public:
   inline AssemblyWriter(formatted_raw_ostream &o, SlotTracker &Mac,
                         const Module *M,
                         AssemblyAnnotationWriter *AAW)
     : Out(o), Machine(Mac), TheModule(M), AnnotationWriter(AAW) {
-    AddModuleTypesToPrinter(TypePrinter, NumberedTypes, M);
+    if (M)
+      TypePrinter.incorporateTypes(*M);
   }
 
   void printMDNodeBody(const MDNode *MD);
@@ -1279,7 +1106,7 @@ public:
 
   void writeAllMDNodes();
 
-  void printTypeSymbolTable(const TypeSymbolTable &ST);
+  void printTypeIdentities();
   void printGlobal(const GlobalVariable *GV);
   void printAlias(const GlobalAlias *GV);
   void printFunction(const Function *F);
@@ -1374,9 +1201,7 @@ void AssemblyWriter::printModule(const Module *M) {
     Out << " ]";
   }
 
-  // Loop over the symbol table, emitting all id'd types.
-  if (!M->getTypeSymbolTable().empty() || !NumberedTypes.empty()) Out << '\n';
-  printTypeSymbolTable(M->getTypeSymbolTable());
+  printTypeIdentities();
 
   // Output all globals.
   if (!M->global_empty()) Out << '\n';
@@ -1534,7 +1359,10 @@ void AssemblyWriter::printAlias(const GlobalAlias *GA) {
 
   const Constant *Aliasee = GA->getAliasee();
 
-  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Aliasee)) {
+  if (Aliasee == 0) {
+    TypePrinter.print(GA->getType(), Out);
+    Out << " <<NULL ALIASEE>>";
+  } else if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Aliasee)) {
     TypePrinter.print(GV->getType(), Out);
     Out << ' ';
     PrintLLVMName(Out, GV);
@@ -1560,26 +1388,40 @@ void AssemblyWriter::printAlias(const GlobalAlias *GA) {
   Out << '\n';
 }
 
-void AssemblyWriter::printTypeSymbolTable(const TypeSymbolTable &ST) {
+void AssemblyWriter::printTypeIdentities() {
+  if (TypePrinter.NumberedTypes.empty() &&
+      TypePrinter.NamedTypes.empty())
+    return;
+  
+  Out << '\n';
+  
+  // We know all the numbers that each type is used and we know that it is a
+  // dense assignment.  Convert the map to an index table.
+  std::vector<StructType*> NumberedTypes(TypePrinter.NumberedTypes.size());
+  for (DenseMap<StructType*, unsigned>::iterator I = 
+       TypePrinter.NumberedTypes.begin(), E = TypePrinter.NumberedTypes.end();
+       I != E; ++I) {
+    assert(I->second < NumberedTypes.size() && "Didn't get a dense numbering?");
+    NumberedTypes[I->second] = I->first;
+  }
+           
   // Emit all numbered types.
   for (unsigned i = 0, e = NumberedTypes.size(); i != e; ++i) {
     Out << '%' << i << " = type ";
-
+    
     // Make sure we print out at least one level of the type structure, so
     // that we do not get %2 = type %2
-    TypePrinter.printAtLeastOneLevel(NumberedTypes[i], Out);
+    TypePrinter.printStructBody(NumberedTypes[i], Out);
     Out << '\n';
   }
-
-  // Print the named types.
-  for (TypeSymbolTable::const_iterator TI = ST.begin(), TE = ST.end();
-       TI != TE; ++TI) {
-    PrintLLVMName(Out, TI->first, LocalPrefix);
+  
+  for (unsigned i = 0, e = TypePrinter.NamedTypes.size(); i != e; ++i) {
+    PrintLLVMName(Out, TypePrinter.NamedTypes[i]->getName(), LocalPrefix);
     Out << " = type ";
 
     // Make sure we print out at least one level of the type structure, so
     // that we do not get %FILE = type %FILE
-    TypePrinter.printAtLeastOneLevel(TI->second, Out);
+    TypePrinter.printStructBody(TypePrinter.NamedTypes[i], Out);
     Out << '\n';
   }
 }
@@ -1893,9 +1735,9 @@ void AssemblyWriter::printInstruction(const Instruction &I) {
     }
 
     Operand = CI->getCalledValue();
-    const PointerType    *PTy = cast<PointerType>(Operand->getType());
-    const FunctionType   *FTy = cast<FunctionType>(PTy->getElementType());
-    const Type         *RetTy = FTy->getReturnType();
+    PointerType *PTy = cast<PointerType>(Operand->getType());
+    FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
+    Type *RetTy = FTy->getReturnType();
     const AttrListPtr &PAL = CI->getAttributes();
 
     if (PAL.getRetAttributes() != Attribute::None)
@@ -1926,9 +1768,9 @@ void AssemblyWriter::printInstruction(const Instruction &I) {
       Out << ' ' << Attribute::getAsString(PAL.getFnAttributes());
   } else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I)) {
     Operand = II->getCalledValue();
-    const PointerType    *PTy = cast<PointerType>(Operand->getType());
-    const FunctionType   *FTy = cast<FunctionType>(PTy->getElementType());
-    const Type         *RetTy = FTy->getReturnType();
+    PointerType *PTy = cast<PointerType>(Operand->getType());
+    FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
+    Type *RetTy = FTy->getReturnType();
     const AttrListPtr &PAL = II->getAttributes();
 
     // Print the calling convention being used.
@@ -2011,7 +1853,7 @@ void AssemblyWriter::printInstruction(const Instruction &I) {
     // omit the type from all but the first operand.  If the instruction has
     // different type operands (for example br), then they are all printed.
     bool PrintAllTypes = false;
-    const Type *TheType = Operand->getType();
+    Type *TheType = Operand->getType();
 
     // Select, Store and ShuffleVector always print all types.
     if (isa<SelectInst>(I) || isa<StoreInst>(I) || isa<ShuffleVectorInst>(I)
@@ -2131,7 +1973,15 @@ void Type::print(raw_ostream &OS) const {
     OS << "<null Type>";
     return;
   }
-  TypePrinting().print(this, OS);
+  TypePrinting TP;
+  TP.print(const_cast<Type*>(this), OS);
+  
+  // If the type is a named struct type, print the body as well.
+  if (StructType *STy = dyn_cast<StructType>(const_cast<Type*>(this)))
+    if (!STy->isAnonymous()) {
+      OS << " = type ";
+      TP.printStructBody(STy, OS);
+    }
 }
 
 void Value::print(raw_ostream &ROS, AssemblyAnnotationWriter *AAW) const {
@@ -2187,14 +2037,7 @@ void Value::printCustom(raw_ostream &OS) const {
 void Value::dump() const { print(dbgs()); dbgs() << '\n'; }
 
 // Type::dump - allow easy printing of Types from the debugger.
-// This one uses type names from the given context module
-void Type::dump(const Module *Context) const {
-  WriteTypeSymbolic(dbgs(), this, Context);
-  dbgs() << '\n';
-}
-
-// Type::dump - allow easy printing of Types from the debugger.
-void Type::dump() const { dump(0); }
+void Type::dump() const { print(dbgs()); }
 
 // Module::dump() - Allow printing of Modules from the debugger.
 void Module::dump() const { print(dbgs(), 0); }
diff --git a/lib/VMCore/CMakeLists.txt b/lib/VMCore/CMakeLists.txt
index 6bde263..f60dd06 100644
--- a/lib/VMCore/CMakeLists.txt
+++ b/lib/VMCore/CMakeLists.txt
@@ -29,7 +29,6 @@ add_llvm_library(LLVMCore
   PassRegistry.cpp
   PrintModulePass.cpp
   Type.cpp
-  TypeSymbolTable.cpp
   Use.cpp
   User.cpp
   Value.cpp
diff --git a/lib/VMCore/ConstantFold.cpp b/lib/VMCore/ConstantFold.cpp
index b7a1350..2c8f430 100644
--- a/lib/VMCore/ConstantFold.cpp
+++ b/lib/VMCore/ConstantFold.cpp
@@ -1466,8 +1466,8 @@ Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode,
 /// isZeroSizedType - This type is zero sized if its an array or structure of
 /// zero sized types.  The only leaf zero sized type is an empty structure.
 static bool isMaybeZeroSizedType(const Type *Ty) {
-  if (Ty->isOpaqueTy()) return true;  // Can't say.
   if (const StructType *STy = dyn_cast<StructType>(Ty)) {
+    if (STy->isOpaque()) return true;  // Can't say.
 
     // If all of elements have zero size, this does too.
     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
diff --git a/lib/VMCore/Constants.cpp b/lib/VMCore/Constants.cpp
index 4e6e64d..d3361cc 100644
--- a/lib/VMCore/Constants.cpp
+++ b/lib/VMCore/Constants.cpp
@@ -31,6 +31,7 @@
 #include "llvm/Support/GetElementPtrTypeIterator.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/STLExtras.h"
 #include <algorithm>
 #include <cstdarg>
 using namespace llvm;
@@ -639,13 +640,13 @@ ConstantStruct::ConstantStruct(const StructType *T,
   : Constant(T, ConstantStructVal,
              OperandTraits<ConstantStruct>::op_end(this) - V.size(),
              V.size()) {
-  assert(V.size() == T->getNumElements() &&
+  assert((T->isOpaque() || V.size() == T->getNumElements()) &&
          "Invalid initializer vector for constant structure");
   Use *OL = OperandList;
   for (std::vector<Constant*>::const_iterator I = V.begin(), E = V.end();
        I != E; ++I, ++OL) {
     Constant *C = *I;
-    assert(C->getType() == T->getElementType(I-V.begin()) &&
+    assert((T->isOpaque() || C->getType() == T->getElementType(I-V.begin())) &&
            "Initializer for struct element doesn't match struct element type!");
     *OL = C;
   }
@@ -653,14 +654,13 @@ ConstantStruct::ConstantStruct(const StructType *T,
 
 // ConstantStruct accessors.
 Constant *ConstantStruct::get(const StructType *ST, ArrayRef<Constant*> V) {
-  assert(ST->getNumElements() == V.size() &&
-         "Incorrect # elements specified to ConstantStruct::get");
-  
   // Create a ConstantAggregateZero value if all elements are zeros.
   for (unsigned i = 0, e = V.size(); i != e; ++i)
     if (!V[i]->isNullValue())
       return ST->getContext().pImpl->StructConstants.getOrCreate(ST, V);
 
+  assert((ST->isOpaque() || ST->getNumElements() == V.size()) &&
+         "Incorrect # elements specified to ConstantStruct::get");
   return ConstantAggregateZero::get(ST);
 }
 
@@ -839,17 +839,15 @@ ConstantExpr::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.
+/// operands replaced with the specified values.  The specified array must
+/// have the same number of operands as our current one.
 Constant *ConstantExpr::
-getWithOperands(ArrayRef<Constant*> Ops) const {
+getWithOperands(ArrayRef<Constant*> Ops, const Type *Ty) const {
   assert(Ops.size() == getNumOperands() && "Operand count mismatch!");
-  bool AnyChange = false;
-  for (unsigned i = 0; i != Ops.size(); ++i) {
-    assert(Ops[i]->getType() == getOperand(i)->getType() &&
-           "Operand type mismatch!");
+  bool AnyChange = Ty != getType();
+  for (unsigned i = 0; i != Ops.size(); ++i)
     AnyChange |= Ops[i] != getOperand(i);
-  }
+  
   if (!AnyChange)  // No operands changed, return self.
     return const_cast<ConstantExpr*>(this);
 
@@ -866,7 +864,7 @@ getWithOperands(ArrayRef<Constant*> Ops) const {
   case Instruction::PtrToInt:
   case Instruction::IntToPtr:
   case Instruction::BitCast:
-    return ConstantExpr::getCast(getOpcode(), Ops[0], getType());
+    return ConstantExpr::getCast(getOpcode(), Ops[0], Ty);
   case Instruction::Select:
     return ConstantExpr::getSelect(Ops[0], Ops[1], Ops[2]);
   case Instruction::InsertElement:
@@ -964,14 +962,14 @@ ConstantAggregateZero* ConstantAggregateZero::get(const Type* Ty) {
 /// destroyConstant - Remove the constant from the constant table...
 ///
 void ConstantAggregateZero::destroyConstant() {
-  getRawType()->getContext().pImpl->AggZeroConstants.remove(this);
+  getType()->getContext().pImpl->AggZeroConstants.remove(this);
   destroyConstantImpl();
 }
 
 /// destroyConstant - Remove the constant from the constant table...
 ///
 void ConstantArray::destroyConstant() {
-  getRawType()->getContext().pImpl->ArrayConstants.remove(this);
+  getType()->getContext().pImpl->ArrayConstants.remove(this);
   destroyConstantImpl();
 }
 
@@ -1050,14 +1048,14 @@ namespace llvm {
 // destroyConstant - Remove the constant from the constant table...
 //
 void ConstantStruct::destroyConstant() {
-  getRawType()->getContext().pImpl->StructConstants.remove(this);
+  getType()->getContext().pImpl->StructConstants.remove(this);
   destroyConstantImpl();
 }
 
 // destroyConstant - Remove the constant from the constant table...
 //
 void ConstantVector::destroyConstant() {
-  getRawType()->getContext().pImpl->VectorConstants.remove(this);
+  getType()->getContext().pImpl->VectorConstants.remove(this);
   destroyConstantImpl();
 }
 
@@ -1098,7 +1096,7 @@ ConstantPointerNull *ConstantPointerNull::get(const PointerType *Ty) {
 // destroyConstant - Remove the constant from the constant table...
 //
 void ConstantPointerNull::destroyConstant() {
-  getRawType()->getContext().pImpl->NullPtrConstants.remove(this);
+  getType()->getContext().pImpl->NullPtrConstants.remove(this);
   destroyConstantImpl();
 }
 
@@ -1113,7 +1111,7 @@ UndefValue *UndefValue::get(const Type *Ty) {
 // destroyConstant - Remove the constant from the constant table.
 //
 void UndefValue::destroyConstant() {
-  getRawType()->getContext().pImpl->UndefValueConstants.remove(this);
+  getType()->getContext().pImpl->UndefValueConstants.remove(this);
   destroyConstantImpl();
 }
 
@@ -1147,7 +1145,7 @@ BlockAddress::BlockAddress(Function *F, BasicBlock *BB)
 // destroyConstant - Remove the constant from the constant table.
 //
 void BlockAddress::destroyConstant() {
-  getFunction()->getRawType()->getContext().pImpl
+  getFunction()->getType()->getContext().pImpl
     ->BlockAddresses.erase(std::make_pair(getFunction(), getBasicBlock()));
   getBasicBlock()->AdjustBlockAddressRefCount(-1);
   destroyConstantImpl();
@@ -1921,7 +1919,7 @@ Constant *ConstantExpr::getAShr(Constant *C1, Constant *C2, bool isExact) {
 // destroyConstant - Remove the constant from the constant table...
 //
 void ConstantExpr::destroyConstant() {
-  getRawType()->getContext().pImpl->ExprConstants.remove(this);
+  getType()->getContext().pImpl->ExprConstants.remove(this);
   destroyConstantImpl();
 }
 
@@ -1962,10 +1960,10 @@ void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To,
   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
   Constant *ToC = cast<Constant>(To);
 
-  LLVMContextImpl *pImpl = getRawType()->getContext().pImpl;
+  LLVMContextImpl *pImpl = getType()->getContext().pImpl;
 
   std::pair<LLVMContextImpl::ArrayConstantsTy::MapKey, ConstantArray*> Lookup;
-  Lookup.first.first = cast<ArrayType>(getRawType());
+  Lookup.first.first = cast<ArrayType>(getType());
   Lookup.second = this;
 
   std::vector<Constant*> &Values = Lookup.first.second;
@@ -1999,7 +1997,7 @@ void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To,
   
   Constant *Replacement = 0;
   if (isAllZeros) {
-    Replacement = ConstantAggregateZero::get(getRawType());
+    Replacement = ConstantAggregateZero::get(getType());
   } else {
     // Check to see if we have this array type already.
     bool Exists;
@@ -2050,7 +2048,7 @@ void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To,
   assert(getOperand(OperandToUpdate) == From && "ReplaceAllUsesWith broken!");
 
   std::pair<LLVMContextImpl::StructConstantsTy::MapKey, ConstantStruct*> Lookup;
-  Lookup.first.first = cast<StructType>(getRawType());
+  Lookup.first.first = cast<StructType>(getType());
   Lookup.second = this;
   std::vector<Constant*> &Values = Lookup.first.second;
   Values.reserve(getNumOperands());  // Build replacement struct.
@@ -2072,11 +2070,11 @@ void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To,
   }
   Values[OperandToUpdate] = ToC;
   
-  LLVMContextImpl *pImpl = getRawType()->getContext().pImpl;
+  LLVMContextImpl *pImpl = getContext().pImpl;
   
   Constant *Replacement = 0;
   if (isAllZeros) {
-    Replacement = ConstantAggregateZero::get(getRawType());
+    Replacement = ConstantAggregateZero::get(getType());
   } else {
     // Check to see if we have this struct type already.
     bool Exists;
@@ -2167,7 +2165,7 @@ void ConstantExpr::replaceUsesOfWithOnConstant(Value *From, Value *ToV,
                                                &Indices[0], Indices.size());
   } else if (isCast()) {
     assert(getOperand(0) == From && "Cast only has one use!");
-    Replacement = ConstantExpr::getCast(getOpcode(), To, getRawType());
+    Replacement = ConstantExpr::getCast(getOpcode(), To, getType());
   } else if (getOpcode() == Instruction::Select) {
     Constant *C1 = getOperand(0);
     Constant *C2 = getOperand(1);
diff --git a/lib/VMCore/ConstantsContext.h b/lib/VMCore/ConstantsContext.h
index ea6ebe9..bd134d9 100644
--- a/lib/VMCore/ConstantsContext.h
+++ b/lib/VMCore/ConstantsContext.h
@@ -570,13 +570,11 @@ struct ConstantKeyData<InlineAsm> {
 
 template<class ValType, class ValRefType, class TypeClass, class ConstantClass,
          bool HasLargeKey = false /*true for arrays and structs*/ >
-class ConstantUniqueMap : public AbstractTypeUser {
+class ConstantUniqueMap {
 public:
   typedef std::pair<const TypeClass*, ValType> MapKey;
   typedef std::map<MapKey, ConstantClass *> MapTy;
   typedef std::map<ConstantClass *, typename MapTy::iterator> InverseMapTy;
-  typedef std::map<const DerivedType*, typename MapTy::iterator>
-    AbstractTypeMapTy;
 private:
   /// Map - This is the main map from the element descriptor to the Constants.
   /// This is the primary way we avoid creating two of the same shape
@@ -589,10 +587,6 @@ private:
   /// through the map with very large keys.
   InverseMapTy InverseMap;
 
-  /// AbstractTypeMap - Map for abstract type constants.
-  ///
-  AbstractTypeMapTy AbstractTypeMap;
-    
 public:
   typename MapTy::iterator map_begin() { return Map.begin(); }
   typename MapTy::iterator map_end() { return Map.end(); }
@@ -629,7 +623,7 @@ private:
     }
       
     typename MapTy::iterator I =
-      Map.find(MapKey(static_cast<const TypeClass*>(CP->getRawType()),
+      Map.find(MapKey(static_cast<const TypeClass*>(CP->getType()),
                       ConstantKeyData<ConstantClass>::getValType(CP)));
     if (I == Map.end() || I->second != CP) {
       // FIXME: This should not use a linear scan.  If this gets to be a
@@ -639,24 +633,8 @@ private:
     }
     return I;
   }
-    
-  void AddAbstractTypeUser(const Type *Ty, typename MapTy::iterator I) {
-    // If the type of the constant is abstract, make sure that an entry
-    // exists for it in the AbstractTypeMap.
-    if (Ty->isAbstract()) {
-      const DerivedType *DTy = static_cast<const DerivedType *>(Ty);
-      typename AbstractTypeMapTy::iterator TI = AbstractTypeMap.find(DTy);
-
-      if (TI == AbstractTypeMap.end()) {
-        // Add ourselves to the ATU list of the type.
-        cast<DerivedType>(DTy)->addAbstractTypeUser(this);
-
-        AbstractTypeMap.insert(TI, std::make_pair(DTy, I));
-      }
-    }
-  }
 
-  ConstantClass* Create(const TypeClass *Ty, ValRefType V,
+  ConstantClass *Create(const TypeClass *Ty, ValRefType V,
                         typename MapTy::iterator I) {
     ConstantClass* Result =
       ConstantCreator<ConstantClass,TypeClass,ValType>::create(Ty, V);
@@ -667,8 +645,6 @@ private:
     if (HasLargeKey)  // Remember the reverse mapping if needed.
       InverseMap.insert(std::make_pair(Result, I));
 
-    AddAbstractTypeUser(Ty, I);
-      
     return Result;
   }
 public:
@@ -692,43 +668,6 @@ public:
     return Result;
   }
 
-  void UpdateAbstractTypeMap(const DerivedType *Ty,
-                             typename MapTy::iterator I) {
-    assert(AbstractTypeMap.count(Ty) &&
-           "Abstract type not in AbstractTypeMap?");
-    typename MapTy::iterator &ATMEntryIt = AbstractTypeMap[Ty];
-    if (ATMEntryIt == I) {
-      // Yes, we are removing the representative entry for this type.
-      // See if there are any other entries of the same type.
-      typename MapTy::iterator TmpIt = ATMEntryIt;
-
-      // First check the entry before this one...
-      if (TmpIt != Map.begin()) {
-        --TmpIt;
-        if (TmpIt->first.first != Ty) // Not the same type, move back...
-          ++TmpIt;
-      }
-
-      // If we didn't find the same type, try to move forward...
-      if (TmpIt == ATMEntryIt) {
-        ++TmpIt;
-        if (TmpIt == Map.end() || TmpIt->first.first != Ty)
-          --TmpIt;   // No entry afterwards with the same type
-      }
-
-      // If there is another entry in the map of the same abstract type,
-      // update the AbstractTypeMap entry now.
-      if (TmpIt != ATMEntryIt) {
-        ATMEntryIt = TmpIt;
-      } else {
-        // Otherwise, we are removing the last instance of this type
-        // from the table.  Remove from the ATM, and from user list.
-        cast<DerivedType>(Ty)->removeAbstractTypeUser(this);
-        AbstractTypeMap.erase(Ty);
-      }
-    }
-  }
-
   void remove(ConstantClass *CP) {
     typename MapTy::iterator I = FindExistingElement(CP);
     assert(I != Map.end() && "Constant not found in constant table!");
@@ -736,12 +675,6 @@ public:
 
     if (HasLargeKey)  // Remember the reverse mapping if needed.
       InverseMap.erase(CP);
-      
-    // Now that we found the entry, make sure this isn't the entry that
-    // the AbstractTypeMap points to.
-    const TypeClass *Ty = I->first.first;
-    if (Ty->isAbstract())
-      UpdateAbstractTypeMap(static_cast<const DerivedType *>(Ty), I);
 
     Map.erase(I);
   }
@@ -755,22 +688,7 @@ public:
     assert(OldI != Map.end() && "Constant not found in constant table!");
     assert(OldI->second == C && "Didn't find correct element?");
       
-    // If this constant is the representative element for its abstract type,
-    // update the AbstractTypeMap so that the representative element is I.
-    //
-    // This must use getRawType() because if the type is under refinement, we
-    // will get the refineAbstractType callback below, and we don't want to
-    // kick union find in on the constant.
-    if (C->getRawType()->isAbstract()) {
-      typename AbstractTypeMapTy::iterator ATI =
-          AbstractTypeMap.find(cast<DerivedType>(C->getRawType()));
-      assert(ATI != AbstractTypeMap.end() &&
-             "Abstract type not in AbstractTypeMap?");
-      if (ATI->second == OldI)
-        ATI->second = I;
-    }
-      
-    // Remove the old entry from the map.
+     // Remove the old entry from the map.
     Map.erase(OldI);
     
     // Update the inverse map so that we know that this constant is now
@@ -780,58 +698,6 @@ public:
       InverseMap[C] = I;
     }
   }
-    
-  void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
-    typename AbstractTypeMapTy::iterator I = AbstractTypeMap.find(OldTy);
-
-    assert(I != AbstractTypeMap.end() &&
-           "Abstract type not in AbstractTypeMap?");
-
-    // Convert a constant at a time until the last one is gone.  The last one
-    // leaving will remove() itself, causing the AbstractTypeMapEntry to be
-    // eliminated eventually.
-    do {
-      ConstantClass *C = I->second->second;
-      MapKey Key(cast<TypeClass>(NewTy),
-                 ConstantKeyData<ConstantClass>::getValType(C));
-
-      std::pair<typename MapTy::iterator, bool> IP =
-        Map.insert(std::make_pair(Key, C));
-      if (IP.second) {
-        // The map didn't previously have an appropriate constant in the
-        // new type.
-        
-        // Remove the old entry.
-        typename MapTy::iterator OldI =
-          Map.find(MapKey(cast<TypeClass>(OldTy), IP.first->first.second));
-        assert(OldI != Map.end() && "Constant not in map!");
-        UpdateAbstractTypeMap(OldTy, OldI);
-        Map.erase(OldI);
-
-        // Set the constant's type. This is done in place!
-        setType(C, NewTy);
-
-        // Update the inverse map so that we know that this constant is now
-        // located at descriptor I.
-        if (HasLargeKey)
-          InverseMap[C] = IP.first;
-
-        AddAbstractTypeUser(NewTy, IP.first);
-      } else {
-        // The map already had an appropriate constant in the new type, so
-        // there's no longer a need for the old constant.
-        C->uncheckedReplaceAllUsesWith(IP.first->second);
-        C->destroyConstant();    // This constant is now dead, destroy it.
-      }
-      I = AbstractTypeMap.find(OldTy);
-    } while (I != AbstractTypeMap.end());
-  }
-
-  // If the type became concrete without being refined to any other existing
-  // type, we just remove ourselves from the ATU list.
-  void typeBecameConcrete(const DerivedType *AbsTy) {
-    AbsTy->removeAbstractTypeUser(this);
-  }
 
   void dump() const {
     DEBUG(dbgs() << "Constant.cpp: ConstantUniqueMap\n");
diff --git a/lib/VMCore/Core.cpp b/lib/VMCore/Core.cpp
index bdd988e..d9ced94 100644
--- a/lib/VMCore/Core.cpp
+++ b/lib/VMCore/Core.cpp
@@ -19,7 +19,6 @@
 #include "llvm/GlobalVariable.h"
 #include "llvm/GlobalAlias.h"
 #include "llvm/LLVMContext.h"
-#include "llvm/TypeSymbolTable.h"
 #include "llvm/InlineAsm.h"
 #include "llvm/IntrinsicInst.h"
 #include "llvm/PassManager.h"
@@ -111,27 +110,6 @@ void LLVMSetTarget(LLVMModuleRef M, const char *Triple) {
   unwrap(M)->setTargetTriple(Triple);
 }
 
-/*--.. Type names ..........................................................--*/
-LLVMBool LLVMAddTypeName(LLVMModuleRef M, const char *Name, LLVMTypeRef Ty) {
-  return unwrap(M)->addTypeName(Name, unwrap(Ty));
-}
-
-void LLVMDeleteTypeName(LLVMModuleRef M, const char *Name) {
-  TypeSymbolTable &TST = unwrap(M)->getTypeSymbolTable();
-
-  TypeSymbolTable::iterator I = TST.find(Name);
-  if (I != TST.end())
-    TST.remove(I);
-}
-
-LLVMTypeRef LLVMGetTypeByName(LLVMModuleRef M, const char *Name) {
-  return wrap(unwrap(M)->getTypeByName(Name));
-}
-
-const char *LLVMGetTypeName(LLVMModuleRef M, LLVMTypeRef Ty) {
-  return unwrap(M)->getTypeName(unwrap(Ty)).c_str();
-}
-
 void LLVMDumpModule(LLVMModuleRef M) {
   unwrap(M)->dump();
 }
@@ -182,8 +160,6 @@ LLVMTypeKind LLVMGetTypeKind(LLVMTypeRef Ty) {
     return LLVMArrayTypeKind;
   case Type::PointerTyID:
     return LLVMPointerTypeKind;
-  case Type::OpaqueTyID:
-    return LLVMOpaqueTypeKind;
   case Type::VectorTyID:
     return LLVMVectorTypeKind;
   case Type::X86_MMXTyID:
@@ -382,9 +358,6 @@ LLVMTypeRef LLVMVoidTypeInContext(LLVMContextRef C)  {
 LLVMTypeRef LLVMLabelTypeInContext(LLVMContextRef C) {
   return wrap(Type::getLabelTy(*unwrap(C)));
 }
-LLVMTypeRef LLVMOpaqueTypeInContext(LLVMContextRef C) {
-  return wrap(OpaqueType::get(*unwrap(C)));
-}
 
 LLVMTypeRef LLVMVoidType(void)  {
   return LLVMVoidTypeInContext(LLVMGetGlobalContext());
@@ -392,28 +365,6 @@ LLVMTypeRef LLVMVoidType(void)  {
 LLVMTypeRef LLVMLabelType(void) {
   return LLVMLabelTypeInContext(LLVMGetGlobalContext());
 }
-LLVMTypeRef LLVMOpaqueType(void) {
-  return LLVMOpaqueTypeInContext(LLVMGetGlobalContext());
-}
-
-/*--.. Operations on type handles ..........................................--*/
-
-LLVMTypeHandleRef LLVMCreateTypeHandle(LLVMTypeRef PotentiallyAbstractTy) {
-  return wrap(new PATypeHolder(unwrap(PotentiallyAbstractTy)));
-}
-
-void LLVMDisposeTypeHandle(LLVMTypeHandleRef TypeHandle) {
-  delete unwrap(TypeHandle);
-}
-
-LLVMTypeRef LLVMResolveTypeHandle(LLVMTypeHandleRef TypeHandle) {
-  return wrap(unwrap(TypeHandle)->get());
-}
-
-void LLVMRefineType(LLVMTypeRef AbstractTy, LLVMTypeRef ConcreteTy) {
-  unwrap<DerivedType>(AbstractTy)->refineAbstractTypeTo(unwrap(ConcreteTy));
-}
-
 
 /*===-- Operations on values ----------------------------------------------===*/
 
diff --git a/lib/VMCore/Function.cpp b/lib/VMCore/Function.cpp
index b8fa60a..972319e 100644
--- a/lib/VMCore/Function.cpp
+++ b/lib/VMCore/Function.cpp
@@ -134,7 +134,7 @@ LLVMContext &Function::getContext() const {
   return getType()->getContext();
 }
 
-const FunctionType *Function::getFunctionType() const {
+FunctionType *Function::getFunctionType() const {
   return cast<FunctionType>(getType()->getElementType());
 }
 
@@ -142,7 +142,7 @@ bool Function::isVarArg() const {
   return getFunctionType()->isVarArg();
 }
 
-const Type *Function::getReturnType() const {
+Type *Function::getReturnType() const {
   return getFunctionType()->getReturnType();
 }
 
@@ -163,7 +163,7 @@ Function::Function(const FunctionType *Ty, LinkageTypes Linkage,
   : GlobalValue(PointerType::getUnqual(Ty), 
                 Value::FunctionVal, 0, 0, Linkage, name) {
   assert(FunctionType::isValidReturnType(getReturnType()) &&
-         !getReturnType()->isOpaqueTy() && "invalid return type");
+         "invalid return type");
   SymTab = new ValueSymbolTable();
 
   // If the function has arguments, mark them as lazily built.
diff --git a/lib/VMCore/Globals.cpp b/lib/VMCore/Globals.cpp
index 60000ad..8f2d887 100644
--- a/lib/VMCore/Globals.cpp
+++ b/lib/VMCore/Globals.cpp
@@ -51,6 +51,7 @@ void GlobalValue::copyAttributesFrom(const GlobalValue *Src) {
   setAlignment(Src->getAlignment());
   setSection(Src->getSection());
   setVisibility(Src->getVisibility());
+  setUnnamedAddr(Src->hasUnnamedAddr());
 }
 
 void GlobalValue::setAlignment(unsigned Align) {
diff --git a/lib/VMCore/InlineAsm.cpp b/lib/VMCore/InlineAsm.cpp
index bd3667d..5ae4a1b 100644
--- a/lib/VMCore/InlineAsm.cpp
+++ b/lib/VMCore/InlineAsm.cpp
@@ -47,7 +47,7 @@ InlineAsm::InlineAsm(const PointerType *Ty, const std::string &asmString,
 }
 
 void InlineAsm::destroyConstant() {
-  getRawType()->getContext().pImpl->InlineAsms.remove(this);
+  getType()->getContext().pImpl->InlineAsms.remove(this);
   delete this;
 }
 
diff --git a/lib/VMCore/Instructions.cpp b/lib/VMCore/Instructions.cpp
index 0eddd5a..ecb3229 100644
--- a/lib/VMCore/Instructions.cpp
+++ b/lib/VMCore/Instructions.cpp
@@ -372,7 +372,7 @@ static Instruction *createMalloc(Instruction *InsertBefore,
   // Create the call to Malloc.
   BasicBlock* BB = InsertBefore ? InsertBefore->getParent() : InsertAtEnd;
   Module* M = BB->getParent()->getParent();
-  const Type *BPTy = Type::getInt8PtrTy(BB->getContext());
+  Type *BPTy = Type::getInt8PtrTy(BB->getContext());
   Value *MallocFunc = MallocF;
   if (!MallocFunc)
     // prototype malloc as "void *malloc(size_t)"
@@ -823,7 +823,7 @@ bool AllocaInst::isArrayAllocation() const {
   return true;
 }
 
-const Type *AllocaInst::getAllocatedType() const {
+Type *AllocaInst::getAllocatedType() const {
   return getType()->getElementType();
 }
 
@@ -1098,7 +1098,7 @@ GetElementPtrInst::GetElementPtrInst(const GetElementPtrInst &GEPI)
 GetElementPtrInst::GetElementPtrInst(Value *Ptr, Value *Idx,
                                      const Twine &Name, Instruction *InBe)
   : Instruction(PointerType::get(
-      checkType(getIndexedType(Ptr->getType(),Idx)), retrieveAddrSpace(Ptr)),
+      checkGEPType(getIndexedType(Ptr->getType(),Idx)), retrieveAddrSpace(Ptr)),
                 GetElementPtr,
                 OperandTraits<GetElementPtrInst>::op_end(this) - 2,
                 2, InBe) {
@@ -1108,7 +1108,7 @@ GetElementPtrInst::GetElementPtrInst(Value *Ptr, Value *Idx,
 GetElementPtrInst::GetElementPtrInst(Value *Ptr, Value *Idx,
                                      const Twine &Name, BasicBlock *IAE)
   : Instruction(PointerType::get(
-            checkType(getIndexedType(Ptr->getType(),Idx)),  
+            checkGEPType(getIndexedType(Ptr->getType(),Idx)),  
                 retrieveAddrSpace(Ptr)),
                 GetElementPtr,
                 OperandTraits<GetElementPtrInst>::op_end(this) - 2,
@@ -1126,60 +1126,50 @@ GetElementPtrInst::GetElementPtrInst(Value *Ptr, Value *Idx,
 /// pointer type.
 ///
 template <typename IndexTy>
-static const Type* getIndexedTypeInternal(const Type *Ptr, IndexTy const *Idxs,
-                                          unsigned NumIdx) {
+static Type *getIndexedTypeInternal(const Type *Ptr, IndexTy const *Idxs,
+                                    unsigned NumIdx) {
   const PointerType *PTy = dyn_cast<PointerType>(Ptr);
   if (!PTy) return 0;   // Type isn't a pointer type!
-  const Type *Agg = PTy->getElementType();
+  Type *Agg = PTy->getElementType();
 
   // Handle the special case of the empty set index set, which is always valid.
   if (NumIdx == 0)
     return Agg;
   
   // If there is at least one index, the top level type must be sized, otherwise
-  // it cannot be 'stepped over'.  We explicitly allow abstract types (those
-  // that contain opaque types) under the assumption that it will be resolved to
-  // a sane type later.
-  if (!Agg->isSized() && !Agg->isAbstract())
+  // it cannot be 'stepped over'.
+  if (!Agg->isSized())
     return 0;
 
   unsigned CurIdx = 1;
   for (; CurIdx != NumIdx; ++CurIdx) {
-    const CompositeType *CT = dyn_cast<CompositeType>(Agg);
+    CompositeType *CT = dyn_cast<CompositeType>(Agg);
     if (!CT || CT->isPointerTy()) return 0;
     IndexTy Index = Idxs[CurIdx];
     if (!CT->indexValid(Index)) return 0;
     Agg = CT->getTypeAtIndex(Index);
-
-    // If the new type forwards to another type, then it is in the middle
-    // of being refined to another type (and hence, may have dropped all
-    // references to what it was using before).  So, use the new forwarded
-    // type.
-    if (const Type *Ty = Agg->getForwardedType())
-      Agg = Ty;
   }
   return CurIdx == NumIdx ? Agg : 0;
 }
 
-const Type* GetElementPtrInst::getIndexedType(const Type *Ptr,
-                                              Value* const *Idxs,
-                                              unsigned NumIdx) {
+Type *GetElementPtrInst::getIndexedType(const Type *Ptr, Value* const *Idxs,
+                                        unsigned NumIdx) {
   return getIndexedTypeInternal(Ptr, Idxs, NumIdx);
 }
 
-const Type* GetElementPtrInst::getIndexedType(const Type *Ptr,
-                                              Constant* const *Idxs,
-                                              unsigned NumIdx) {
+Type *GetElementPtrInst::getIndexedType(const Type *Ptr,
+                                        Constant* const *Idxs,
+                                        unsigned NumIdx) {
   return getIndexedTypeInternal(Ptr, Idxs, NumIdx);
 }
 
-const Type* GetElementPtrInst::getIndexedType(const Type *Ptr,
-                                              uint64_t const *Idxs,
-                                              unsigned NumIdx) {
+Type *GetElementPtrInst::getIndexedType(const Type *Ptr,
+                                        uint64_t const *Idxs,
+                                        unsigned NumIdx) {
   return getIndexedTypeInternal(Ptr, Idxs, NumIdx);
 }
 
-const Type* GetElementPtrInst::getIndexedType(const Type *Ptr, Value *Idx) {
+Type *GetElementPtrInst::getIndexedType(const Type *Ptr, Value *Idx) {
   const PointerType *PTy = dyn_cast<PointerType>(Ptr);
   if (!PTy) return 0;   // Type isn't a pointer type!
 
@@ -1482,9 +1472,9 @@ ExtractValueInst::ExtractValueInst(const ExtractValueInst &EVI)
 // A null type is returned if the indices are invalid for the specified
 // pointer type.
 //
-const Type* ExtractValueInst::getIndexedType(const Type *Agg,
-                                             const unsigned *Idxs,
-                                             unsigned NumIdx) {
+Type *ExtractValueInst::getIndexedType(const Type *Agg,
+                                       const unsigned *Idxs,
+                                       unsigned NumIdx) {
   for (unsigned CurIdx = 0; CurIdx != NumIdx; ++CurIdx) {
     unsigned Index = Idxs[CurIdx];
     // We can't use CompositeType::indexValid(Index) here.
@@ -1505,19 +1495,11 @@ const Type* ExtractValueInst::getIndexedType(const Type *Agg,
     }
 
     Agg = cast<CompositeType>(Agg)->getTypeAtIndex(Index);
-
-    // If the new type forwards to another type, then it is in the middle
-    // of being refined to another type (and hence, may have dropped all
-    // references to what it was using before).  So, use the new forwarded
-    // type.
-    if (const Type *Ty = Agg->getForwardedType())
-      Agg = Ty;
   }
-  return Agg;
+  return const_cast<Type*>(Agg);
 }
 
-const Type* ExtractValueInst::getIndexedType(const Type *Agg,
-                                             unsigned Idx) {
+Type *ExtractValueInst::getIndexedType(const Type *Agg, unsigned Idx) {
   return getIndexedType(Agg, &Idx, 1);
 }
 
diff --git a/lib/VMCore/LLVMContextImpl.cpp b/lib/VMCore/LLVMContextImpl.cpp
index ccb8dc5..0b7ae6c 100644
--- a/lib/VMCore/LLVMContextImpl.cpp
+++ b/lib/VMCore/LLVMContextImpl.cpp
@@ -31,14 +31,10 @@ LLVMContextImpl::LLVMContextImpl(LLVMContext &C)
     Int8Ty(C, 8),
     Int16Ty(C, 16),
     Int32Ty(C, 32),
-    Int64Ty(C, 64),
-    AlwaysOpaqueTy(new OpaqueType(C)) {
+    Int64Ty(C, 64) {
   InlineAsmDiagHandler = 0;
   InlineAsmDiagContext = 0;
-      
-  // Make sure the AlwaysOpaqueTy stays alive as long as the Context.
-  AlwaysOpaqueTy->addRef();
-  OpaqueTypes.insert(AlwaysOpaqueTy);
+  NamedStructTypesUniqueID = 0;
 }
 
 namespace {
@@ -86,12 +82,7 @@ LLVMContextImpl::~LLVMContextImpl() {
        I != E; ++I) {
     delete I->second;
   }
-  AlwaysOpaqueTy->dropRef();
-  for (OpaqueTypesTy::iterator I = OpaqueTypes.begin(), E = OpaqueTypes.end();
-       I != E; ++I) {
-    (*I)->AbstractTypeUsers.clear();
-    delete *I;
-  }
+  
   // Destroy MDNodes.  ~MDNode can move and remove nodes between the MDNodeSet
   // and the NonUniquedMDNodes sets, so copy the values out first.
   SmallVector<MDNode*, 8> MDNodes;
@@ -109,7 +100,6 @@ LLVMContextImpl::~LLVMContextImpl() {
          "Destroying all MDNodes didn't empty the Context's sets.");
   // Destroy MDStrings.
   for (StringMap<MDString*>::iterator I = MDStringCache.begin(),
-         E = MDStringCache.end(); I != E; ++I) {
+         E = MDStringCache.end(); I != E; ++I)
     delete I->second;
-  }
 }
diff --git a/lib/VMCore/LLVMContextImpl.h b/lib/VMCore/LLVMContextImpl.h
index d8808b0..e36864b 100644
--- a/lib/VMCore/LLVMContextImpl.h
+++ b/lib/VMCore/LLVMContextImpl.h
@@ -15,10 +15,9 @@
 #ifndef LLVM_LLVMCONTEXT_IMPL_H
 #define LLVM_LLVMCONTEXT_IMPL_H
 
+#include "llvm/LLVMContext.h"
 #include "ConstantsContext.h"
 #include "LeaksContext.h"
-#include "TypesContext.h"
-#include "llvm/LLVMContext.h"
 #include "llvm/Constants.h"
 #include "llvm/DerivedTypes.h"
 #include "llvm/Metadata.h"
@@ -170,34 +169,22 @@ public:
   LeakDetectorImpl<Value> LLVMObjects;
   
   // Basic type instances.
-  const Type VoidTy;
-  const Type LabelTy;
-  const Type FloatTy;
-  const Type DoubleTy;
-  const Type MetadataTy;
-  const Type X86_FP80Ty;
-  const Type FP128Ty;
-  const Type PPC_FP128Ty;
-  const Type X86_MMXTy;
-  const IntegerType Int1Ty;
-  const IntegerType Int8Ty;
-  const IntegerType Int16Ty;
-  const IntegerType Int32Ty;
-  const IntegerType Int64Ty;
-
-  TypeMap<ArrayValType, ArrayType> ArrayTypes;
-  TypeMap<VectorValType, VectorType> VectorTypes;
-  TypeMap<PointerValType, PointerType> PointerTypes;
-  TypeMap<FunctionValType, FunctionType> FunctionTypes;
-  TypeMap<StructValType, StructType> StructTypes;
-  TypeMap<IntegerValType, IntegerType> IntegerTypes;
-
-  // Opaque types are not structurally uniqued, so don't use TypeMap.
-  typedef SmallPtrSet<const OpaqueType*, 8> OpaqueTypesTy;
-  OpaqueTypesTy OpaqueTypes;
-
-  /// Used as an abstract type that will never be resolved.
-  OpaqueType *const AlwaysOpaqueTy;
+  Type VoidTy, LabelTy, FloatTy, DoubleTy, MetadataTy;
+  Type X86_FP80Ty, FP128Ty, PPC_FP128Ty, X86_MMXTy;
+  IntegerType Int1Ty, Int8Ty, Int16Ty, Int32Ty, Int64Ty;
+
+  DenseMap<unsigned, IntegerType*> IntegerTypes;
+  
+  // TODO: Optimize FunctionTypes/AnonStructTypes!
+  std::map<std::vector<Type*>, FunctionType*> FunctionTypes;
+  std::map<std::vector<Type*>, StructType*> AnonStructTypes;
+  StringMap<StructType*> NamedStructTypes;
+  unsigned NamedStructTypesUniqueID;
+    
+  DenseMap<std::pair<Type *, uint64_t>, ArrayType*> ArrayTypes;
+  DenseMap<std::pair<Type *, unsigned>, VectorType*> VectorTypes;
+  DenseMap<Type*, PointerType*> PointerTypes;  // Pointers in AddrSpace = 0
+  DenseMap<std::pair<Type*, unsigned>, PointerType*> ASPointerTypes;
 
 
   /// ValueHandles - This map keeps track of all of the value handles that are
diff --git a/lib/VMCore/Metadata.cpp b/lib/VMCore/Metadata.cpp
index eb719e5..ace4dc2 100644
--- a/lib/VMCore/Metadata.cpp
+++ b/lib/VMCore/Metadata.cpp
@@ -19,6 +19,7 @@
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/STLExtras.h"
 #include "SymbolTableListTraitsImpl.h"
 #include "llvm/Support/LeakDetector.h"
 #include "llvm/Support/ValueHandle.h"
diff --git a/lib/VMCore/Module.cpp b/lib/VMCore/Module.cpp
index 341e527..1ca7016 100644
--- a/lib/VMCore/Module.cpp
+++ b/lib/VMCore/Module.cpp
@@ -17,12 +17,12 @@
 #include "llvm/DerivedTypes.h"
 #include "llvm/GVMaterializer.h"
 #include "llvm/LLVMContext.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/LeakDetector.h"
 #include "SymbolTableListTraitsImpl.h"
-#include "llvm/TypeSymbolTable.h"
 #include <algorithm>
 #include <cstdarg>
 #include <cstdlib>
@@ -60,7 +60,6 @@ template class llvm::SymbolTableListTraits<GlobalAlias, Module>;
 Module::Module(StringRef MID, LLVMContext& C)
   : Context(C), Materializer(NULL), ModuleID(MID) {
   ValSymTab = new ValueSymbolTable();
-  TypeSymTab = new TypeSymbolTable();
   NamedMDSymTab = new StringMap<NamedMDNode *>();
   Context.addModule(this);
 }
@@ -74,11 +73,10 @@ Module::~Module() {
   LibraryList.clear();
   NamedMDList.clear();
   delete ValSymTab;
-  delete TypeSymTab;
   delete static_cast<StringMap<NamedMDNode *> *>(NamedMDSymTab);
 }
 
-/// Target endian information...
+/// Target endian information.
 Module::Endianness Module::getEndianness() const {
   StringRef temp = DataLayout;
   Module::Endianness ret = AnyEndianness;
@@ -340,51 +338,6 @@ void Module::eraseNamedMetadata(NamedMDNode *NMD) {
   NamedMDList.erase(NMD);
 }
 
-//===----------------------------------------------------------------------===//
-// Methods for easy access to the types in the module.
-//
-
-
-// addTypeName - Insert an entry in the symbol table mapping Str to Type.  If
-// there is already an entry for this name, true is returned and the symbol
-// table is not modified.
-//
-bool Module::addTypeName(StringRef Name, const Type *Ty) {
-  TypeSymbolTable &ST = getTypeSymbolTable();
-
-  if (ST.lookup(Name)) return true;  // Already in symtab...
-
-  // Not in symbol table?  Set the name with the Symtab as an argument so the
-  // type knows what to update...
-  ST.insert(Name, Ty);
-
-  return false;
-}
-
-/// getTypeByName - Return the type with the specified name in this module, or
-/// null if there is none by that name.
-const Type *Module::getTypeByName(StringRef Name) const {
-  const TypeSymbolTable &ST = getTypeSymbolTable();
-  return cast_or_null<Type>(ST.lookup(Name));
-}
-
-// getTypeName - If there is at least one entry in the symbol table for the
-// specified type, return it.
-//
-std::string Module::getTypeName(const Type *Ty) const {
-  const TypeSymbolTable &ST = getTypeSymbolTable();
-
-  TypeSymbolTable::const_iterator TI = ST.begin();
-  TypeSymbolTable::const_iterator TE = ST.end();
-  if ( TI == TE ) return ""; // No names for types
-
-  while (TI != TE && TI->second != Ty)
-    ++TI;
-
-  if (TI != TE)  // Must have found an entry!
-    return TI->first;
-  return "";     // Must not have found anything...
-}
 
 //===----------------------------------------------------------------------===//
 // Methods to control the materialization of GlobalValues in the Module.
@@ -471,3 +424,130 @@ void Module::removeLibrary(StringRef Lib) {
       return;
     }
 }
+
+//===----------------------------------------------------------------------===//
+// Type finding functionality.
+//===----------------------------------------------------------------------===//
+
+namespace {
+  /// TypeFinder - Walk over a module, identifying all of the types that are
+  /// used by the module.
+  class TypeFinder {
+    // To avoid walking constant expressions multiple times and other IR
+    // objects, we keep several helper maps.
+    DenseSet<const Value*> VisitedConstants;
+    DenseSet<const Type*> VisitedTypes;
+    
+    std::vector<StructType*> &StructTypes;
+  public:
+    TypeFinder(std::vector<StructType*> &structTypes)
+      : StructTypes(structTypes) {}
+    
+    void run(const Module &M) {
+      // Get types from global variables.
+      for (Module::const_global_iterator I = M.global_begin(),
+           E = M.global_end(); I != E; ++I) {
+        incorporateType(I->getType());
+        if (I->hasInitializer())
+          incorporateValue(I->getInitializer());
+      }
+      
+      // Get types from aliases.
+      for (Module::const_alias_iterator I = M.alias_begin(),
+           E = M.alias_end(); I != E; ++I) {
+        incorporateType(I->getType());
+        if (const Value *Aliasee = I->getAliasee())
+          incorporateValue(Aliasee);
+      }
+      
+      SmallVector<std::pair<unsigned, MDNode*>, 4> MDForInst;
+
+      // Get types from functions.
+      for (Module::const_iterator FI = M.begin(), E = M.end(); FI != E; ++FI) {
+        incorporateType(FI->getType());
+        
+        for (Function::const_iterator BB = FI->begin(), E = FI->end();
+             BB != E;++BB)
+          for (BasicBlock::const_iterator II = BB->begin(),
+               E = BB->end(); II != E; ++II) {
+            const Instruction &I = *II;
+            // Incorporate the type of the instruction and all its operands.
+            incorporateType(I.getType());
+            for (User::const_op_iterator OI = I.op_begin(), OE = I.op_end();
+                 OI != OE; ++OI)
+              incorporateValue(*OI);
+            
+            // Incorporate types hiding in metadata.
+            I.getAllMetadata(MDForInst);
+            for (unsigned i = 0, e = MDForInst.size(); i != e; ++i)
+              incorporateMDNode(MDForInst[i].second);
+            MDForInst.clear();
+          }
+      }
+      
+      for (Module::const_named_metadata_iterator I = M.named_metadata_begin(),
+           E = M.named_metadata_end(); I != E; ++I) {
+        const NamedMDNode *NMD = I;
+        for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i)
+          incorporateMDNode(NMD->getOperand(i));
+      }
+    }
+    
+  private:
+    void incorporateType(Type *Ty) {
+      // Check to see if we're already visited this type.
+      if (!VisitedTypes.insert(Ty).second)
+        return;
+      
+      // If this is a structure or opaque type, add a name for the type.
+      if (StructType *STy = dyn_cast<StructType>(Ty))
+        StructTypes.push_back(STy);
+      
+      // Recursively walk all contained types.
+      for (Type::subtype_iterator I = Ty->subtype_begin(),
+           E = Ty->subtype_end(); I != E; ++I)
+        incorporateType(*I);
+    }
+    
+    /// incorporateValue - This method is used to walk operand lists finding
+    /// types hiding in constant expressions and other operands that won't be
+    /// walked in other ways.  GlobalValues, basic blocks, instructions, and
+    /// inst operands are all explicitly enumerated.
+    void incorporateValue(const Value *V) {
+      if (const MDNode *M = dyn_cast<MDNode>(V))
+        return incorporateMDNode(M);
+      if (!isa<Constant>(V) || isa<GlobalValue>(V)) return;
+      
+      // Already visited?
+      if (!VisitedConstants.insert(V).second)
+        return;
+      
+      // Check this type.
+      incorporateType(V->getType());
+      
+      // Look in operands for types.
+      const User *U = cast<User>(V);
+      for (Constant::const_op_iterator I = U->op_begin(),
+           E = U->op_end(); I != E;++I)
+        incorporateValue(*I);
+    }
+    
+    void incorporateMDNode(const MDNode *V) {
+      
+      // Already visited?
+      if (!VisitedConstants.insert(V).second)
+        return;
+      
+      // Look in operands for types.
+      for (unsigned i = 0, e = V->getNumOperands(); i != e; ++i)
+        if (Value *Op = V->getOperand(i))
+          incorporateValue(Op);
+    }
+  };
+} // end anonymous namespace
+
+void Module::findUsedStructTypes(std::vector<StructType*> &StructTypes) const {
+  TypeFinder(StructTypes).run(*this);
+}
+
+
diff --git a/lib/VMCore/Type.cpp b/lib/VMCore/Type.cpp
index 9299070..734d43a 100644
--- a/lib/VMCore/Type.cpp
+++ b/lib/VMCore/Type.cpp
@@ -12,81 +12,17 @@
 //===----------------------------------------------------------------------===//
 
 #include "LLVMContextImpl.h"
-#include "llvm/ADT/SCCIterator.h"
+#include "llvm/Module.h"
 #include <algorithm>
 #include <cstdarg>
+#include "llvm/ADT/SmallString.h"
 using namespace llvm;
 
-// 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.
-//
-// #define DEBUG_MERGE_TYPES 1
-
-AbstractTypeUser::~AbstractTypeUser() {}
-
-void AbstractTypeUser::setType(Value *V, const Type *NewTy) {
-  V->VTy = NewTy;
-}
-
 //===----------------------------------------------------------------------===//
 //                         Type Class Implementation
 //===----------------------------------------------------------------------===//
 
-/// Because of the way Type subclasses are allocated, this function is necessary
-/// to use the correct kind of "delete" operator to deallocate the Type object.
-/// Some type objects (FunctionTy, StructTy) allocate additional space
-/// after the space for their derived type to hold the contained types array of
-/// PATypeHandles. Using this allocation scheme means all the PATypeHandles are
-/// allocated with the type object, decreasing allocations and eliminating the
-/// need for a std::vector to be used in the Type class itself. 
-/// @brief Type destruction function
-void Type::destroy() const {
-  // Nothing calls getForwardedType from here on.
-  if (ForwardType && ForwardType->isAbstract()) {
-    ForwardType->dropRef();
-    ForwardType = NULL;
-  }
-
-  // Structures and Functions allocate their contained types past the end of
-  // the type object itself. These need to be destroyed differently than the
-  // other types.
-  if (this->isFunctionTy() || this->isStructTy()) {
-    // First, make sure we destruct any PATypeHandles allocated by these
-    // subclasses.  They must be manually destructed. 
-    for (unsigned i = 0; i < NumContainedTys; ++i)
-      ContainedTys[i].PATypeHandle::~PATypeHandle();
-
-    // Now call the destructor for the subclass directly because we're going
-    // to delete this as an array of char.
-    if (this->isFunctionTy())
-      static_cast<const FunctionType*>(this)->FunctionType::~FunctionType();
-    else {
-      assert(isStructTy());
-      static_cast<const StructType*>(this)->StructType::~StructType();
-    }
-
-    // Finally, remove the memory as an array deallocation of the chars it was
-    // constructed from.
-    operator delete(const_cast<Type *>(this));
-
-    return;
-  }
-  
-  if (const OpaqueType *opaque_this = dyn_cast<OpaqueType>(this)) {
-    LLVMContextImpl *pImpl = this->getContext().pImpl;
-    pImpl->OpaqueTypes.erase(opaque_this);
-  }
-
-  // For all the other type subclasses, there is either no contained types or 
-  // just one (all Sequentials). For Sequentials, the PATypeHandle is not
-  // allocated past the type object, its included directly in the SequentialType
-  // class. This means we can safely just do "normal" delete of this object and
-  // all the destructors that need to run will be run.
-  delete this; 
-}
-
-const Type *Type::getPrimitiveType(LLVMContext &C, TypeID IDNumber) {
+Type *Type::getPrimitiveType(LLVMContext &C, TypeID IDNumber) {
   switch (IDNumber) {
   case VoidTyID      : return getVoidTy(C);
   case FloatTyID     : return getFloatTy(C);
@@ -245,7 +181,11 @@ bool Type::isSizedDerivedType() const {
   if (!this->isStructTy()) 
     return false;
 
-  // Okay, our struct is sized if all of the elements are...
+  // Opaque structs have no size.
+  if (cast<StructType>(this)->isOpaque())
+    return false;
+  
+  // Okay, our struct is sized if all of the elements are.
   for (subtype_iterator I = subtype_begin(), E = subtype_end(); I != E; ++I)
     if (!(*I)->isSized()) 
       return false;
@@ -253,703 +193,346 @@ bool Type::isSizedDerivedType() const {
   return true;
 }
 
-/// getForwardedTypeInternal - This method is used to implement the union-find
-/// algorithm for when a type is being forwarded to another type.
-const Type *Type::getForwardedTypeInternal() const {
-  assert(ForwardType && "This type is not being forwarded to another type!");
-
-  // Check to see if the forwarded type has been forwarded on.  If so, collapse
-  // the forwarding links.
-  const Type *RealForwardedType = ForwardType->getForwardedType();
-  if (!RealForwardedType)
-    return ForwardType;  // No it's not forwarded again
-
-  // Yes, it is forwarded again.  First thing, add the reference to the new
-  // forward type.
-  if (RealForwardedType->isAbstract())
-    RealForwardedType->addRef();
-
-  // Now drop the old reference.  This could cause ForwardType to get deleted.
-  // ForwardType must be abstract because only abstract types can have their own
-  // ForwardTypes.
-  ForwardType->dropRef();
-
-  // Return the updated type.
-  ForwardType = RealForwardedType;
-  return ForwardType;
-}
-
-void Type::refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
-  llvm_unreachable("Attempting to refine a derived type!");
-}
-void Type::typeBecameConcrete(const DerivedType *AbsTy) {
-  llvm_unreachable("DerivedType is already a concrete type!");
-}
-
-const Type *CompositeType::getTypeAtIndex(const Value *V) const {
-  if (const StructType *STy = dyn_cast<StructType>(this)) {
-    unsigned Idx = (unsigned)cast<ConstantInt>(V)->getZExtValue();
-    assert(indexValid(Idx) && "Invalid structure index!");
-    return STy->getElementType(Idx);
-  }
-    
-  return cast<SequentialType>(this)->getElementType();
-}
-const Type *CompositeType::getTypeAtIndex(unsigned Idx) const {
-  if (const StructType *STy = dyn_cast<StructType>(this)) {
-    assert(indexValid(Idx) && "Invalid structure index!");
-    return STy->getElementType(Idx);
-  }
-  
-  return cast<SequentialType>(this)->getElementType();
-}
-bool CompositeType::indexValid(const Value *V) const {
-  if (const StructType *STy = dyn_cast<StructType>(this)) {
-    // Structure indexes require 32-bit integer constants.
-    if (V->getType()->isIntegerTy(32))
-      if (const ConstantInt *CU = dyn_cast<ConstantInt>(V))
-        return CU->getZExtValue() < STy->getNumElements();
-    return false;
-  }
-  
-  // Sequential types can be indexed by any integer.
-  return V->getType()->isIntegerTy();
-}
-
-bool CompositeType::indexValid(unsigned Idx) const {
-  if (const StructType *STy = dyn_cast<StructType>(this))
-    return Idx < STy->getNumElements();
-  // Sequential types can be indexed by any integer.
-  return true;
-}
-
-
 //===----------------------------------------------------------------------===//
 //                          Primitive 'Type' data
 //===----------------------------------------------------------------------===//
 
-const Type *Type::getVoidTy(LLVMContext &C) {
-  return &C.pImpl->VoidTy;
-}
-
-const Type *Type::getLabelTy(LLVMContext &C) {
-  return &C.pImpl->LabelTy;
-}
-
-const Type *Type::getFloatTy(LLVMContext &C) {
-  return &C.pImpl->FloatTy;
-}
-
-const Type *Type::getDoubleTy(LLVMContext &C) {
-  return &C.pImpl->DoubleTy;
-}
-
-const Type *Type::getMetadataTy(LLVMContext &C) {
-  return &C.pImpl->MetadataTy;
-}
-
-const Type *Type::getX86_FP80Ty(LLVMContext &C) {
-  return &C.pImpl->X86_FP80Ty;
-}
-
-const Type *Type::getFP128Ty(LLVMContext &C) {
-  return &C.pImpl->FP128Ty;
-}
-
-const Type *Type::getPPC_FP128Ty(LLVMContext &C) {
-  return &C.pImpl->PPC_FP128Ty;
-}
-
-const Type *Type::getX86_MMXTy(LLVMContext &C) {
-  return &C.pImpl->X86_MMXTy;
-}
-
-const IntegerType *Type::getIntNTy(LLVMContext &C, unsigned N) {
+Type *Type::getVoidTy(LLVMContext &C) { return &C.pImpl->VoidTy; }
+Type *Type::getLabelTy(LLVMContext &C) { return &C.pImpl->LabelTy; }
+Type *Type::getFloatTy(LLVMContext &C) { return &C.pImpl->FloatTy; }
+Type *Type::getDoubleTy(LLVMContext &C) { return &C.pImpl->DoubleTy; }
+Type *Type::getMetadataTy(LLVMContext &C) { return &C.pImpl->MetadataTy; }
+Type *Type::getX86_FP80Ty(LLVMContext &C) { return &C.pImpl->X86_FP80Ty; }
+Type *Type::getFP128Ty(LLVMContext &C) { return &C.pImpl->FP128Ty; }
+Type *Type::getPPC_FP128Ty(LLVMContext &C) { return &C.pImpl->PPC_FP128Ty; }
+Type *Type::getX86_MMXTy(LLVMContext &C) { return &C.pImpl->X86_MMXTy; }
+
+IntegerType *Type::getInt1Ty(LLVMContext &C) { return &C.pImpl->Int1Ty; }
+IntegerType *Type::getInt8Ty(LLVMContext &C) { return &C.pImpl->Int8Ty; }
+IntegerType *Type::getInt16Ty(LLVMContext &C) { return &C.pImpl->Int16Ty; }
+IntegerType *Type::getInt32Ty(LLVMContext &C) { return &C.pImpl->Int32Ty; }
+IntegerType *Type::getInt64Ty(LLVMContext &C) { return &C.pImpl->Int64Ty; }
+
+IntegerType *Type::getIntNTy(LLVMContext &C, unsigned N) {
   return IntegerType::get(C, N);
 }
 
-const IntegerType *Type::getInt1Ty(LLVMContext &C) {
-  return &C.pImpl->Int1Ty;
-}
-
-const IntegerType *Type::getInt8Ty(LLVMContext &C) {
-  return &C.pImpl->Int8Ty;
-}
-
-const IntegerType *Type::getInt16Ty(LLVMContext &C) {
-  return &C.pImpl->Int16Ty;
-}
-
-const IntegerType *Type::getInt32Ty(LLVMContext &C) {
-  return &C.pImpl->Int32Ty;
-}
-
-const IntegerType *Type::getInt64Ty(LLVMContext &C) {
-  return &C.pImpl->Int64Ty;
-}
-
-const PointerType *Type::getFloatPtrTy(LLVMContext &C, unsigned AS) {
+PointerType *Type::getFloatPtrTy(LLVMContext &C, unsigned AS) {
   return getFloatTy(C)->getPointerTo(AS);
 }
 
-const PointerType *Type::getDoublePtrTy(LLVMContext &C, unsigned AS) {
+PointerType *Type::getDoublePtrTy(LLVMContext &C, unsigned AS) {
   return getDoubleTy(C)->getPointerTo(AS);
 }
 
-const PointerType *Type::getX86_FP80PtrTy(LLVMContext &C, unsigned AS) {
+PointerType *Type::getX86_FP80PtrTy(LLVMContext &C, unsigned AS) {
   return getX86_FP80Ty(C)->getPointerTo(AS);
 }
 
-const PointerType *Type::getFP128PtrTy(LLVMContext &C, unsigned AS) {
+PointerType *Type::getFP128PtrTy(LLVMContext &C, unsigned AS) {
   return getFP128Ty(C)->getPointerTo(AS);
 }
 
-const PointerType *Type::getPPC_FP128PtrTy(LLVMContext &C, unsigned AS) {
+PointerType *Type::getPPC_FP128PtrTy(LLVMContext &C, unsigned AS) {
   return getPPC_FP128Ty(C)->getPointerTo(AS);
 }
 
-const PointerType *Type::getX86_MMXPtrTy(LLVMContext &C, unsigned AS) {
+PointerType *Type::getX86_MMXPtrTy(LLVMContext &C, unsigned AS) {
   return getX86_MMXTy(C)->getPointerTo(AS);
 }
 
-const PointerType *Type::getIntNPtrTy(LLVMContext &C, unsigned N, unsigned AS) {
+PointerType *Type::getIntNPtrTy(LLVMContext &C, unsigned N, unsigned AS) {
   return getIntNTy(C, N)->getPointerTo(AS);
 }
 
-const PointerType *Type::getInt1PtrTy(LLVMContext &C, unsigned AS) {
+PointerType *Type::getInt1PtrTy(LLVMContext &C, unsigned AS) {
   return getInt1Ty(C)->getPointerTo(AS);
 }
 
-const PointerType *Type::getInt8PtrTy(LLVMContext &C, unsigned AS) {
+PointerType *Type::getInt8PtrTy(LLVMContext &C, unsigned AS) {
   return getInt8Ty(C)->getPointerTo(AS);
 }
 
-const PointerType *Type::getInt16PtrTy(LLVMContext &C, unsigned AS) {
+PointerType *Type::getInt16PtrTy(LLVMContext &C, unsigned AS) {
   return getInt16Ty(C)->getPointerTo(AS);
 }
 
-const PointerType *Type::getInt32PtrTy(LLVMContext &C, unsigned AS) {
+PointerType *Type::getInt32PtrTy(LLVMContext &C, unsigned AS) {
   return getInt32Ty(C)->getPointerTo(AS);
 }
 
-const PointerType *Type::getInt64PtrTy(LLVMContext &C, unsigned AS) {
+PointerType *Type::getInt64PtrTy(LLVMContext &C, unsigned AS) {
   return getInt64Ty(C)->getPointerTo(AS);
 }
 
+
 //===----------------------------------------------------------------------===//
-//                          Derived Type Constructors
+//                       IntegerType Implementation
 //===----------------------------------------------------------------------===//
 
-/// isValidReturnType - Return true if the specified type is valid as a return
-/// type.
-bool FunctionType::isValidReturnType(const Type *RetTy) {
-  return !RetTy->isFunctionTy() && !RetTy->isLabelTy() &&
-         !RetTy->isMetadataTy();
+IntegerType *IntegerType::get(LLVMContext &C, unsigned NumBits) {
+  assert(NumBits >= MIN_INT_BITS && "bitwidth too small");
+  assert(NumBits <= MAX_INT_BITS && "bitwidth too large");
+  
+  // Check for the built-in integer types
+  switch (NumBits) {
+  case  1: return cast<IntegerType>(Type::getInt1Ty(C));
+  case  8: return cast<IntegerType>(Type::getInt8Ty(C));
+  case 16: return cast<IntegerType>(Type::getInt16Ty(C));
+  case 32: return cast<IntegerType>(Type::getInt32Ty(C));
+  case 64: return cast<IntegerType>(Type::getInt64Ty(C));
+  default: 
+    break;
+  }
+  
+  IntegerType *&Entry = C.pImpl->IntegerTypes[NumBits];
+  
+  if (Entry == 0)
+    Entry = new IntegerType(C, NumBits);
+  
+  return Entry;
 }
 
-/// isValidArgumentType - Return true if the specified type is valid as an
-/// argument type.
-bool FunctionType::isValidArgumentType(const Type *ArgTy) {
-  return ArgTy->isFirstClassType() || ArgTy->isOpaqueTy();
+bool IntegerType::isPowerOf2ByteWidth() const {
+  unsigned BitWidth = getBitWidth();
+  return (BitWidth > 7) && isPowerOf2_32(BitWidth);
+}
+
+APInt IntegerType::getMask() const {
+  return APInt::getAllOnesValue(getBitWidth());
 }
 
-FunctionType::FunctionType(const Type *Result,
-                           ArrayRef<const Type*> Params,
+//===----------------------------------------------------------------------===//
+//                       FunctionType Implementation
+//===----------------------------------------------------------------------===//
+
+FunctionType::FunctionType(const Type *Result, ArrayRef<Type*> Params,
                            bool IsVarArgs)
   : DerivedType(Result->getContext(), FunctionTyID) {
-  ContainedTys = reinterpret_cast<PATypeHandle*>(this+1);
-  NumContainedTys = Params.size() + 1; // + 1 for result type
+  Type **SubTys = reinterpret_cast<Type**>(this+1);
   assert(isValidReturnType(Result) && "invalid return type for function");
   setSubclassData(IsVarArgs);
 
-  bool isAbstract = Result->isAbstract();
-  new (&ContainedTys[0]) PATypeHandle(Result, this);
+  SubTys[0] = const_cast<Type*>(Result);
 
-  for (unsigned i = 0; i != Params.size(); ++i) {
+  for (unsigned i = 0, e = Params.size(); i != e; ++i) {
     assert(isValidArgumentType(Params[i]) &&
            "Not a valid type for function argument!");
-    new (&ContainedTys[i+1]) PATypeHandle(Params[i], this);
-    isAbstract |= Params[i]->isAbstract();
-  }
-
-  // Calculate whether or not this type is abstract
-  setAbstract(isAbstract);
-}
-
-StructType::StructType(LLVMContext &C, 
-                       ArrayRef<const Type*> Types, bool isPacked)
-  : CompositeType(C, StructTyID) {
-  ContainedTys = reinterpret_cast<PATypeHandle*>(this + 1);
-  NumContainedTys = Types.size();
-  setSubclassData(isPacked);
-  bool isAbstract = false;
-  for (unsigned i = 0; i < Types.size(); ++i) {
-    assert(Types[i] && "<null> type for structure field!");
-    assert(isValidElementType(Types[i]) &&
-           "Invalid type for structure element!");
-    new (&ContainedTys[i]) PATypeHandle(Types[i], this);
-    isAbstract |= Types[i]->isAbstract();
+    SubTys[i+1] = Params[i];
   }
 
-  // Calculate whether or not this type is abstract
-  setAbstract(isAbstract);
-}
-
-ArrayType::ArrayType(const Type *ElType, uint64_t NumEl)
-  : SequentialType(ArrayTyID, ElType) {
-  NumElements = NumEl;
-
-  // Calculate whether or not this type is abstract
-  setAbstract(ElType->isAbstract());
+  ContainedTys = SubTys;
+  NumContainedTys = Params.size() + 1; // + 1 for result type
 }
 
-VectorType::VectorType(const Type *ElType, unsigned NumEl)
-  : SequentialType(VectorTyID, ElType) {
-  NumElements = NumEl;
-  setAbstract(ElType->isAbstract());
-  assert(NumEl > 0 && "NumEl of a VectorType must be greater than 0");
-  assert(isValidElementType(ElType) &&
-         "Elements of a VectorType must be a primitive type");
-
+// FIXME: Remove this version.
+FunctionType *FunctionType::get(const Type *ReturnType,
+                                ArrayRef<const Type*> Params, bool isVarArg) {
+  return get(ReturnType, ArrayRef<Type*>(const_cast<Type**>(Params.data()),
+                                         Params.size()), isVarArg);
 }
 
+// FunctionType::get - The factory function for the FunctionType class.
+FunctionType *FunctionType::get(const Type *ReturnType,
+                                ArrayRef<Type*> Params, bool isVarArg) {
+  // TODO: This is brutally slow.
+  std::vector<Type*> Key;
+  Key.reserve(Params.size()+2);
+  Key.push_back(const_cast<Type*>(ReturnType));
+  for (unsigned i = 0, e = Params.size(); i != e; ++i)
+    Key.push_back(const_cast<Type*>(Params[i]));
+  if (isVarArg)
+    Key.push_back(0);
+  
+  FunctionType *&FT = ReturnType->getContext().pImpl->FunctionTypes[Key];
+  
+  if (FT == 0) {
+    FT = (FunctionType*) operator new(sizeof(FunctionType) +
+                                    sizeof(Type*)*(Params.size()+1));
+    new (FT) FunctionType(ReturnType, Params, isVarArg);
+  }
 
-PointerType::PointerType(const Type *E, unsigned AddrSpace)
-  : SequentialType(PointerTyID, E) {
-  setSubclassData(AddrSpace);
-  // Calculate whether or not this type is abstract
-  setAbstract(E->isAbstract());
-}
-
-OpaqueType::OpaqueType(LLVMContext &C) : DerivedType(C, OpaqueTyID) {
-  setAbstract(true);
-#ifdef DEBUG_MERGE_TYPES
-  DEBUG(dbgs() << "Derived new type: " << *this << "\n");
-#endif
+  return FT;
 }
 
-void PATypeHolder::destroy() {
-  Ty = 0;
-}
 
-// 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 DerivedType::dropAllTypeUses() {
-  if (NumContainedTys != 0) {
-    // The type must stay abstract.  To do this, we insert a pointer to a type
-    // that will never get resolved, thus will always be abstract.
-    ContainedTys[0] = getContext().pImpl->AlwaysOpaqueTy;
-
-    // Change the rest of the types to be Int32Ty's.  It doesn't matter what we
-    // pick so long as it doesn't point back to this type.  We choose something
-    // concrete to avoid overhead for adding to AbstractTypeUser lists and
-    // stuff.
-    const Type *ConcreteTy = Type::getInt32Ty(getContext());
-    for (unsigned i = 1, e = NumContainedTys; i != e; ++i)
-      ContainedTys[i] = ConcreteTy;
-  }
+FunctionType *FunctionType::get(const Type *Result, bool isVarArg) {
+  return get(Result, ArrayRef<const Type *>(), isVarArg);
 }
 
 
-namespace {
-
-/// TypePromotionGraph and graph traits - this is designed to allow us to do
-/// efficient SCC processing of type graphs.  This is the exact same as
-/// GraphTraits<Type*>, except that we pretend that concrete types have no
-/// children to avoid processing them.
-struct TypePromotionGraph {
-  Type *Ty;
-  TypePromotionGraph(Type *T) : Ty(T) {}
-};
-
-}
-
-namespace llvm {
-  template <> struct GraphTraits<TypePromotionGraph> {
-    typedef Type NodeType;
-    typedef Type::subtype_iterator ChildIteratorType;
-
-    static inline NodeType *getEntryNode(TypePromotionGraph G) { return G.Ty; }
-    static inline ChildIteratorType child_begin(NodeType *N) {
-      if (N->isAbstract())
-        return N->subtype_begin();
-      // No need to process children of concrete types.
-      return N->subtype_end();
-    }
-    static inline ChildIteratorType child_end(NodeType *N) {
-      return N->subtype_end();
-    }
-  };
+/// isValidReturnType - Return true if the specified type is valid as a return
+/// type.
+bool FunctionType::isValidReturnType(const Type *RetTy) {
+  return !RetTy->isFunctionTy() && !RetTy->isLabelTy() &&
+  !RetTy->isMetadataTy();
 }
 
-
-// PromoteAbstractToConcrete - This is a recursive function that walks a type
-// graph calculating whether or not a type is abstract.
-//
-void Type::PromoteAbstractToConcrete() {
-  if (!isAbstract()) return;
-
-  scc_iterator<TypePromotionGraph> SI = scc_begin(TypePromotionGraph(this));
-  scc_iterator<TypePromotionGraph> SE = scc_end  (TypePromotionGraph(this));
-
-  for (; SI != SE; ++SI) {
-    std::vector<Type*> &SCC = *SI;
-
-    // Concrete types are leaves in the tree.  Since an SCC will either be all
-    // abstract or all concrete, we only need to check one type.
-    if (!SCC[0]->isAbstract()) continue;
-    
-    if (SCC[0]->isOpaqueTy())
-      return;     // Not going to be concrete, sorry.
-
-    // If all of the children of all of the types in this SCC are concrete,
-    // then this SCC is now concrete as well.  If not, neither this SCC, nor
-    // any parent SCCs will be concrete, so we might as well just exit.
-    for (unsigned i = 0, e = SCC.size(); i != e; ++i)
-      for (Type::subtype_iterator CI = SCC[i]->subtype_begin(),
-             E = SCC[i]->subtype_end(); CI != E; ++CI)
-        if ((*CI)->isAbstract())
-          // If the child type is in our SCC, it doesn't make the entire SCC
-          // abstract unless there is a non-SCC abstract type.
-          if (std::find(SCC.begin(), SCC.end(), *CI) == SCC.end())
-            return;               // Not going to be concrete, sorry.
-
-    // Okay, we just discovered this whole SCC is now concrete, mark it as
-    // such!
-    for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
-      assert(SCC[i]->isAbstract() && "Why are we processing concrete types?");
-
-      SCC[i]->setAbstract(false);
-    }
-
-    for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
-      assert(!SCC[i]->isAbstract() && "Concrete type became abstract?");
-      // The type just became concrete, notify all users!
-      cast<DerivedType>(SCC[i])->notifyUsesThatTypeBecameConcrete();
-    }
-  }
+/// isValidArgumentType - Return true if the specified type is valid as an
+/// argument type.
+bool FunctionType::isValidArgumentType(const Type *ArgTy) {
+  return ArgTy->isFirstClassType();
 }
 
-
 //===----------------------------------------------------------------------===//
-//                      Type Structural Equality Testing
+//                       StructType Implementation
 //===----------------------------------------------------------------------===//
 
-// TypesEqual - Two types are considered structurally equal if they have the
-// same "shape": Every level and element of the types have identical primitive
-// ID's, and the graphs have the same edges/nodes in them.  Nodes do not have to
-// be pointer equals to be equivalent though.  This uses an optimistic algorithm
-// that assumes that two graphs are the same until proven otherwise.
-//
-static bool TypesEqual(const Type *Ty, const Type *Ty2,
-                       std::map<const Type *, const Type *> &EqTypes) {
-  if (Ty == Ty2) return true;
-  if (Ty->getTypeID() != Ty2->getTypeID()) return false;
-  if (Ty->isOpaqueTy())
-    return false;  // Two unequal opaque types are never equal
-
-  std::map<const Type*, const Type*>::iterator It = EqTypes.find(Ty);
-  if (It != EqTypes.end())
-    return It->second == Ty2;    // Looping back on a type, check for equality
-
-  // Otherwise, add the mapping to the table to make sure we don't get
-  // recursion on the types...
-  EqTypes.insert(It, std::make_pair(Ty, Ty2));
-
-  // Two really annoying special cases that breaks an otherwise nice simple
-  // algorithm is the fact that arraytypes have sizes that differentiates types,
-  // and that function types can be varargs or not.  Consider this now.
-  //
-  if (const IntegerType *ITy = dyn_cast<IntegerType>(Ty)) {
-    const IntegerType *ITy2 = cast<IntegerType>(Ty2);
-    return ITy->getBitWidth() == ITy2->getBitWidth();
-  }
-  
-  if (const PointerType *PTy = dyn_cast<PointerType>(Ty)) {
-    const PointerType *PTy2 = cast<PointerType>(Ty2);
-    return PTy->getAddressSpace() == PTy2->getAddressSpace() &&
-           TypesEqual(PTy->getElementType(), PTy2->getElementType(), EqTypes);
+// Primitive Constructors.
+
+StructType *StructType::get(LLVMContext &Context, ArrayRef<Type*> ETypes, 
+                            bool isPacked) {
+  // FIXME: std::vector is horribly inefficient for this probe.
+  std::vector<Type*> Key;
+  for (unsigned i = 0, e = ETypes.size(); i != e; ++i) {
+    assert(isValidElementType(ETypes[i]) &&
+           "Invalid type for structure element!");
+    Key.push_back(ETypes[i]);
   }
+  if (isPacked)
+    Key.push_back(0);
   
-  if (const StructType *STy = dyn_cast<StructType>(Ty)) {
-    const StructType *STy2 = cast<StructType>(Ty2);
-    if (STy->getNumElements() != STy2->getNumElements()) return false;
-    if (STy->isPacked() != STy2->isPacked()) return false;
-    for (unsigned i = 0, e = STy2->getNumElements(); i != e; ++i)
-      if (!TypesEqual(STy->getElementType(i), STy2->getElementType(i), EqTypes))
-        return false;
-    return true;
-  }
+  StructType *&ST = Context.pImpl->AnonStructTypes[Key];
+    
+  if (ST) return ST;
   
-  if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
-    const ArrayType *ATy2 = cast<ArrayType>(Ty2);
-    return ATy->getNumElements() == ATy2->getNumElements() &&
-           TypesEqual(ATy->getElementType(), ATy2->getElementType(), EqTypes);
-  }
+  // Value not found.  Create a new type!
+  ST = new StructType(Context);
+  ST->setSubclassData(SCDB_IsAnonymous);  // Anonymous struct.
+  ST->setBody(ETypes, isPacked);
+  return ST;
+}
+
+void StructType::setBody(ArrayRef<Type*> Elements, bool isPacked) {
+  assert(isOpaque() && "Struct body already set!");
   
-  if (const VectorType *PTy = dyn_cast<VectorType>(Ty)) {
-    const VectorType *PTy2 = cast<VectorType>(Ty2);
-    return PTy->getNumElements() == PTy2->getNumElements() &&
-           TypesEqual(PTy->getElementType(), PTy2->getElementType(), EqTypes);
-  }
+  setSubclassData(getSubclassData() | SCDB_HasBody);
+  if (isPacked)
+    setSubclassData(getSubclassData() | SCDB_Packed);
   
-  if (const FunctionType *FTy = dyn_cast<FunctionType>(Ty)) {
-    const FunctionType *FTy2 = cast<FunctionType>(Ty2);
-    if (FTy->isVarArg() != FTy2->isVarArg() ||
-        FTy->getNumParams() != FTy2->getNumParams() ||
-        !TypesEqual(FTy->getReturnType(), FTy2->getReturnType(), EqTypes))
-      return false;
-    for (unsigned i = 0, e = FTy2->getNumParams(); i != e; ++i) {
-      if (!TypesEqual(FTy->getParamType(i), FTy2->getParamType(i), EqTypes))
-        return false;
-    }
-    return true;
-  }
+  Type **Elts = new Type*[Elements.size()];
+  memcpy(Elts, Elements.data(), sizeof(Elements[0])*Elements.size());
   
-  llvm_unreachable("Unknown derived type!");
-  return false;
-}
-
-namespace llvm { // in namespace llvm so findable by ADL
-static bool TypesEqual(const Type *Ty, const Type *Ty2) {
-  std::map<const Type *, const Type *> EqTypes;
-  return ::TypesEqual(Ty, Ty2, EqTypes);
-}
-}
-
-// 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,
-                                SmallPtrSet<const Type*, 128> &VisitedTypes) {
-  if (TargetTy == CurTy) return true;
-  if (!CurTy->isAbstract()) return false;
-
-  if (!VisitedTypes.insert(CurTy))
-    return false;  // Already been here.
-
-  for (Type::subtype_iterator I = CurTy->subtype_begin(),
-       E = CurTy->subtype_end(); I != E; ++I)
-    if (AbstractTypeHasCycleThrough(TargetTy, *I, VisitedTypes))
-      return true;
-  return false;
+  ContainedTys = Elts;
+  NumContainedTys = Elements.size();
 }
 
-static bool ConcreteTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy,
-                                SmallPtrSet<const Type*, 128> &VisitedTypes) {
-  if (TargetTy == CurTy) return true;
-
-  if (!VisitedTypes.insert(CurTy))
-    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.
-
-namespace llvm { // in namespace llvm so it's findable by ADL
-static bool TypeHasCycleThroughItself(const Type *Ty) {
-  SmallPtrSet<const Type*, 128> VisitedTypes;
-
-  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;
-}
+StructType *StructType::createNamed(LLVMContext &Context, StringRef Name) {
+  StructType *ST = new StructType(Context);
+  ST->setName(Name);
+  return ST;
 }
 
-//===----------------------------------------------------------------------===//
-// Function Type Factory and Value Class...
-//
-const IntegerType *IntegerType::get(LLVMContext &C, unsigned NumBits) {
-  assert(NumBits >= MIN_INT_BITS && "bitwidth too small");
-  assert(NumBits <= MAX_INT_BITS && "bitwidth too large");
+void StructType::setName(StringRef Name) {
+  if (Name == getName()) return;
 
-  // Check for the built-in integer types
-  switch (NumBits) {
-  case  1: return cast<IntegerType>(Type::getInt1Ty(C));
-  case  8: return cast<IntegerType>(Type::getInt8Ty(C));
-  case 16: return cast<IntegerType>(Type::getInt16Ty(C));
-  case 32: return cast<IntegerType>(Type::getInt32Ty(C));
-  case 64: return cast<IntegerType>(Type::getInt64Ty(C));
-  default: 
-    break;
+  // If this struct already had a name, remove its symbol table entry.
+  if (SymbolTableEntry) {
+    getContext().pImpl->NamedStructTypes.erase(getName());
+    SymbolTableEntry = 0;
   }
-
-  LLVMContextImpl *pImpl = C.pImpl;
   
-  IntegerValType IVT(NumBits);
-  IntegerType *ITy = 0;
+  // If this is just removing the name, we're done.
+  if (Name.empty())
+    return;
   
-  // First, see if the type is already in the table, for which
-  // a reader lock suffices.
-  ITy = pImpl->IntegerTypes.get(IVT);
-    
-  if (!ITy) {
-    // Value not found.  Derive a new type!
-    ITy = new IntegerType(C, NumBits);
-    pImpl->IntegerTypes.add(IVT, ITy);
+  // Look up the entry for the name.
+  StringMapEntry<StructType*> *Entry =
+    &getContext().pImpl->NamedStructTypes.GetOrCreateValue(Name);
+  
+  // While we have a name collision, try a random rename.
+  if (Entry->getValue()) {
+    SmallString<64> TempStr(Name);
+    TempStr.push_back('.');
+    raw_svector_ostream TmpStream(TempStr);
+   
+    do {
+      TempStr.resize(Name.size()+1);
+      TmpStream.resync();
+      TmpStream << getContext().pImpl->NamedStructTypesUniqueID++;
+      
+      Entry = &getContext().pImpl->
+                 NamedStructTypes.GetOrCreateValue(TmpStream.str());
+    } while (Entry->getValue());
   }
-#ifdef DEBUG_MERGE_TYPES
-  DEBUG(dbgs() << "Derived new type: " << *ITy << "\n");
-#endif
-  return ITy;
-}
 
-bool IntegerType::isPowerOf2ByteWidth() const {
-  unsigned BitWidth = getBitWidth();
-  return (BitWidth > 7) && isPowerOf2_32(BitWidth);
+  // Okay, we found an entry that isn't used.  It's us!
+  Entry->setValue(this);
+    
+  SymbolTableEntry = Entry;
 }
 
-APInt IntegerType::getMask() const {
-  return APInt::getAllOnesValue(getBitWidth());
-}
+//===----------------------------------------------------------------------===//
+// StructType Helper functions.
 
-FunctionValType FunctionValType::get(const FunctionType *FT) {
-  // Build up a FunctionValType
-  std::vector<const Type *> ParamTypes;
-  ParamTypes.reserve(FT->getNumParams());
-  for (unsigned i = 0, e = FT->getNumParams(); i != e; ++i)
-    ParamTypes.push_back(FT->getParamType(i));
-  return FunctionValType(FT->getReturnType(), ParamTypes, FT->isVarArg());
+// FIXME: Remove this version.
+StructType *StructType::get(LLVMContext &Context, ArrayRef<const Type*>Elements,
+                            bool isPacked) {
+  return get(Context, ArrayRef<Type*>(const_cast<Type**>(Elements.data()),
+             Elements.size()), isPacked);
 }
 
-FunctionType *FunctionType::get(const Type *Result, bool isVarArg) {
-  return get(Result, ArrayRef<const Type *>(), isVarArg);
+StructType *StructType::get(LLVMContext &Context, bool isPacked) {
+  return get(Context, llvm::ArrayRef<const Type*>(), isPacked);
 }
 
-// FunctionType::get - The factory function for the FunctionType class...
-FunctionType *FunctionType::get(const Type *ReturnType,
-                                ArrayRef<const Type*> Params,
-                                bool isVarArg) {
-  FunctionValType VT(ReturnType, Params, isVarArg);
-  FunctionType *FT = 0;
-  
-  LLVMContextImpl *pImpl = ReturnType->getContext().pImpl;
-  
-  FT = pImpl->FunctionTypes.get(VT);
-  
-  if (!FT) {
-    FT = (FunctionType*) operator new(sizeof(FunctionType) +
-                                    sizeof(PATypeHandle)*(Params.size()+1));
-    new (FT) FunctionType(ReturnType, Params, isVarArg);
-    pImpl->FunctionTypes.add(VT, FT);
+StructType *StructType::get(const Type *type, ...) {
+  assert(type != 0 && "Cannot create a struct type with no elements with this");
+  LLVMContext &Ctx = type->getContext();
+  va_list ap;
+  SmallVector<const llvm::Type*, 8> StructFields;
+  va_start(ap, type);
+  while (type) {
+    StructFields.push_back(type);
+    type = va_arg(ap, llvm::Type*);
   }
-
-#ifdef DEBUG_MERGE_TYPES
-  DEBUG(dbgs() << "Derived new type: " << FT << "\n");
-#endif
-  return FT;
+  return llvm::StructType::get(Ctx, StructFields);
 }
 
-ArrayType *ArrayType::get(const Type *ElementType, uint64_t NumElements) {
-  assert(ElementType && "Can't get array of <null> types!");
-  assert(isValidElementType(ElementType) && "Invalid type for array element!");
-
-  ArrayValType AVT(ElementType, NumElements);
-  ArrayType *AT = 0;
-
-  LLVMContextImpl *pImpl = ElementType->getContext().pImpl;
-  
-  AT = pImpl->ArrayTypes.get(AVT);
-      
-  if (!AT) {
-    // Value not found.  Derive a new type!
-    pImpl->ArrayTypes.add(AVT, AT = new ArrayType(ElementType, NumElements));
-  }
-#ifdef DEBUG_MERGE_TYPES
-  DEBUG(dbgs() << "Derived new type: " << *AT << "\n");
-#endif
-  return AT;
+StructType *StructType::createNamed(LLVMContext &Context, StringRef Name,
+                                    ArrayRef<Type*> Elements, bool isPacked) {
+  StructType *ST = createNamed(Context, Name);
+  ST->setBody(Elements, isPacked);
+  return ST;
 }
 
-bool ArrayType::isValidElementType(const Type *ElemTy) {
-  return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() &&
-         !ElemTy->isMetadataTy() && !ElemTy->isFunctionTy();
+StructType *StructType::createNamed(StringRef Name, ArrayRef<Type*> Elements,
+                                    bool isPacked) {
+  assert(!Elements.empty() &&
+         "This method may not be invoked with an empty list");
+  return createNamed(Elements[0]->getContext(), Name, Elements, isPacked);
 }
 
-VectorType *VectorType::get(const Type *ElementType, unsigned NumElements) {
-  assert(ElementType && "Can't get vector of <null> types!");
-
-  VectorValType PVT(ElementType, NumElements);
-  VectorType *PT = 0;
-  
-  LLVMContextImpl *pImpl = ElementType->getContext().pImpl;
-  
-  PT = pImpl->VectorTypes.get(PVT);
-    
-  if (!PT) {
-    pImpl->VectorTypes.add(PVT, PT = new VectorType(ElementType, NumElements));
+StructType *StructType::createNamed(StringRef Name, Type *type, ...) {
+  assert(type != 0 && "Cannot create a struct type with no elements with this");
+  LLVMContext &Ctx = type->getContext();
+  va_list ap;
+  SmallVector<llvm::Type*, 8> StructFields;
+  va_start(ap, type);
+  while (type) {
+    StructFields.push_back(type);
+    type = va_arg(ap, llvm::Type*);
   }
-#ifdef DEBUG_MERGE_TYPES
-  DEBUG(dbgs() << "Derived new type: " << *PT << "\n");
-#endif
-  return PT;
-}
-
-bool VectorType::isValidElementType(const Type *ElemTy) {
-  return ElemTy->isIntegerTy() || ElemTy->isFloatingPointTy() ||
-         ElemTy->isOpaqueTy();
-}
-
-//===----------------------------------------------------------------------===//
-// Struct Type Factory.
-//
-
-StructType *StructType::get(LLVMContext &Context, bool isPacked) {
-  return get(Context, llvm::ArrayRef<const Type*>(), isPacked);
+  return llvm::StructType::createNamed(Ctx, Name, StructFields);
 }
 
-
-StructType *StructType::get(LLVMContext &Context,
-                            ArrayRef<const Type*> ETypes, 
-                            bool isPacked) {
-  StructValType STV(ETypes, isPacked);
-  StructType *ST = 0;
-  
-  LLVMContextImpl *pImpl = Context.pImpl;
+StringRef StructType::getName() const {
+  assert(!isAnonymous() && "Anonymous structs never have names");
+  if (SymbolTableEntry == 0) return StringRef();
   
-  ST = pImpl->StructTypes.get(STV);
-    
-  if (!ST) {
-    // Value not found.  Derive a new type!
-    ST = (StructType*) operator new(sizeof(StructType) +
-                                    sizeof(PATypeHandle) * ETypes.size());
-    new (ST) StructType(Context, ETypes, isPacked);
-    pImpl->StructTypes.add(STV, ST);
-  }
-#ifdef DEBUG_MERGE_TYPES
-  DEBUG(dbgs() << "Derived new type: " << *ST << "\n");
-#endif
-  return ST;
+  return ((StringMapEntry<StructType*> *)SymbolTableEntry)->getKey();
 }
 
-StructType *StructType::get(const Type *type, ...) {
+void StructType::setBody(Type *type, ...) {
   assert(type != 0 && "Cannot create a struct type with no elements with this");
-  LLVMContext &Ctx = type->getContext();
   va_list ap;
-  SmallVector<const llvm::Type*, 8> StructFields;
+  SmallVector<llvm::Type*, 8> StructFields;
   va_start(ap, type);
   while (type) {
     StructFields.push_back(type);
     type = va_arg(ap, llvm::Type*);
   }
-  return llvm::StructType::get(Ctx, StructFields);
+  setBody(StructFields);
 }
 
 bool StructType::isValidElementType(const Type *ElemTy) {
@@ -957,267 +540,157 @@ bool StructType::isValidElementType(const Type *ElemTy) {
          !ElemTy->isMetadataTy() && !ElemTy->isFunctionTy();
 }
 
-
-//===----------------------------------------------------------------------===//
-// Pointer Type Factory...
-//
-
-PointerType *PointerType::get(const Type *ValueType, unsigned AddressSpace) {
-  assert(ValueType && "Can't get a pointer to <null> type!");
-  assert(ValueType->getTypeID() != VoidTyID &&
-         "Pointer to void is not valid, use i8* instead!");
-  assert(isValidElementType(ValueType) && "Invalid type for pointer element!");
-  PointerValType PVT(ValueType, AddressSpace);
-
-  PointerType *PT = 0;
-  
-  LLVMContextImpl *pImpl = ValueType->getContext().pImpl;
+/// isLayoutIdentical - Return true if this is layout identical to the
+/// specified struct.
+bool StructType::isLayoutIdentical(const StructType *Other) const {
+  if (this == Other) return true;
   
-  PT = pImpl->PointerTypes.get(PVT);
+  if (isPacked() != Other->isPacked() ||
+      getNumElements() != Other->getNumElements())
+    return false;
   
-  if (!PT) {
-    // Value not found.  Derive a new type!
-    pImpl->PointerTypes.add(PVT, PT = new PointerType(ValueType, AddressSpace));
-  }
-#ifdef DEBUG_MERGE_TYPES
-  DEBUG(dbgs() << "Derived new type: " << *PT << "\n");
-#endif
-  return PT;
+  return std::equal(element_begin(), element_end(), Other->element_begin());
 }
 
-const PointerType *Type::getPointerTo(unsigned addrs) const {
-  return PointerType::get(this, addrs);
-}
 
-bool PointerType::isValidElementType(const Type *ElemTy) {
-  return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() &&
-         !ElemTy->isMetadataTy();
+/// getTypeByName - Return the type with the specified name, or null if there
+/// is none by that name.
+StructType *Module::getTypeByName(StringRef Name) const {
+  StringMap<StructType*>::iterator I =
+    getContext().pImpl->NamedStructTypes.find(Name);
+  if (I != getContext().pImpl->NamedStructTypes.end())
+    return I->second;
+  return 0;
 }
 
 
 //===----------------------------------------------------------------------===//
-// Opaque Type Factory...
-//
+//                       CompositeType Implementation
+//===----------------------------------------------------------------------===//
 
-OpaqueType *OpaqueType::get(LLVMContext &C) {
-  OpaqueType *OT = new OpaqueType(C);       // All opaque types are distinct.
-  LLVMContextImpl *pImpl = C.pImpl;
-  pImpl->OpaqueTypes.insert(OT);
-  return OT;
+Type *CompositeType::getTypeAtIndex(const Value *V) const {
+  if (const StructType *STy = dyn_cast<StructType>(this)) {
+    unsigned Idx = (unsigned)cast<ConstantInt>(V)->getZExtValue();
+    assert(indexValid(Idx) && "Invalid structure index!");
+    return STy->getElementType(Idx);
+  }
+  
+  return cast<SequentialType>(this)->getElementType();
+}
+Type *CompositeType::getTypeAtIndex(unsigned Idx) const {
+  if (const StructType *STy = dyn_cast<StructType>(this)) {
+    assert(indexValid(Idx) && "Invalid structure index!");
+    return STy->getElementType(Idx);
+  }
+  
+  return cast<SequentialType>(this)->getElementType();
+}
+bool CompositeType::indexValid(const Value *V) const {
+  if (const StructType *STy = dyn_cast<StructType>(this)) {
+    // Structure indexes require 32-bit integer constants.
+    if (V->getType()->isIntegerTy(32))
+      if (const ConstantInt *CU = dyn_cast<ConstantInt>(V))
+        return CU->getZExtValue() < STy->getNumElements();
+    return false;
+  }
+  
+  // Sequential types can be indexed by any integer.
+  return V->getType()->isIntegerTy();
 }
 
+bool CompositeType::indexValid(unsigned Idx) const {
+  if (const StructType *STy = dyn_cast<StructType>(this))
+    return Idx < STy->getNumElements();
+  // Sequential types can be indexed by any integer.
+  return true;
+}
 
 
 //===----------------------------------------------------------------------===//
-//                     Derived Type Refinement Functions
+//                           ArrayType Implementation
 //===----------------------------------------------------------------------===//
 
-// addAbstractTypeUser - Notify an abstract type that there is a new user of
-// it.  This function is called primarily by the PATypeHandle class.
-void Type::addAbstractTypeUser(AbstractTypeUser *U) const {
-  assert(isAbstract() && "addAbstractTypeUser: Current type not abstract!");
-  AbstractTypeUsers.push_back(U);
+ArrayType::ArrayType(Type *ElType, uint64_t NumEl)
+  : SequentialType(ArrayTyID, ElType) {
+  NumElements = NumEl;
 }
 
 
-// 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 Type::removeAbstractTypeUser(AbstractTypeUser *U) const {
-  
-  // Search from back to front because we will notify users from back to
-  // front.  Also, it is likely that there will be a stack like behavior to
-  // users that register and unregister users.
-  //
-  unsigned i;
-  for (i = AbstractTypeUsers.size(); AbstractTypeUsers[i-1] != U; --i)
-    assert(i != 0 && "AbstractTypeUser not in user list!");
-
-  --i;  // Convert to be in range 0 <= i < size()
-  assert(i < AbstractTypeUsers.size() && "Index out of range!");  // Wraparound?
-
-  AbstractTypeUsers.erase(AbstractTypeUsers.begin()+i);
-
-#ifdef DEBUG_MERGE_TYPES
-  DEBUG(dbgs() << "  remAbstractTypeUser[" << (void*)this << ", "
-               << *this << "][" << i << "] User = " << U << "\n");
-#endif
-
-  if (AbstractTypeUsers.empty() && getRefCount() == 0 && isAbstract()) {
-#ifdef DEBUG_MERGE_TYPES
-    DEBUG(dbgs() << "DELETEing unused abstract type: <" << *this
-                 << ">[" << (void*)this << "]" << "\n");
-#endif
+ArrayType *ArrayType::get(const Type *elementType, uint64_t NumElements) {
+  Type *ElementType = const_cast<Type*>(elementType);
+  assert(isValidElementType(ElementType) && "Invalid type for array element!");
+    
+  ArrayType *&Entry = ElementType->getContext().pImpl
+     ->ArrayTypes[std::make_pair(ElementType, NumElements)];
   
-    this->destroy();
-  }
+  if (Entry == 0)
+    Entry = new ArrayType(ElementType, NumElements);
+  return Entry;
 }
 
-// refineAbstractTypeTo - This function is used 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.  Only used for internal
-// callers.
-//
-void DerivedType::refineAbstractTypeTo(const Type *NewType) {
-  assert(isAbstract() && "refineAbstractTypeTo: Current type is not abstract!");
-  assert(this != NewType && "Can't refine to myself!");
-  assert(ForwardType == 0 && "This type has already been refined!");
-
-#ifdef DEBUG_MERGE_TYPES
-  DEBUG(dbgs() << "REFINING abstract type [" << (void*)this << " "
-               << *this << "] to [" << (void*)NewType << " "
-               << *NewType << "]!\n");
-#endif
-
-  // Make sure to put the type to be refined to into a holder so that if IT gets
-  // refined, that we will not continue using a dead reference...
-  //
-  PATypeHolder NewTy(NewType);
-  // Any PATypeHolders referring to this type will now automatically forward to
-  // the type we are resolved to.
-  ForwardType = NewType;
-  if (ForwardType->isAbstract())
-    ForwardType->addRef();
-
-  // Add a self use of the current type so that we don't delete ourself until
-  // after the function exits.
-  //
-  PATypeHolder CurrentTy(this);
-
-  // To make the situation simpler, we ask the subclass to remove this type from
-  // the type map, and to replace any type uses with uses of non-abstract types.
-  // This dramatically limits the amount of recursive type trouble we can find
-  // ourselves in.
-  dropAllTypeUses();
-
-  // Iterate over all of the uses of this type, invoking callback.  Each user
-  // should remove itself from our use list automatically.  We have to check to
-  // make sure that NewTy doesn't _become_ 'this'.  If it does, resolving types
-  // will not cause users to drop off of the use list.  If we resolve to ourself
-  // we succeed!
-  //
-  while (!AbstractTypeUsers.empty() && NewTy != this) {
-    AbstractTypeUser *User = AbstractTypeUsers.back();
-
-    unsigned OldSize = AbstractTypeUsers.size(); (void)OldSize;
-#ifdef DEBUG_MERGE_TYPES
-    DEBUG(dbgs() << " REFINING user " << OldSize-1 << "[" << (void*)User
-                 << "] of abstract type [" << (void*)this << " "
-                 << *this << "] to [" << (void*)NewTy.get() << " "
-                 << *NewTy << "]!\n");
-#endif
-    User->refineAbstractType(this, NewTy);
-
-    assert(AbstractTypeUsers.size() != OldSize &&
-           "AbsTyUser did not remove self from user list!");
-  }
-
-  // If we were successful removing all users from the type, 'this' will be
-  // deleted when the last PATypeHolder is destroyed or updated from this type.
-  // This may occur on exit of this function, as the CurrentTy object is
-  // destroyed.
-}
-
-// notifyUsesThatTypeBecameConcrete - Notify AbstractTypeUsers of this type that
-// the current type has transitioned from being abstract to being concrete.
-//
-void DerivedType::notifyUsesThatTypeBecameConcrete() {
-#ifdef DEBUG_MERGE_TYPES
-  DEBUG(dbgs() << "typeIsREFINED type: " << (void*)this << " " << *this <<"\n");
-#endif
-
-  unsigned OldSize = AbstractTypeUsers.size(); (void)OldSize;
-  while (!AbstractTypeUsers.empty()) {
-    AbstractTypeUser *ATU = AbstractTypeUsers.back();
-    ATU->typeBecameConcrete(this);
-
-    assert(AbstractTypeUsers.size() < OldSize-- &&
-           "AbstractTypeUser did not remove itself from the use list!");
-  }
+bool ArrayType::isValidElementType(const Type *ElemTy) {
+  return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() &&
+         !ElemTy->isMetadataTy() && !ElemTy->isFunctionTy();
 }
 
-// refineAbstractType - Called when a contained type is found to be more
-// concrete - this could potentially change us from an abstract type to a
-// concrete type.
-//
-void FunctionType::refineAbstractType(const DerivedType *OldType,
-                                      const Type *NewType) {
-  LLVMContextImpl *pImpl = OldType->getContext().pImpl;
-  pImpl->FunctionTypes.RefineAbstractType(this, OldType, NewType);
-}
+//===----------------------------------------------------------------------===//
+//                          VectorType Implementation
+//===----------------------------------------------------------------------===//
 
-void FunctionType::typeBecameConcrete(const DerivedType *AbsTy) {
-  LLVMContextImpl *pImpl = AbsTy->getContext().pImpl;
-  pImpl->FunctionTypes.TypeBecameConcrete(this, AbsTy);
+VectorType::VectorType(Type *ElType, unsigned NumEl)
+  : SequentialType(VectorTyID, ElType) {
+  NumElements = NumEl;
 }
 
-
-// refineAbstractType - Called when a contained type is found to be more
-// concrete - this could potentially change us from an abstract type to a
-// concrete type.
-//
-void ArrayType::refineAbstractType(const DerivedType *OldType,
-                                   const Type *NewType) {
-  LLVMContextImpl *pImpl = OldType->getContext().pImpl;
-  pImpl->ArrayTypes.RefineAbstractType(this, OldType, NewType);
+VectorType *VectorType::get(const Type *elementType, unsigned NumElements) {
+  Type *ElementType = const_cast<Type*>(elementType);
+  assert(NumElements > 0 && "#Elements of a VectorType must be greater than 0");
+  assert(isValidElementType(ElementType) &&
+         "Elements of a VectorType must be a primitive type");
+  
+  VectorType *&Entry = ElementType->getContext().pImpl
+    ->VectorTypes[std::make_pair(ElementType, NumElements)];
+  
+  if (Entry == 0)
+    Entry = new VectorType(ElementType, NumElements);
+  return Entry;
 }
 
-void ArrayType::typeBecameConcrete(const DerivedType *AbsTy) {
-  LLVMContextImpl *pImpl = AbsTy->getContext().pImpl;
-  pImpl->ArrayTypes.TypeBecameConcrete(this, AbsTy);
+bool VectorType::isValidElementType(const Type *ElemTy) {
+  return ElemTy->isIntegerTy() || ElemTy->isFloatingPointTy();
 }
 
-// refineAbstractType - Called when a contained type is found to be more
-// concrete - this could potentially change us from an abstract type to a
-// concrete type.
-//
-void VectorType::refineAbstractType(const DerivedType *OldType,
-                                   const Type *NewType) {
-  LLVMContextImpl *pImpl = OldType->getContext().pImpl;
-  pImpl->VectorTypes.RefineAbstractType(this, OldType, NewType);
-}
+//===----------------------------------------------------------------------===//
+//                         PointerType Implementation
+//===----------------------------------------------------------------------===//
 
-void VectorType::typeBecameConcrete(const DerivedType *AbsTy) {
-  LLVMContextImpl *pImpl = AbsTy->getContext().pImpl;
-  pImpl->VectorTypes.TypeBecameConcrete(this, AbsTy);
-}
+PointerType *PointerType::get(const Type *eltTy, unsigned AddressSpace) {
+  Type *EltTy = const_cast<Type*>(eltTy);
+  assert(EltTy && "Can't get a pointer to <null> type!");
+  assert(isValidElementType(EltTy) && "Invalid type for pointer element!");
+  
+  LLVMContextImpl *CImpl = EltTy->getContext().pImpl;
+  
+  // Since AddressSpace #0 is the common case, we special case it.
+  PointerType *&Entry = AddressSpace == 0 ? CImpl->PointerTypes[EltTy]
+     : CImpl->ASPointerTypes[std::make_pair(EltTy, AddressSpace)];
 
-// refineAbstractType - Called when a contained type is found to be more
-// concrete - this could potentially change us from an abstract type to a
-// concrete type.
-//
-void StructType::refineAbstractType(const DerivedType *OldType,
-                                    const Type *NewType) {
-  LLVMContextImpl *pImpl = OldType->getContext().pImpl;
-  pImpl->StructTypes.RefineAbstractType(this, OldType, NewType);
+  if (Entry == 0)
+    Entry = new PointerType(EltTy, AddressSpace);
+  return Entry;
 }
 
-void StructType::typeBecameConcrete(const DerivedType *AbsTy) {
-  LLVMContextImpl *pImpl = AbsTy->getContext().pImpl;
-  pImpl->StructTypes.TypeBecameConcrete(this, AbsTy);
-}
 
-// refineAbstractType - Called when a contained type is found to be more
-// concrete - this could potentially change us from an abstract type to a
-// concrete type.
-//
-void PointerType::refineAbstractType(const DerivedType *OldType,
-                                     const Type *NewType) {
-  LLVMContextImpl *pImpl = OldType->getContext().pImpl;
-  pImpl->PointerTypes.RefineAbstractType(this, OldType, NewType);
+PointerType::PointerType(Type *E, unsigned AddrSpace)
+  : SequentialType(PointerTyID, E) {
+  setSubclassData(AddrSpace);
 }
 
-void PointerType::typeBecameConcrete(const DerivedType *AbsTy) {
-  LLVMContextImpl *pImpl = AbsTy->getContext().pImpl;
-  pImpl->PointerTypes.TypeBecameConcrete(this, AbsTy);
+PointerType *Type::getPointerTo(unsigned addrs) const {
+  return PointerType::get(this, addrs);
 }
 
-namespace llvm {
-raw_ostream &operator<<(raw_ostream &OS, const Type &T) {
-  T.print(OS);
-  return OS;
-}
+bool PointerType::isValidElementType(const Type *ElemTy) {
+  return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() &&
+         !ElemTy->isMetadataTy();
 }
diff --git a/lib/VMCore/TypeSymbolTable.cpp b/lib/VMCore/TypeSymbolTable.cpp
deleted file mode 100644
index 80c6a74..0000000
--- a/lib/VMCore/TypeSymbolTable.cpp
+++ /dev/null
@@ -1,168 +0,0 @@
-//===-- TypeSymbolTable.cpp - Implement the TypeSymbolTable class ---------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file implements the TypeSymbolTable class for the VMCore library.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/TypeSymbolTable.h"
-#include "llvm/DerivedTypes.h"
-#include "llvm/ADT/StringExtras.h"
-#include "llvm/ADT/StringRef.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/ManagedStatic.h"
-#include "llvm/Support/raw_ostream.h"
-#include <algorithm>
-using namespace llvm;
-
-#define DEBUG_SYMBOL_TABLE 0
-#define DEBUG_ABSTYPE 0
-
-TypeSymbolTable::~TypeSymbolTable() {
-  // Drop all abstract type references in the type plane...
-  for (iterator TI = tmap.begin(), TE = tmap.end(); TI != TE; ++TI) {
-    if (TI->second->isAbstract())   // If abstract, drop the reference...
-      cast<DerivedType>(TI->second)->removeAbstractTypeUser(this);
-  }
-}
-
-std::string TypeSymbolTable::getUniqueName(StringRef BaseName) const {
-  std::string TryName = BaseName;
-  
-  const_iterator End = tmap.end();
-
-  // See if the name exists
-  while (tmap.find(TryName) != End)            // Loop until we find a free
-    TryName = BaseName.str() + utostr(++LastUnique); // name in the symbol table
-  return TryName;
-}
-
-// lookup a type by name - returns null on failure
-Type* TypeSymbolTable::lookup(StringRef Name) const {
-  const_iterator TI = tmap.find(Name);
-  Type* result = 0;
-  if (TI != tmap.end())
-    result = const_cast<Type*>(TI->second);
-  return result;
-}
-
-// remove - Remove a type from the symbol table...
-Type* TypeSymbolTable::remove(iterator Entry) {
-  assert(Entry != tmap.end() && "Invalid entry to remove!");
-  const Type* Result = Entry->second;
-
-#if DEBUG_SYMBOL_TABLE
-  dump();
-  dbgs() << " Removing Value: " << *Result << "\n";
-#endif
-
-  tmap.erase(Entry);
-  
-  // If we are removing an abstract type, remove the symbol table from it's use
-  // list...
-  if (Result->isAbstract()) {
-#if DEBUG_ABSTYPE
-    dbgs() << "Removing abstract type from symtab"
-           << *Result << "\n";
-#endif
-    cast<DerivedType>(Result)->removeAbstractTypeUser(this);
-  }
-
-  return const_cast<Type*>(Result);
-}
-
-
-// insert - Insert a type into the symbol table with the specified name...
-void TypeSymbolTable::insert(StringRef Name, const Type* T) {
-  assert(T && "Can't insert null type into symbol table!");
-
-  if (tmap.insert(std::make_pair(Name, T)).second) {
-    // Type inserted fine with no conflict.
-    
-#if DEBUG_SYMBOL_TABLE
-    dump();
-    dbgs() << " Inserted type: " << Name << ": " << *T << "\n";
-#endif
-  } else {
-    // If there is a name conflict...
-    
-    // Check to see if there is a naming conflict.  If so, rename this type!
-    std::string UniqueName = Name;
-    if (lookup(Name))
-      UniqueName = getUniqueName(Name);
-    
-#if DEBUG_SYMBOL_TABLE
-    dump();
-    dbgs() << " Inserting type: " << UniqueName << ": "
-           << *T << "\n";
-#endif
-
-    // Insert the tmap entry
-    tmap.insert(make_pair(UniqueName, T));
-  }
-  
-  // If we are adding an abstract type, add the symbol table to it's use list.
-  if (T->isAbstract()) {
-    cast<DerivedType>(T)->addAbstractTypeUser(this);
-#if DEBUG_ABSTYPE
-    dbgs() << "Added abstract type to ST: " << *T << "\n";
-#endif
-  }
-}
-
-// This function is called when one of the types in the type plane are refined
-void TypeSymbolTable::refineAbstractType(const DerivedType *OldType,
-                                         const Type *NewType) {
-  // Loop over all of the types in the symbol table, replacing any references
-  // to OldType with references to NewType.  Note that there may be multiple
-  // occurrences, and although we only need to remove one at a time, it's
-  // faster to remove them all in one pass.
-  //
-  for (iterator I = begin(), E = end(); I != E; ++I) {
-    // FIXME when Types aren't const.
-    if (I->second == const_cast<DerivedType *>(OldType)) {
-#if DEBUG_ABSTYPE
-      dbgs() << "Removing type " << *OldType << "\n";
-#endif
-      OldType->removeAbstractTypeUser(this);
-
-      // TODO FIXME when types aren't const
-      I->second = const_cast<Type *>(NewType);
-      if (NewType->isAbstract()) {
-#if DEBUG_ABSTYPE
-        dbgs() << "Added type " << *NewType << "\n";
-#endif
-        cast<DerivedType>(NewType)->addAbstractTypeUser(this);
-      }
-    }
-  }
-}
-
-
-// Handle situation where type becomes Concreate from Abstract
-void TypeSymbolTable::typeBecameConcrete(const DerivedType *AbsTy) {
-  // Loop over all of the types in the symbol table, dropping any abstract
-  // type user entries for AbsTy which occur because there are names for the
-  // type.
-  for (iterator TI = begin(), TE = end(); TI != TE; ++TI)
-    if (TI->second == const_cast<Type*>(static_cast<const Type*>(AbsTy)))
-      AbsTy->removeAbstractTypeUser(this);
-}
-
-static void DumpTypes(const std::pair<const std::string, const Type*>& T ) {
-  dbgs() << "  '" << T.first << "' = ";
-  T.second->dump();
-  dbgs() << "\n";
-}
-
-void TypeSymbolTable::dump() const {
-  dbgs() << "TypeSymbolPlane: ";
-  for_each(tmap.begin(), tmap.end(), DumpTypes);
-}
-
diff --git a/lib/VMCore/TypesContext.h b/lib/VMCore/TypesContext.h
deleted file mode 100644
index ad09478..0000000
--- a/lib/VMCore/TypesContext.h
+++ /dev/null
@@ -1,426 +0,0 @@
-//===-- TypesContext.h - Types-related Context Internals ------------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-//  This file defines various helper methods and classes used by
-// LLVMContextImpl for creating and managing types.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_TYPESCONTEXT_H
-#define LLVM_TYPESCONTEXT_H
-
-#include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/STLExtras.h"
-#include <map>
-
-
-//===----------------------------------------------------------------------===//
-//                       Derived Type Factory Functions
-//===----------------------------------------------------------------------===//
-namespace llvm {
-
-/// getSubElementHash - Generate a hash value for all of the SubType's of this
-/// type.  The hash value is guaranteed to be zero if any of the subtypes are 
-/// an opaque type.  Otherwise we try to mix them in as well as possible, but do
-/// not look at the subtype's subtype's.
-static unsigned getSubElementHash(const Type *Ty) {
-  unsigned HashVal = 0;
-  for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
-       I != E; ++I) {
-    HashVal *= 32;
-    const Type *SubTy = I->get();
-    HashVal += SubTy->getTypeID();
-    switch (SubTy->getTypeID()) {
-    default: break;
-    case Type::OpaqueTyID: return 0;    // Opaque -> hash = 0 no matter what.
-    case Type::IntegerTyID:
-      HashVal ^= (cast<IntegerType>(SubTy)->getBitWidth() << 3);
-      break;
-    case Type::FunctionTyID:
-      HashVal ^= cast<FunctionType>(SubTy)->getNumParams()*2 + 
-                 cast<FunctionType>(SubTy)->isVarArg();
-      break;
-    case Type::ArrayTyID:
-      HashVal ^= cast<ArrayType>(SubTy)->getNumElements();
-      break;
-    case Type::VectorTyID:
-      HashVal ^= cast<VectorType>(SubTy)->getNumElements();
-      break;
-    case Type::StructTyID:
-      HashVal ^= cast<StructType>(SubTy)->getNumElements();
-      break;
-    case Type::PointerTyID:
-      HashVal ^= cast<PointerType>(SubTy)->getAddressSpace();
-      break;
-    }
-  }
-  return HashVal ? HashVal : 1;  // Do not return zero unless opaque subty.
-}
-
-//===----------------------------------------------------------------------===//
-// Integer Type Factory...
-//
-class IntegerValType {
-  uint32_t bits;
-public:
-  IntegerValType(uint32_t numbits) : bits(numbits) {}
-
-  static IntegerValType get(const IntegerType *Ty) {
-    return IntegerValType(Ty->getBitWidth());
-  }
-
-  static unsigned hashTypeStructure(const IntegerType *Ty) {
-    return (unsigned)Ty->getBitWidth();
-  }
-
-  inline bool operator<(const IntegerValType &IVT) const {
-    return bits < IVT.bits;
-  }
-};
-
-// PointerValType - Define a class to hold the key that goes into the TypeMap
-//
-class PointerValType {
-  const Type *ValTy;
-  unsigned AddressSpace;
-public:
-  PointerValType(const Type *val, unsigned as) : ValTy(val), AddressSpace(as) {}
-
-  static PointerValType get(const PointerType *PT) {
-    return PointerValType(PT->getElementType(), PT->getAddressSpace());
-  }
-
-  static unsigned hashTypeStructure(const PointerType *PT) {
-    return getSubElementHash(PT);
-  }
-
-  bool operator<(const PointerValType &MTV) const {
-    if (AddressSpace < MTV.AddressSpace) return true;
-    return AddressSpace == MTV.AddressSpace && ValTy < MTV.ValTy;
-  }
-};
-
-//===----------------------------------------------------------------------===//
-// Array Type Factory...
-//
-class ArrayValType {
-  const Type *ValTy;
-  uint64_t Size;
-public:
-  ArrayValType(const Type *val, uint64_t sz) : ValTy(val), Size(sz) {}
-
-  static ArrayValType get(const ArrayType *AT) {
-    return ArrayValType(AT->getElementType(), AT->getNumElements());
-  }
-
-  static unsigned hashTypeStructure(const ArrayType *AT) {
-    return (unsigned)AT->getNumElements();
-  }
-
-  inline bool operator<(const ArrayValType &MTV) const {
-    if (Size < MTV.Size) return true;
-    return Size == MTV.Size && ValTy < MTV.ValTy;
-  }
-};
-
-//===----------------------------------------------------------------------===//
-// Vector Type Factory...
-//
-class VectorValType {
-  const Type *ValTy;
-  unsigned Size;
-public:
-  VectorValType(const Type *val, int sz) : ValTy(val), Size(sz) {}
-
-  static VectorValType get(const VectorType *PT) {
-    return VectorValType(PT->getElementType(), PT->getNumElements());
-  }
-
-  static unsigned hashTypeStructure(const VectorType *PT) {
-    return PT->getNumElements();
-  }
-
-  inline bool operator<(const VectorValType &MTV) const {
-    if (Size < MTV.Size) return true;
-    return Size == MTV.Size && ValTy < MTV.ValTy;
-  }
-};
-
-// StructValType - Define a class to hold the key that goes into the TypeMap
-//
-class StructValType {
-  std::vector<const Type*> ElTypes;
-  bool packed;
-public:
-  StructValType(ArrayRef<const Type*> args, bool isPacked)
-    : ElTypes(args.vec()), packed(isPacked) {}
-
-  static StructValType get(const StructType *ST) {
-    std::vector<const Type *> ElTypes;
-    ElTypes.reserve(ST->getNumElements());
-    for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i)
-      ElTypes.push_back(ST->getElementType(i));
-
-    return StructValType(ElTypes, ST->isPacked());
-  }
-
-  static unsigned hashTypeStructure(const StructType *ST) {
-    return ST->getNumElements();
-  }
-
-  inline bool operator<(const StructValType &STV) const {
-    if (ElTypes < STV.ElTypes) return true;
-    else if (ElTypes > STV.ElTypes) return false;
-    else return (int)packed < (int)STV.packed;
-  }
-};
-
-// FunctionValType - Define a class to hold the key that goes into the TypeMap
-//
-class FunctionValType {
-  const Type *RetTy;
-  std::vector<const Type*> ArgTypes;
-  bool isVarArg;
-public:
-  FunctionValType(const Type *ret, ArrayRef<const Type*> args, bool isVA)
-    : RetTy(ret), ArgTypes(args.vec()), isVarArg(isVA) {}
-
-  static FunctionValType get(const FunctionType *FT);
-
-  static unsigned hashTypeStructure(const FunctionType *FT) {
-    unsigned Result = FT->getNumParams()*2 + FT->isVarArg();
-    return Result;
-  }
-
-  inline bool operator<(const FunctionValType &MTV) const {
-    if (RetTy < MTV.RetTy) return true;
-    if (RetTy > MTV.RetTy) return false;
-    if (isVarArg < MTV.isVarArg) return true;
-    if (isVarArg > MTV.isVarArg) return false;
-    if (ArgTypes < MTV.ArgTypes) return true;
-    if (ArgTypes > MTV.ArgTypes) return false;
-    return false;
-  }
-};
-
-class TypeMapBase {
-protected:
-  /// TypesByHash - Keep track of types by their structure hash value.  Note
-  /// that we only keep track of types that have cycles through themselves in
-  /// this map.
-  ///
-  std::multimap<unsigned, PATypeHolder> TypesByHash;
-
-  ~TypeMapBase() {
-    // PATypeHolder won't destroy non-abstract types.
-    // We can't destroy them by simply iterating, because
-    // they may contain references to each-other.
-    for (std::multimap<unsigned, PATypeHolder>::iterator I
-         = TypesByHash.begin(), E = TypesByHash.end(); I != E; ++I) {
-      Type *Ty = const_cast<Type*>(I->second.Ty);
-      I->second.destroy();
-      // We can't invoke destroy or delete, because the type may
-      // contain references to already freed types.
-      // So we have to destruct the object the ugly way.
-      if (Ty) {
-        Ty->AbstractTypeUsers.clear();
-        static_cast<const Type*>(Ty)->Type::~Type();
-        operator delete(Ty);
-      }
-    }
-  }
-
-public:
-  void RemoveFromTypesByHash(unsigned Hash, const Type *Ty) {
-    std::multimap<unsigned, PATypeHolder>::iterator I =
-      TypesByHash.lower_bound(Hash);
-    for (; I != TypesByHash.end() && I->first == Hash; ++I) {
-      if (I->second == Ty) {
-        TypesByHash.erase(I);
-        return;
-      }
-    }
-
-    // This must be do to an opaque type that was resolved.  Switch down to hash
-    // code of zero.
-    assert(Hash && "Didn't find type entry!");
-    RemoveFromTypesByHash(0, Ty);
-  }
-
-  /// TypeBecameConcrete - When Ty gets a notification that TheType just became
-  /// concrete, drop uses and make Ty non-abstract if we should.
-  void TypeBecameConcrete(DerivedType *Ty, const DerivedType *TheType) {
-    // If the element just became concrete, remove 'ty' from the abstract
-    // type user list for the type.  Do this for as many times as Ty uses
-    // OldType.
-    for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
-         I != E; ++I)
-      if (I->get() == TheType)
-        TheType->removeAbstractTypeUser(Ty);
-
-    // If the type is currently thought to be abstract, rescan all of our
-    // subtypes to see if the type has just become concrete!  Note that this
-    // may send out notifications to AbstractTypeUsers that types become
-    // concrete.
-    if (Ty->isAbstract())
-      Ty->PromoteAbstractToConcrete();
-  }
-};
-
-// TypeMap - Make sure that only one instance of a particular type may be
-// created on any given run of the compiler... note that this involves updating
-// our map if an abstract type gets refined somehow.
-//
-template<class ValType, class TypeClass>
-class TypeMap : public TypeMapBase {
-  std::map<ValType, PATypeHolder> Map;
-public:
-  typedef typename std::map<ValType, PATypeHolder>::iterator iterator;
-
-  inline TypeClass *get(const ValType &V) {
-    iterator I = Map.find(V);
-    return I != Map.end() ? cast<TypeClass>((Type*)I->second.get()) : 0;
-  }
-
-  inline void add(const ValType &V, TypeClass *Ty) {
-    Map.insert(std::make_pair(V, Ty));
-
-    // If this type has a cycle, remember it.
-    TypesByHash.insert(std::make_pair(ValType::hashTypeStructure(Ty), Ty));
-    print("add");
-  }
-  
-  /// RefineAbstractType - This method is called after we have merged a type
-  /// with another one.  We must now either merge the type away with
-  /// some other type or reinstall it in the map with it's new configuration.
-  void RefineAbstractType(TypeClass *Ty, const DerivedType *OldType,
-                        const Type *NewType) {
-#ifdef DEBUG_MERGE_TYPES
-    DEBUG(dbgs() << "RefineAbstractType(" << (void*)OldType << "[" << *OldType
-                 << "], " << (void*)NewType << " [" << *NewType << "])\n");
-#endif
-    
-    // Otherwise, we are changing one subelement type into another.  Clearly the
-    // OldType must have been abstract, making us abstract.
-    assert(Ty->isAbstract() && "Refining a non-abstract type!");
-    assert(OldType != NewType);
-
-    // Make a temporary type holder for the type so that it doesn't disappear on
-    // us when we erase the entry from the map.
-    PATypeHolder TyHolder = Ty;
-
-    // The old record is now out-of-date, because one of the children has been
-    // updated.  Remove the obsolete entry from the map.
-    unsigned NumErased = Map.erase(ValType::get(Ty));
-    assert(NumErased && "Element not found!"); (void)NumErased;
-
-    // Remember the structural hash for the type before we start hacking on it,
-    // in case we need it later.
-    unsigned OldTypeHash = ValType::hashTypeStructure(Ty);
-
-    // Find the type element we are refining... and change it now!
-    for (unsigned i = 0, e = Ty->getNumContainedTypes(); i != e; ++i)
-      if (Ty->ContainedTys[i] == OldType)
-        Ty->ContainedTys[i] = NewType;
-    unsigned NewTypeHash = ValType::hashTypeStructure(Ty);
-    
-    // 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.
-    if (!TypeHasCycleThroughItself(Ty)) {
-      typename std::map<ValType, PATypeHolder>::iterator I;
-      bool Inserted;
-
-      tie(I, Inserted) = Map.insert(std::make_pair(ValType::get(Ty), Ty));
-      if (!Inserted) {
-        // Refined to a different type altogether?
-        RemoveFromTypesByHash(OldTypeHash, Ty);
-
-        // We already have this type in the table.  Get rid of the newly refined
-        // type.
-        TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get());
-        Ty->refineAbstractTypeTo(NewTy);
-        return;
-      }
-    } else {
-      // 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.
-      //
-      std::multimap<unsigned, PATypeHolder>::iterator I, E, Entry;
-      tie(I, E) = TypesByHash.equal_range(NewTypeHash);
-      Entry = E;
-      for (; I != E; ++I) {
-        if (I->second == Ty) {
-          // Remember the position of the old type if we see it in our scan.
-          Entry = I;
-          continue;
-        }
-        
-        if (!TypesEqual(Ty, I->second))
-          continue;
-        
-        TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get());
-
-        // Remove the old entry form TypesByHash.  If the hash values differ
-        // now, remove it from the old place.  Otherwise, continue scanning
-        // within this hashcode to reduce work.
-        if (NewTypeHash != OldTypeHash) {
-          RemoveFromTypesByHash(OldTypeHash, Ty);
-        } else {
-          if (Entry == E) {
-            // Find the location of Ty in the TypesByHash structure if we
-            // haven't seen it already.
-            while (I->second != Ty) {
-              ++I;
-              assert(I != E && "Structure doesn't contain type??");
-            }
-            Entry = I;
-          }
-          TypesByHash.erase(Entry);
-        }
-        Ty->refineAbstractTypeTo(NewTy);
-        return;
-      }
-
-      // If there is no existing type of the same structure, we reinsert an
-      // updated record into the map.
-      Map.insert(std::make_pair(ValType::get(Ty), Ty));
-    }
-
-    // If the hash codes differ, update TypesByHash
-    if (NewTypeHash != OldTypeHash) {
-      RemoveFromTypesByHash(OldTypeHash, Ty);
-      TypesByHash.insert(std::make_pair(NewTypeHash, Ty));
-    }
-    
-    // If the type is currently thought to be abstract, rescan all of our
-    // subtypes to see if the type has just become concrete!  Note that this
-    // may send out notifications to AbstractTypeUsers that types become
-    // concrete.
-    if (Ty->isAbstract())
-      Ty->PromoteAbstractToConcrete();
-  }
-
-  void print(const char *Arg) const {
-#ifdef DEBUG_MERGE_TYPES
-    DEBUG(dbgs() << "TypeMap<>::" << Arg << " table contents:\n");
-    unsigned i = 0;
-    for (typename std::map<ValType, PATypeHolder>::const_iterator I
-           = Map.begin(), E = Map.end(); I != E; ++I)
-      DEBUG(dbgs() << " " << (++i) << ". " << (void*)I->second.get() << " "
-                   << *I->second.get() << "\n");
-#endif
-  }
-
-  void dump() const { print("dump output"); }
-};
-}
-
-#endif
diff --git a/lib/VMCore/Value.cpp b/lib/VMCore/Value.cpp
index a03cddc..c7a4212 100644
--- a/lib/VMCore/Value.cpp
+++ b/lib/VMCore/Value.cpp
@@ -35,22 +35,21 @@ using namespace llvm;
 //                                Value Class
 //===----------------------------------------------------------------------===//
 
-static inline const Type *checkType(const Type *Ty) {
+static inline Type *checkType(const Type *Ty) {
   assert(Ty && "Value defined with a null type: Error!");
-  return Ty;
+  return const_cast<Type*>(Ty);
 }
 
 Value::Value(const Type *ty, unsigned scid)
   : SubclassID(scid), HasValueHandle(0),
-    SubclassOptionalData(0), SubclassData(0), VTy(checkType(ty)),
+    SubclassOptionalData(0), SubclassData(0), VTy((Type*)checkType(ty)),
     UseList(0), Name(0) {
+  // FIXME: Why isn't this in the subclass gunk??
   if (isa<CallInst>(this) || isa<InvokeInst>(this))
-    assert((VTy->isFirstClassType() || VTy->isVoidTy() ||
-            ty->isOpaqueTy() || VTy->isStructTy()) &&
-           "invalid CallInst  type!");
+    assert((VTy->isFirstClassType() || VTy->isVoidTy() || VTy->isStructTy()) &&
+           "invalid CallInst type!");
   else if (!isa<Constant>(this) && !isa<BasicBlock>(this))
-    assert((VTy->isFirstClassType() || VTy->isVoidTy() ||
-            ty->isOpaqueTy()) &&
+    assert((VTy->isFirstClassType() || VTy->isVoidTy()) &&
            "Cannot create non-first-class values except for constants!");
 }
 
diff --git a/lib/VMCore/Verifier.cpp b/lib/VMCore/Verifier.cpp
index 18de671..c35d5ad 100644
--- a/lib/VMCore/Verifier.cpp
+++ b/lib/VMCore/Verifier.cpp
@@ -49,7 +49,6 @@
 #include "llvm/Module.h"
 #include "llvm/Pass.h"
 #include "llvm/PassManager.h"
-#include "llvm/TypeSymbolTable.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Assembly/Writer.h"
 #include "llvm/CodeGen/ValueTypes.h"
@@ -109,54 +108,6 @@ INITIALIZE_PASS(PreVerifier, "preverify", "Preliminary module verification",
 static char &PreVerifyID = PreVerifier::ID;
 
 namespace {
-  class TypeSet : public AbstractTypeUser {
-  public:
-    TypeSet() {}
-
-    /// Insert a type into the set of types.
-    bool insert(const Type *Ty) {
-      if (!Types.insert(Ty))
-        return false;
-      if (Ty->isAbstract())
-        Ty->addAbstractTypeUser(this);
-      return true;
-    }
-
-    // Remove ourselves as abstract type listeners for any types that remain
-    // abstract when the TypeSet is destroyed.
-    ~TypeSet() {
-      for (SmallSetVector<const Type *, 16>::iterator I = Types.begin(),
-             E = Types.end(); I != E; ++I) {
-        const Type *Ty = *I;
-        if (Ty->isAbstract())
-          Ty->removeAbstractTypeUser(this);
-      }
-    }
-
-    // Abstract type user interface.
-
-    /// Remove types from the set when refined. Do not insert the type it was
-    /// refined to because that type hasn't been verified yet.
-    void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
-      Types.remove(OldTy);
-      OldTy->removeAbstractTypeUser(this);
-    }
-
-    /// Stop listening for changes to a type which is no longer abstract.
-    void typeBecameConcrete(const DerivedType *AbsTy) {
-      AbsTy->removeAbstractTypeUser(this);
-    }
-
-    void dump() const {}
-
-  private:
-    SmallSetVector<const Type *, 16> Types;
-
-    // Disallow copying.
-    TypeSet(const TypeSet &);
-    TypeSet &operator=(const TypeSet &);
-  };
-
   struct Verifier : public FunctionPass, public InstVisitor<Verifier> {
     static char ID; // Pass ID, replacement for typeid
     bool Broken;          // Is this module found to be broken?
@@ -176,9 +127,6 @@ namespace {
     /// an instruction in the same block.
     SmallPtrSet<Instruction*, 16> InstsInThisBlock;
 
-    /// Types - keep track of the types that have been checked already.
-    TypeSet Types;
-
     /// MDNodes - keep track of the metadata nodes that have been checked
     /// already.
     SmallPtrSet<MDNode *, 32> MDNodes;
@@ -199,7 +147,6 @@ namespace {
     bool doInitialization(Module &M) {
       Mod = &M;
       Context = &M.getContext();
-      verifyTypeSymbolTable(M.getTypeSymbolTable());
 
       // If this is a real pass, in a pass manager, we must abort before
       // returning back to the pass manager, or else the pass manager may try to
@@ -285,7 +232,6 @@ namespace {
 
 
     // Verification methods...
-    void verifyTypeSymbolTable(TypeSymbolTable &ST);
     void visitGlobalValue(GlobalValue &GV);
     void visitGlobalVariable(GlobalVariable &GV);
     void visitGlobalAlias(GlobalAlias &GA);
@@ -345,7 +291,6 @@ namespace {
                               bool isReturnValue, const Value *V);
     void VerifyFunctionAttrs(const FunctionType *FT, const AttrListPtr &Attrs,
                              const Value *V);
-    void VerifyType(const Type *Ty);
 
     void WriteValue(const Value *V) {
       if (!V) return;
@@ -359,8 +304,7 @@ namespace {
 
     void WriteType(const Type *T) {
       if (!T) return;
-      MessagesStr << ' ';
-      WriteTypeSymbolic(MessagesStr, T, Mod);
+      MessagesStr << ' ' << *T;
     }
 
 
@@ -568,11 +512,6 @@ void Verifier::visitMDNode(MDNode &MD, Function *F) {
   }
 }
 
-void Verifier::verifyTypeSymbolTable(TypeSymbolTable &ST) {
-  for (TypeSymbolTable::iterator I = ST.begin(), E = ST.end(); I != E; ++I)
-    VerifyType(I->second);
-}
-
 // VerifyParameterAttrs - Check the given attributes for an argument or return
 // value of the specified type.  The value V is printed in error messages.
 void Verifier::VerifyParameterAttrs(Attributes Attrs, const Type *Ty,
@@ -1192,11 +1131,11 @@ void Verifier::VerifyCallSite(CallSite CS) {
     }
 
   // Verify that there's no metadata unless it's a direct call to an intrinsic.
-  if (!CS.getCalledFunction() ||
+  if (CS.getCalledFunction() == 0 ||
       !CS.getCalledFunction()->getName().startswith("llvm.")) {
     for (FunctionType::param_iterator PI = FTy->param_begin(),
            PE = FTy->param_end(); PI != PE; ++PI)
-      Assert1(!PI->get()->isMetadataTy(),
+      Assert1(!(*PI)->isMetadataTy(),
               "Function has metadata parameter but isn't an intrinsic", I);
   }
 
@@ -1542,69 +1481,6 @@ void Verifier::visitInstruction(Instruction &I) {
     }
   }
   InstsInThisBlock.insert(&I);
-
-  VerifyType(I.getType());
-}
-
-/// VerifyType - Verify that a type is well formed.
-///
-void Verifier::VerifyType(const Type *Ty) {
-  if (!Types.insert(Ty)) return;
-
-  Assert1(Context == &Ty->getContext(),
-          "Type context does not match Module context!", Ty);
-
-  switch (Ty->getTypeID()) {
-  case Type::FunctionTyID: {
-    const FunctionType *FTy = cast<FunctionType>(Ty);
-
-    const Type *RetTy = FTy->getReturnType();
-    Assert2(FunctionType::isValidReturnType(RetTy),
-            "Function type with invalid return type", RetTy, FTy);
-    VerifyType(RetTy);
-
-    for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) {
-      const Type *ElTy = FTy->getParamType(i);
-      Assert2(FunctionType::isValidArgumentType(ElTy),
-              "Function type with invalid parameter type", ElTy, FTy);
-      VerifyType(ElTy);
-    }
-    break;
-  }
-  case Type::StructTyID: {
-    const StructType *STy = cast<StructType>(Ty);
-    for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
-      const Type *ElTy = STy->getElementType(i);
-      Assert2(StructType::isValidElementType(ElTy),
-              "Structure type with invalid element type", ElTy, STy);
-      VerifyType(ElTy);
-    }
-    break;
-  }
-  case Type::ArrayTyID: {
-    const ArrayType *ATy = cast<ArrayType>(Ty);
-    Assert1(ArrayType::isValidElementType(ATy->getElementType()),
-            "Array type with invalid element type", ATy);
-    VerifyType(ATy->getElementType());
-    break;
-  }
-  case Type::PointerTyID: {
-    const PointerType *PTy = cast<PointerType>(Ty);
-    Assert1(PointerType::isValidElementType(PTy->getElementType()),
-            "Pointer type with invalid element type", PTy);
-    VerifyType(PTy->getElementType());
-    break;
-  }
-  case Type::VectorTyID: {
-    const VectorType *VTy = cast<VectorType>(Ty);
-    Assert1(VectorType::isValidElementType(VTy->getElementType()),
-            "Vector type with invalid element type", VTy);
-    VerifyType(VTy->getElementType());
-    break;
-  }
-  default:
-    break;
-  }
 }
 
 // Flags used by TableGen to mark intrinsic parameters with the