* Add support for forward referencing types

* Add support for upreferences for recursive types
* Remove support for ConstantPool.h
* Add support for globally unique Constants
* Add support for the opaque type


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

1 files changed, 501 insertions, 369 deletions

diff --git a/lib/AsmParser/llvmAsmParser.y b/lib/AsmParser/llvmAsmParser.y
index 181ca19e14..9971050f3a 100644
--- a/lib/AsmParser/llvmAsmParser.y
+++ b/lib/AsmParser/llvmAsmParser.y
@@ -19,12 +19,13 @@
 #include "llvm/Type.h"
 #include "llvm/DerivedTypes.h"
 #include "llvm/Assembly/Parser.h"
-#include "llvm/ConstantPool.h"
 #include "llvm/iTerminators.h"
 #include "llvm/iMemory.h"
+#include "llvm/CFG.h"         // TODO: Change this when we have a DF.h
+#include "llvm/Support/STLExtras.h"
 #include <list>
 #include <utility>            // Get definition of pair class
-#include <algorithm>          // Get definition of find_if
+#include <algorithm>
 #include <stdio.h>            // This embarasment is due to our flex lexer...
 
 int yyerror(const char *ErrorMsg); // Forward declarations to prevent "implicit 
@@ -34,23 +35,38 @@ int yyparse();
 static Module *ParserResult;
 string CurFilename;
 
+// DEBUG_UPREFS - Define this symbol if you want to enable debugging output
+// relating to upreferences in the input stream.
+//
+//#define DEBUG_UPREFS 1
+#ifdef DEBUG_UPREFS
+#define UR_OUT(X) cerr << X
+#else
+#define UR_OUT(X)
+#endif
+
 // This contains info used when building the body of a method.  It is destroyed
 // when the method is completed.
 //
 typedef vector<Value *> ValueList;           // Numbered defs
 static void ResolveDefinitions(vector<ValueList> &LateResolvers);
+static void ResolveTypes      (vector<PATypeHolder<Type> > &LateResolveTypes);
 
 static struct PerModuleInfo {
   Module *CurrentModule;
-  vector<ValueList> Values;     // Module level numbered definitions
-  vector<ValueList> LateResolveValues;
+  vector<ValueList>    Values;     // Module level numbered definitions
+  vector<ValueList>    LateResolveValues;
+  vector<PATypeHolder<Type> > Types, LateResolveTypes;
 
   void ModuleDone() {
-    // If we could not resolve some blocks at parsing time (forward branches)
-    // resolve the branches now...
+    // If we could not resolve some methods at method compilation time (calls to
+    // methods before they are defined), resolve them now...  Types are resolved
+    // when the constant pool has been completely parsed.
+    //
     ResolveDefinitions(LateResolveValues);
 
     Values.clear();         // Clear out method local definitions
+    Types.clear();
     CurrentModule = 0;
   }
 } CurModule;
@@ -60,6 +76,7 @@ static struct PerMethodInfo {
 
   vector<ValueList> Values;      // Keep track of numbered definitions
   vector<ValueList> LateResolveValues;
+  vector<PATypeHolder<Type> > Types, LateResolveTypes;
   bool isDeclare;                // Is this method a forward declararation?
 
   inline PerMethodInfo() {
@@ -79,6 +96,7 @@ static struct PerMethodInfo {
     ResolveDefinitions(LateResolveValues);
 
     Values.clear();         // Clear out method local definitions
+    Types.clear();
     CurrentMethod = 0;
     isDeclare = false;
   }
@@ -99,11 +117,71 @@ static void InsertValue(Value *D, vector<ValueList> &ValueTab = CurMeth.Values){
   }
 }
 
-static Value *getVal(const Type *Type, const ValID &D, 
+// TODO: FIXME when Type are not const
+static void InsertType(const Type *Ty, vector<PATypeHolder<Type> > &Types) {
+  Types.push_back(Ty);
+}
+
+static const Type *getTypeVal(const ValID &D, bool DoNotImprovise = false) {
+  switch (D.Type) {
+  case 0: {                 // Is it a numbered definition?
+    unsigned Num = (unsigned)D.Num;
+
+    // Module constants occupy the lowest numbered slots...
+    if (Num < CurModule.Types.size()) 
+      return CurModule.Types[Num];
+
+    Num -= CurModule.Types.size();
+
+    // Check that the number is within bounds...
+    if (Num <= CurMeth.Types.size())
+      return CurMeth.Types[Num];
+  }
+  case 1: {                // Is it a named definition?
+    string Name(D.Name);
+    SymbolTable *SymTab = 0;
+    if (CurMeth.CurrentMethod) 
+      SymTab = CurMeth.CurrentMethod->getSymbolTable();
+    Value *N = SymTab ? SymTab->lookup(Type::TypeTy, Name) : 0;
+
+    if (N == 0) {
+      // Symbol table doesn't automatically chain yet... because the method
+      // hasn't been added to the module...
+      //
+      SymTab = CurModule.CurrentModule->getSymbolTable();
+      if (SymTab)
+        N = SymTab->lookup(Type::TypeTy, Name);
+      if (N == 0) break;
+    }
+
+    D.destroy();  // Free old strdup'd memory...
+    return N->castTypeAsserting();
+  }
+  default:
+    ThrowException("Invalid symbol type reference!");
+  }
+
+  // If we reached here, we referenced either a symbol that we don't know about
+  // or an id number that hasn't been read yet.  We may be referencing something
+  // forward, so just create an entry to be resolved later and get to it...
+  //
+  if (DoNotImprovise) return 0;  // Do we just want a null to be returned?
+
+  vector<PATypeHolder<Type> > *LateResolver = CurMeth.CurrentMethod ? 
+    &CurMeth.LateResolveTypes : &CurModule.LateResolveTypes;
+
+  Type *Typ = new TypePlaceHolder(Type::TypeTy, D);
+  InsertType(Typ, *LateResolver);
+  return Typ;
+}
+
+static Value *getVal(const Type *Ty, const ValID &D, 
                      bool DoNotImprovise = false) {
+  assert(Ty != Type::TypeTy && "Should use getTypeVal for types!");
+
   switch (D.Type) {
   case 0: {                 // Is it a numbered definition?
-    unsigned type = Type->getUniqueID();
+    unsigned type = Ty->getUniqueID();
     unsigned Num = (unsigned)D.Num;
 
     // Module constants occupy the lowest numbered slots...
@@ -129,12 +207,15 @@ static Value *getVal(const Type *Type, const ValID &D,
     SymbolTable *SymTab = 0;
     if (CurMeth.CurrentMethod) 
       SymTab = CurMeth.CurrentMethod->getSymbolTable();
-    Value *N = SymTab ? SymTab->lookup(Type, Name) : 0;
+    Value *N = SymTab ? SymTab->lookup(Ty, Name) : 0;
 
     if (N == 0) {
+      // Symbol table doesn't automatically chain yet... because the method
+      // hasn't been added to the module...
+      //
       SymTab = CurModule.CurrentModule->getSymbolTable();
       if (SymTab)
-        N = SymTab->lookup(Type, Name);
+        N = SymTab->lookup(Ty, Name);
       if (N == 0) break;
     }
 
@@ -148,29 +229,29 @@ static Value *getVal(const Type *Type, const ValID &D,
   case 5:{                // Is it a floating point const pool reference?
     ConstPoolVal *CPV = 0;
 
-    // Check to make sure that "Type" is an integral type, and that our 
+    // Check to make sure that "Ty" is an integral type, and that our 
     // value will fit into the specified type...
     switch (D.Type) {
     case 2:
-      if (Type == Type::BoolTy) {  // Special handling for boolean data
-        CPV = new ConstPoolBool(D.ConstPool64 != 0);
+      if (Ty == Type::BoolTy) {  // Special handling for boolean data
+        CPV = ConstPoolBool::get(D.ConstPool64 != 0);
       } else {
-        if (!ConstPoolSInt::isValueValidForType(Type, D.ConstPool64))
+        if (!ConstPoolSInt::isValueValidForType(Ty, D.ConstPool64))
           ThrowException("Symbolic constant pool value '" +
 			 itostr(D.ConstPool64) + "' is invalid for type '" + 
-			 Type->getName() + "'!");
-        CPV = new ConstPoolSInt(Type, D.ConstPool64);
+			 Ty->getName() + "'!");
+        CPV = ConstPoolSInt::get(Ty, D.ConstPool64);
       }
       break;
     case 3:
-      if (!ConstPoolUInt::isValueValidForType(Type, D.UConstPool64)) {
-        if (!ConstPoolSInt::isValueValidForType(Type, D.ConstPool64)) {
+      if (!ConstPoolUInt::isValueValidForType(Ty, D.UConstPool64)) {
+        if (!ConstPoolSInt::isValueValidForType(Ty, D.ConstPool64)) {
           ThrowException("Integral constant pool reference is invalid!");
         } else {     // This is really a signed reference.  Transmogrify.
-          CPV = new ConstPoolSInt(Type, D.ConstPool64);
+          CPV = ConstPoolSInt::get(Ty, D.ConstPool64);
         }
       } else {
-        CPV = new ConstPoolUInt(Type, D.UConstPool64);
+        CPV = ConstPoolUInt::get(Ty, D.UConstPool64);
       }
       break;
     case 4:
@@ -178,30 +259,17 @@ static Value *getVal(const Type *Type, const ValID &D,
       abort();
       break;
     case 5:
-      if (!ConstPoolFP::isValueValidForType(Type, D.ConstPoolFP))
+      if (!ConstPoolFP::isValueValidForType(Ty, D.ConstPoolFP))
 	ThrowException("FP constant invalid for type!!");
       else
-	CPV = new ConstPoolFP(Type, D.ConstPoolFP);
+	CPV = ConstPoolFP::get(Ty, D.ConstPoolFP);
       break;
     }
     assert(CPV && "How did we escape creating a constant??");
-
-    // Scan through the constant table and see if we already have loaded this
-    // constant.
-    //
-    ConstantPool &CP = CurMeth.CurrentMethod ? 
-                         CurMeth.CurrentMethod->getConstantPool() :
-                           CurModule.CurrentModule->getConstantPool();
-    ConstPoolVal *C = CP.find(CPV);      // Already have this constant?
-    if (C) {
-      delete CPV;  // Didn't need this after all, oh well.
-      return C;    // Yup, we already have one, recycle it!
-    }
-    CP.insert(CPV);
-      
-    // Success, everything is kosher. Lets go!
     return CPV;
   }   // End of case 2,3,4
+  default:
+    assert(0 && "Unhandled case!");
   }   // End of switch
 
 
@@ -211,15 +279,15 @@ static Value *getVal(const Type *Type, const ValID &D,
   //
   if (DoNotImprovise) return 0;  // Do we just want a null to be returned?
 
-  // TODO: Attempt to coallecse nodes that are the same with previous ones.
   Value *d = 0;
-  vector<ValueList> *LateResolver = &CurMeth.LateResolveValues;
+  vector<ValueList> *LateResolver =  (CurMeth.CurrentMethod) ? 
+    &CurMeth.LateResolveValues : &CurModule.LateResolveValues;
 
-  switch (Type->getPrimitiveID()) {
-  case Type::LabelTyID:  d = new    BBPlaceHolder(Type, D); break;
-  case Type::MethodTyID: d = new  MethPlaceHolder(Type, D); 
+  switch (Ty->getPrimitiveID()) {
+  case Type::LabelTyID:  d = new   BBPlaceHolder(Ty, D); break;
+  case Type::MethodTyID: d = new MethPlaceHolder(Ty, D); 
                          LateResolver = &CurModule.LateResolveValues; break;
-  default:               d = new ValuePlaceHolder(Type, D); break;
+  default:               d = new ValuePlaceHolder(Ty, D); break;
   }
 
   assert(d != 0 && "How did we not make something?");
@@ -254,17 +322,21 @@ static void ResolveDefinitions(vector<ValueList> &LateResolvers) {
 
       Value *TheRealValue = getVal(Type::getUniqueIDType(ty), DID, true);
 
-      if (TheRealValue == 0 && DID.Type == 1)
-        ThrowException("Reference to an invalid definition: '" +DID.getName() +
-                       "' of type '" + V->getType()->getName() + "'",
-		       getLineNumFromPlaceHolder(V));
-      else if (TheRealValue == 0)
-        ThrowException("Reference to an invalid definition: #" +itostr(DID.Num)+
-                       " of type '" + V->getType()->getName() + "'",
-		       getLineNumFromPlaceHolder(V));
+      if (TheRealValue == 0) {
+	if (DID.Type == 1)
+	  ThrowException("Reference to an invalid definition: '" +DID.getName()+
+			 "' of type '" + V->getType()->getDescription() + "'",
+			 getLineNumFromPlaceHolder(V));
+	else
+	  ThrowException("Reference to an invalid definition: #" +
+			 itostr(DID.Num) + " of type '" + 
+			 V->getType()->getDescription() + "'",
+			 getLineNumFromPlaceHolder(V));
+      }
+
+      assert(!V->isType() && "Types should be in LateResolveTypes!");
 
       V->replaceAllUsesWith(TheRealValue);
-      assert(V->use_empty());
       delete V;
     }
   }
@@ -272,103 +344,128 @@ static void ResolveDefinitions(vector<ValueList> &LateResolvers) {
   LateResolvers.clear();
 }
 
-// addConstValToConstantPool - This code is used to insert a constant into the
-// current constant pool.  This is designed to make maximal (but not more than
-// possible) reuse (merging) of constants in the constant pool.  This means that
-// multiple references to %4, for example will all get merged.
+
+// ResolveTypes - This goes through the forward referenced type table and makes
+// sure that all type references are complete.  This code is executed after the
+// constant pool of a method or module is completely parsed.
 //
-static ConstPoolVal *addConstValToConstantPool(ConstPoolVal *C) {
-  vector<ValueList> &ValTab = CurMeth.CurrentMethod ? 
-                                  CurMeth.Values : CurModule.Values;
-  ConstantPool &CP = CurMeth.CurrentMethod ? 
-                          CurMeth.CurrentMethod->getConstantPool() : 
-                          CurModule.CurrentModule->getConstantPool();
-
-  if (ConstPoolVal *CPV = CP.find(C)) {
-    // Constant already in constant pool. Try to merge the two constants
-    if (CPV->hasName() && !C->hasName()) {
-      // Merge the two values, we inherit the existing CPV's name.  
-      // InsertValue requires that the value have no name to insert correctly
-      // (because we want to fill the slot this constant would have filled)
-      //
-      string Name = CPV->getName();
-      CPV->setName("");
-      InsertValue(CPV, ValTab);
-      CPV->setName(Name);
-      delete C;
-      return CPV;
-    } else if (!CPV->hasName() && C->hasName()) {
-      // If we have a name on this value and there isn't one in the const 
-      // pool val already, propogate it.
-      //
-      CPV->setName(C->getName());
-      delete C;   // Sorry, you're toast
-      return CPV;
-    } else if (!CPV->hasName() && !C->hasName()) {
-      // Neither value has a name, trivially merge them.
-      InsertValue(CPV, ValTab);
-      delete C;
-      return CPV;
-    } else if (CPV->hasName() && C->hasName()) {
-      // Both values have distinct names.  We cannot merge them.
-      // fall through
+static void ResolveTypes(vector<PATypeHolder<Type> > &LateResolveTypes) {
+  while (!LateResolveTypes.empty()) {
+    const Type *Ty = LateResolveTypes.back();
+    ValID &DID = getValIDFromPlaceHolder(Ty);
+
+    const Type *TheRealType = getTypeVal(DID, true);
+    if (TheRealType == 0) {
+      if (DID.Type == 1)
+	ThrowException("Reference to an invalid type: '" +DID.getName(),
+		       getLineNumFromPlaceHolder(Ty));
+      else
+	ThrowException("Reference to an invalid type: #" + itostr(DID.Num),
+		       getLineNumFromPlaceHolder(Ty));
     }
-  }
 
-  // No duplication of value, check to see if our current symbol table already
-  // has a variable of this type and name...
-  //
-  if (C->hasName()) {
-    SymbolTable *SymTab = CurMeth.CurrentMethod ? 
-                                    CurMeth.CurrentMethod->getSymbolTable() :
-                                    CurModule.CurrentModule->getSymbolTable();
-    if (SymTab && SymTab->lookup(C->getType(), C->getName()))
-      ThrowException("<" + C->getType()->getName() + ">:" + C->getName() + 
-		     " already defined in translation unit!");
-  }
-
-  // Everything is happy: Insert into constant pool now!
-  CP.insert(C);
-  InsertValue(C, ValTab);
-  return C;
+    // FIXME: When types are not const
+    DerivedType *DTy = const_cast<DerivedType*>(Ty->castDerivedTypeAsserting());
+    
+    // Refine the opaque type we had to the new type we are getting.
+    DTy->refineAbstractTypeTo(TheRealType);
+
+    // No need to delete type, refine does that for us.
+    LateResolveTypes.pop_back();
+  }
 }
 
+static void setValueName(Value *V, const string &Name) {
+  SymbolTable *ST = CurMeth.CurrentMethod ? 
+    CurMeth.CurrentMethod->getSymbolTableSure() : 
+    CurModule.CurrentModule->getSymbolTableSure();
+
+  Value *Existing = ST->lookup(V->getType(), Name);
+  if (Existing) {    // Inserting a name that is already defined???
+    // There is only one case where this is allowed: when we are refining an
+    // opaque type.  In this case, Existing will be an opaque type.
+    if (const Type *Ty = Existing->castType())
+      if (Ty->isOpaqueType()) {
+	// We ARE replacing an opaque type!
+
+	// TODO: FIXME when types are not const!
+	const_cast<DerivedType*>(Ty->castDerivedTypeAsserting())->refineAbstractTypeTo(V->castTypeAsserting());
+	return;
+      }
 
-struct EqualsType {
-  const Type *T;
-  inline EqualsType(const Type *t) { T = t; }
-  inline bool operator()(const ConstPoolVal *CPV) const {
-    return static_cast<const ConstPoolType*>(CPV)->getValue() == T;
+    // Otherwise, we are a simple redefinition of a value, baaad
+    ThrowException("Redefinition of value name '" + Name + "' in the '" +
+		   V->getType()->getDescription() + "' type plane!");
   }
-};
+
+  V->setName(Name, ST);
+}
 
 
-// checkNewType - We have to be careful to add all types referenced by the
-// program to the constant pool of the method or module.  Because of this, we
-// often want to check to make sure that types used are in the constant pool,
-// and add them if they aren't.  That's what this function does.
+//===----------------------------------------------------------------------===//
+// Code for handling upreferences in type names...
 //
-static const Type *checkNewType(const Type *Ty) {
-  ConstantPool &CP = CurMeth.CurrentMethod ? 
-                          CurMeth.CurrentMethod->getConstantPool() : 
-                          CurModule.CurrentModule->getConstantPool();
-
-  // TODO: This should use ConstantPool::ensureTypeAvailable
-
-  // Get the type type plane...
-  ConstantPool::PlaneType &P = CP.getPlane(Type::TypeTy);
-  ConstantPool::PlaneType::const_iterator PI = find_if(P.begin(), P.end(), 
-						       EqualsType(Ty));
-  if (PI == P.end()) {
-    vector<ValueList> &ValTab = CurMeth.CurrentMethod ? 
-                                CurMeth.Values : CurModule.Values;
-    ConstPoolVal *CPT = new ConstPoolType(Ty);
-    CP.insert(CPT);
-    InsertValue(CPT, ValTab);
+
+// TypeContains - Returns true if Ty contains E in it.
+//
+static bool TypeContains(const Type *Ty, const Type *E) {
+  return find(cfg::tdf_begin(Ty), cfg::tdf_end(Ty), E) != cfg::tdf_end(Ty);
+}
+
+
+static vector<pair<unsigned, OpaqueType *> > UpRefs;
+
+static PATypeHolder<Type> HandleUpRefs(const Type *ty) {
+  PATypeHolder<Type> Ty(ty);
+  UR_OUT(UpRefs.size() << " upreferences active!\n");
+  for (unsigned i = 0; i < UpRefs.size(); ) {
+    UR_OUT("TypeContains(" << Ty->getDescription() << ", " 
+	   << UpRefs[i].second->getDescription() << ") = " 
+	   << TypeContains(Ty, UpRefs[i].second) << endl);
+    if (TypeContains(Ty, UpRefs[i].second)) {
+      unsigned Level = --UpRefs[i].first;   // Decrement level of upreference
+      UR_OUT("Uplevel Ref Level = " << Level << endl);
+      if (Level == 0) {                     // Upreference should be resolved! 
+	UR_OUT("About to resolve upreference!\n";
+	       string OldName = UpRefs[i].second->getDescription());
+	UpRefs[i].second->refineAbstractTypeTo(Ty);
+	UpRefs.erase(UpRefs.begin()+i);     // Remove from upreference list...
+	UR_OUT("Type '" << OldName << "' refined upreference to: "
+	       << (const void*)Ty << ", " << Ty->getDescription() << endl);
+	continue;
+      }
+    }
+
+    ++i;                                  // Otherwise, no resolve, move on...
   }
+  // FIXME: TODO: this should return the updated type
   return Ty;
 }
 
+template <class TypeTy>
+inline static void TypeDone(PATypeHolder<TypeTy> *Ty) {
+  if (UpRefs.size())
+    ThrowException("Invalid upreference in type: " + (*Ty)->getDescription());
+}
+
+// newTH - Allocate a new type holder for the specified type
+template <class TypeTy>
+inline static PATypeHolder<TypeTy> *newTH(const TypeTy *Ty) {
+  return new PATypeHolder<TypeTy>(Ty);
+}
+template <class TypeTy>
+inline static PATypeHolder<TypeTy> *newTH(const PATypeHolder<TypeTy> &TH) {
+  return new PATypeHolder<TypeTy>(TH);
+}
+
+
+// newTHC - Allocate a new type holder for the specified type that can be
+// casted to a new Type type.
+template <class TypeTy, class OldTy>
+inline static PATypeHolder<TypeTy> *newTHC(const PATypeHolder<OldTy> &Old) {
+  return new PATypeHolder<TypeTy>((const TypeTy*)Old.get());
+}
+
 
 //===----------------------------------------------------------------------===//
 //            RunVMAsmParser - Define an interface to this parser
@@ -391,37 +488,41 @@ Module *RunVMAsmParser(const string &Filename, FILE *F) {
 %}
 
 %union {
-  Module                  *ModuleVal;
-  Method                  *MethodVal;
-  MethodArgument          *MethArgVal;
-  BasicBlock              *BasicBlockVal;
-  TerminatorInst          *TermInstVal;
-  Instruction             *InstVal;
-  ConstPoolVal            *ConstVal;
-  const Type              *TypeVal;
-  Value                   *ValueVal;
-
-  list<MethodArgument*>   *MethodArgList;
-  list<Value*>            *ValueList;
-  list<const Type*>       *TypeList;
+  Module                           *ModuleVal;
+  Method                           *MethodVal;
+  MethodArgument                   *MethArgVal;
+  BasicBlock                       *BasicBlockVal;
+  TerminatorInst                   *TermInstVal;
+  Instruction                      *InstVal;
+  ConstPoolVal                     *ConstVal;
+
+  const Type                       *PrimType;
+  PATypeHolder<Type>               *TypeVal;
+  PATypeHolder<ArrayType>          *ArrayTypeTy;
+  PATypeHolder<StructType>         *StructTypeTy;
+  Value                            *ValueVal;
+
+  list<MethodArgument*>            *MethodArgList;
+  list<Value*>                     *ValueList;
+  list<PATypeHolder<Type> >        *TypeList;
   list<pair<Value*, BasicBlock*> > *PHIList;   // Represent the RHS of PHI node
   list<pair<ConstPoolVal*, BasicBlock*> > *JumpTable;
-  vector<ConstPoolVal*>   *ConstVector;
-
-  int64_t                  SInt64Val;
-  uint64_t                 UInt64Val;
-  int                      SIntVal;
-  unsigned                 UIntVal;
-  double                   FPVal;
-
-  char                    *StrVal;   // This memory is allocated by strdup!
-  ValID                    ValIDVal; // May contain memory allocated by strdup
-
-  Instruction::UnaryOps    UnaryOpVal;
-  Instruction::BinaryOps   BinaryOpVal;
-  Instruction::TermOps     TermOpVal;
-  Instruction::MemoryOps   MemOpVal;
-  Instruction::OtherOps    OtherOpVal;
+  vector<ConstPoolVal*>            *ConstVector;
+
+  int64_t                           SInt64Val;
+  uint64_t                          UInt64Val;
+  int                               SIntVal;
+  unsigned                          UIntVal;
+  double                            FPVal;
+
+  char                             *StrVal;   // This memory is strdup'd!
+  ValID                             ValIDVal; // strdup'd memory maybe!
+
+  Instruction::UnaryOps             UnaryOpVal;
+  Instruction::BinaryOps            BinaryOpVal;
+  Instruction::TermOps              TermOpVal;
+  Instruction::MemoryOps            MemOpVal;
+  Instruction::OtherOps             OtherOpVal;
 }
 
 %type <ModuleVal>     Module MethodList
@@ -435,7 +536,7 @@ Module *RunVMAsmParser(const string &Filename, FILE *F) {
 %type <MethArgVal>    ArgVal
 %type <PHIList>       PHIList
 %type <ValueList>     ValueRefList ValueRefListE  // For call param lists
-%type <TypeList>      TypeList ArgTypeList
+%type <TypeList>      TypeListI ArgTypeListI
 %type <JumpTable>     JumpTable
 
 %type <ValIDVal>      ValueRef ConstValueRef // Reference to a definition or BB
@@ -455,9 +556,13 @@ Module *RunVMAsmParser(const string &Filename, FILE *F) {
 %token  <FPVal>     FPVAL     // Float or Double constant
 
 // Built in types...
-%type  <TypeVal> Types TypesV SIntType UIntType IntType FPType
-%token <TypeVal> VOID BOOL SBYTE UBYTE SHORT USHORT INT UINT LONG ULONG
-%token <TypeVal> FLOAT DOUBLE TYPE LABEL
+%type  <TypeVal> Types TypesV UpRTypes UpRTypesV
+%type  <PrimType> SIntType UIntType IntType FPType PrimType   // Classifications
+%token <TypeVal>  OPAQUE
+%token <PrimType> VOID BOOL SBYTE UBYTE SHORT USHORT INT UINT LONG ULONG
+%token <PrimType> FLOAT DOUBLE TYPE LABEL
+%type  <ArrayTypeTy> ArrayType ArrayTypeI
+%type  <StructTypeTy> StructType StructTypeI
 
 %token <StrVal>     VAR_ID LABELSTR STRINGCONSTANT
 %type  <StrVal>  OptVAR_ID OptAssign
@@ -505,17 +610,6 @@ EINT64VAL : EUINT64VAL {
   $$ = (int64_t)$1;
 }
 
-// Types includes all predefined types... except void, because you can't do 
-// anything with it except for certain specific things...
-//
-// User defined types are added later...
-//
-Types     : BOOL | SBYTE | UBYTE | SHORT | USHORT | INT | UINT 
-Types     : LONG | ULONG | FLOAT | DOUBLE | TYPE | LABEL
-
-// TypesV includes all of 'Types', but it also includes the void type.
-TypesV    : Types | VOID
-
 // Operations that are notably excluded from this list include: 
 // RET, BR, & SWITCH because they end basic blocks and are treated specially.
 //
@@ -528,8 +622,8 @@ ShiftOps  : SHL | SHR
 // thing... for example, only a signed, unsigned, or integral type.
 SIntType :  LONG |  INT |  SHORT | SBYTE
 UIntType : ULONG | UINT | USHORT | UBYTE
-IntType : SIntType | UIntType
-FPType  : FLOAT | DOUBLE
+IntType  : SIntType | UIntType
+FPType   : FLOAT | DOUBLE
 
 // OptAssign - Value producing statements have an optional assignment component
 OptAssign : VAR_ID '=' {
@@ -539,102 +633,178 @@ OptAssign : VAR_ID '=' {
     $$ = 0; 
   }
 
-// ConstVal - The various declarations that go into the constant pool.  This
-// includes all forward declarations of types, constants, and functions.
+
+//===----------------------------------------------------------------------===//
+// Types includes all predefined types... except void, because it can only be
+// used in specific contexts (method returning void for example).  To have
+// access to it, a user must explicitly use TypesV.
 //
-// This is broken into two sections: ExtendedConstVal and ConstVal
+
+// TypesV includes all of 'Types', but it also includes the void type.
+TypesV    : Types    | VOID { $$ = newTH($1); }
+UpRTypesV : UpRTypes | VOID { $$ = newTH($1); }
+
+Types     : UpRTypes {
+    TypeDone($$ = $1);
+  }
+
+
+// Derived types are added later...
 //
-ExtendedConstVal: '[' Types ']' '[' ConstVector ']' { // Nonempty unsized array
-    // Verify all elements are correct type!
-    const ArrayType *AT = ArrayType::getArrayType($2);
-    for (unsigned i = 0; i < $5->size(); i++) {
-      if ($2 != (*$5)[i]->getType())
-	ThrowException("Element #" + utostr(i) + " is not of type '" + 
-		       $2->getName() + "' as required!\nIt is of type '" +
-		       (*$5)[i]->getType()->getName() + "'.");
-    }
+PrimType : BOOL | SBYTE | UBYTE | SHORT  | USHORT | INT   | UINT 
+PrimType : LONG | ULONG | FLOAT | DOUBLE | TYPE   | LABEL
+UpRTypes : OPAQUE | PrimType { $$ = newTH($1); }
+UpRTypes : ValueRef {                    // Named types are also simple types...
+  $$ = newTH(getTypeVal($1));
+}
 
-    $$ = new ConstPoolArray(AT, *$5);
-    delete $5;
+// ArrayTypeI - Internal version of ArrayType that can have incomplete uprefs
+//
+ArrayTypeI : '[' UpRTypesV ']' {               // Unsized array type?
+    $$ = newTHC<ArrayType>(HandleUpRefs(ArrayType::get(*$2)));
+    delete $2;
   }
-  | '[' Types ']' '[' ']' {                  // Empty unsized array constant
-    vector<ConstPoolVal*> Empty;
-    $$ = new ConstPoolArray(ArrayType::getArrayType($2), Empty);
+  | '[' EUINT64VAL 'x' UpRTypes ']' {          // Sized array type?
+    $$ = newTHC<ArrayType>(HandleUpRefs(ArrayType::get(*$4, (int)$2)));
+    delete $4;
   }
-  | '[' Types ']' 'c' STRINGCONSTANT {
-    char *EndStr = UnEscapeLexed($5, true);
-    vector<ConstPoolVal*> Vals;
-    if ($2 == Type::SByteTy) {
-      for (char *C = $5; C != EndStr; ++C)
-	Vals.push_back(addConstValToConstantPool(new ConstPoolSInt($2, *C)));
-    } else if ($2 == Type::UByteTy) {
-      for (char *C = $5; C != EndStr; ++C)
-	Vals.push_back(addConstValToConstantPool(new ConstPoolUInt($2, *C)));
-    } else {
-      ThrowException("Cannot build string arrays of non byte sized elements!");
-    }
-    free($5);
 
-    $$ = new ConstPoolArray(ArrayType::getArrayType($2), Vals);
+StructTypeI : '{' TypeListI '}' {              // Structure type?
+    vector<const Type*> Elements;
+    mapto($2->begin(), $2->end(), back_inserter(Elements), 
+	mem_fun_ref(&PATypeHandle<Type>::get));
+
+    $$ = newTHC<StructType>(HandleUpRefs(StructType::get(Elements)));
+    delete $2;
   }
-  | '[' EUINT64VAL 'x' Types ']' '[' ConstVector ']' {
-    // Verify all elements are correct type!
-    const ArrayType *AT = ArrayType::getArrayType($4, (int)$2);
-    if ($2 != $7->size())
+  | '{' '}' {                                  // Empty structure type?
+    $$ = newTH(StructType::get(vector<const Type*>()));
+  }
+
+
+// Include derived types in the Types production.
+//
+UpRTypes : '\\' EUINT64VAL {                   // Type UpReference
+    if ($2 > (uint64_t)INT64_MAX) ThrowException("Value out of range!");
+    OpaqueType *OT = OpaqueType::get();        // Use temporary placeholder
+    UpRefs.push_back(make_pair((unsigned)$2, OT));  // Add to vector...
+    $$ = newTH<Type>(OT);
+    UR_OUT("New Upreference!\n");
+  }
+  | UpRTypesV '(' ArgTypeListI ')' {           // Method derived type?
+    vector<const Type*> Params;
+    mapto($3->begin(), $3->end(), back_inserter(Params), 
+	  mem_fun_ref(&PATypeHandle<Type>::get));
+    $$ = newTH(HandleUpRefs(MethodType::get(*$1, Params)));
+    delete $3;      // Delete the argument list
+    delete $1;      // Delete the old type handle
+  }
+  | ArrayTypeI {                               // [Un]sized array type?
+    $$ = newTHC<Type>(*$1); delete $1;
+  }
+  | StructTypeI {                              // Structure type?
+    $$ = newTHC<Type>(*$1); delete $1;
+  }
+  | UpRTypes '*' {                             // Pointer type?
+    $$ = newTH(HandleUpRefs(PointerType::get(*$1)));
+    delete $1;  // Delete the type handle
+  }
+
+// Define some helpful top level types that do not allow UpReferences to escape
+//
+ArrayType  : ArrayTypeI  { TypeDone($$ = $1); }
+StructType : StructTypeI { TypeDone($$ = $1); }
+
+
+
+// TypeList - Used for struct declarations and as a basis for method type 
+// declaration type lists
+//
+TypeListI : UpRTypes {
+    $$ = new list<PATypeHolder<Type> >();
+    $$->push_back(*$1); delete $1;
+  }
+  | TypeListI ',' UpRTypes {
+    ($$=$1)->push_back(*$3); delete $3;
+  }
+
+// ArgTypeList - List of types for a method type declaration...
+ArgTypeListI : TypeListI
+  | TypeListI ',' DOTDOTDOT {
+    ($$=$1)->push_back(Type::VoidTy);
+  }
+  | DOTDOTDOT {
+    ($$ = new list<PATypeHolder<Type> >())->push_back(Type::VoidTy);
+  }
+  | /*empty*/ {
+    $$ = new list<PATypeHolder<Type> >();
+  }
+
+
+// ConstVal - The various declarations that go into the constant pool.  This
+// includes all forward declarations of types, constants, and functions.
+//
+// This is broken into two sections: ExtendedConstVal and ConstVal
+//
+ExtendedConstVal: ArrayType '[' ConstVector ']' { // Nonempty unsized arr
+    const ArrayType *ATy = *$1;
+    const Type *ETy = ATy->getElementType();
+    int NumElements = ATy->getNumElements();
+
+    // Verify that we have the correct size...
+    if (NumElements != -1 && NumElements != (int)$3->size())
       ThrowException("Type mismatch: constant sized array initialized with " +
-		     utostr($7->size()) +  " arguments, but has size of " + 
-		     itostr((int)$2) + "!");
+		     utostr($3->size()) +  " arguments, but has size of " + 
+		     itostr(NumElements) + "!");
 
-    for (unsigned i = 0; i < $7->size(); i++) {
-      if ($4 != (*$7)[i]->getType())
+    // Verify all elements are correct type!
+    for (unsigned i = 0; i < $3->size(); i++) {
+      if (ETy != (*$3)[i]->getType())
 	ThrowException("Element #" + utostr(i) + " is not of type '" + 
-		       $4->getName() + "' as required!\nIt is of type '" +
-		       (*$7)[i]->getType()->getName() + "'.");
+		       ETy->getName() + "' as required!\nIt is of type '" +
+		       (*$3)[i]->getType()->getName() + "'.");
     }
 
-    $$ = new ConstPoolArray(AT, *$7);
-    delete $7;
+    $$ = ConstPoolArray::get(ATy, *$3);
+    delete $1; delete $3;
   }
-  | '[' EUINT64VAL 'x' Types ']' '[' ']' {
-    if ($2 != 0) 
+  | ArrayType '[' ']' {
+    int NumElements = (*$1)->getNumElements();
+    if (NumElements != -1 && NumElements != 0) 
       ThrowException("Type mismatch: constant sized array initialized with 0"
-		     " arguments, but has size of " + itostr((int)$2) + "!");
-    vector<ConstPoolVal*> Empty;
-    $$ = new ConstPoolArray(ArrayType::getArrayType($4, 0), Empty);
-  }
-  | '[' EUINT64VAL 'x' Types ']' 'c' STRINGCONSTANT {
-    char *EndStr = UnEscapeLexed($7, true);
-    if ($2 != (unsigned)(EndStr-$7))
+		     " arguments, but has size of " + itostr(NumElements) +"!");
+    $$ = ConstPoolArray::get((*$1), vector<ConstPoolVal*>());
+    delete $1;
+  }
+  | ArrayType 'c' STRINGCONSTANT {
+    const ArrayType *ATy = *$1;
+    int NumElements = ATy->getNumElements();
+    const Type *ETy = ATy->getElementType();
+    char *EndStr = UnEscapeLexed($3, true);
+    if (NumElements != -1 && NumElements != (EndStr-$3))
       ThrowException("Can't build string constant of size " + 
-		     itostr((int)(EndStr-$7)) +
-		     " when array has size " + itostr((int)$2) + "!");
+		     itostr((int)(EndStr-$3)) +
+		     " when array has size " + itostr(NumElements) + "!");
     vector<ConstPoolVal*> Vals;
-    if ($4 == Type::SByteTy) {
-      for (char *C = $7; C != EndStr; ++C)
-	Vals.push_back(addConstValToConstantPool(new ConstPoolSInt($4, *C)));
-    } else if ($4 == Type::UByteTy) {
-      for (char *C = $7; C != EndStr; ++C)
-	Vals.push_back(addConstValToConstantPool(new ConstPoolUInt($4, *C)));
+    if (ETy == Type::SByteTy) {
+      for (char *C = $3; C != EndStr; ++C)
+	Vals.push_back(ConstPoolSInt::get(ETy, *C));
+    } else if (ETy == Type::UByteTy) {
+      for (char *C = $3; C != EndStr; ++C)
+	Vals.push_back(ConstPoolUInt::get(ETy, *C));
     } else {
+      free($3);
       ThrowException("Cannot build string arrays of non byte sized elements!");
     }
-    free($7);
-
-    $$ = new ConstPoolArray(ArrayType::getArrayType($4, (int)$2), Vals);
-  }
-  | '{' TypeList '}' '{' ConstVector '}' {
-    StructType::ElementTypes Types($2->begin(), $2->end());
-    delete $2;
-
-    const StructType *St = StructType::getStructType(Types);
-    $$ = new ConstPoolStruct(St, *$5);
-    delete $5;
+    free($3);
+    $$ = ConstPoolArray::get(ATy, Vals);
+    delete $1;
   }
-  | '{' '}' '{' '}' {
-    const StructType *St = 
-      StructType::getStructType(StructType::ElementTypes());
-    vector<ConstPoolVal*> Empty;
-    $$ = new ConstPoolStruct(St, Empty);
+  | StructType '{' ConstVector '}' {
+    // FIXME: TODO: Check to see that the constants are compatible with the type
+    // initializer!
+    $$ = ConstPoolStruct::get(*$1, *$3);
+    delete $1; delete $3;
   }
 /*
   | Types '*' ConstVal {
@@ -646,36 +816,33 @@ ExtendedConstVal: '[' Types ']' '[' ConstVector ']' { // Nonempty unsized array
 ConstVal : ExtendedConstVal {
     $$ = $1;
   }
-  | TYPE TypesV {                    // Type constants
-    $$ = new ConstPoolType($2);
-  }
   | SIntType EINT64VAL {     // integral constants
     if (!ConstPoolSInt::isValueValidForType($1, $2))
       ThrowException("Constant value doesn't fit in type!");
-    $$ = new ConstPoolSInt($1, $2);
+    $$ = ConstPoolSInt::get($1, $2);
   } 
   | UIntType EUINT64VAL {           // integral constants
     if (!ConstPoolUInt::isValueValidForType($1, $2))
       ThrowException("Constant value doesn't fit in type!");
-    $$ = new ConstPoolUInt($1, $2);
+    $$ = ConstPoolUInt::get($1, $2);
   } 
   | BOOL TRUE {                     // Boolean constants
-    $$ = new ConstPoolBool(true);
+    $$ = ConstPoolBool::True;
   }
   | BOOL FALSE {                    // Boolean constants
-    $$ = new ConstPoolBool(false);
+    $$ = ConstPoolBool::False;
   }
   | FPType FPVAL {                   // Float & Double constants
-    $$ = new ConstPoolFP($1, $2);
+    $$ = ConstPoolFP::get($1, $2);