Reimplement the old and horrible bison parser for .ll files with a nice

and clean recursive descent parser.

This change has a couple of ramifications:
1. The parser code is about 400 lines shorter (in what we maintain, not
   including what is autogenerated).
2. The code should be significantly faster than the old code because we 
   don't have to work around bison's poor handling of datatypes with 
   ctors/dtors.  This also makes the code much more resistant to memory 
   leaks.
3. We now get caret diagnostics from the .ll parser, woo.
4. The actual diagnostics emited from the parser are completely different
   so a bunch of testcases had to be updated.
5. I now disallow "%ty = type opaque %ty = type i32".  There was no good
   reason to support this, it was just an accident of the old 
   implementation.  I have no reason to think that anyone is actually using
   this.
6. The syntax for sticking a global variable has changed to make it 
   unambiguous.  I don't think anyone is depending on this since only clang
   supports this and it is not solid yet, so I'm not worried about anything
   breaking.
7. This gets rid of the last use of bison, and along with it the .cvs files.
   I'll prune this from the makefiles as a subsequent commit.

There are a few minor cleanups that can be done after this commit (suggestions
welcome!) but this passes dejagnu testing and is ready for its time in the
limelight.



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

1 files changed, 3158 insertions, 0 deletions

diff --git a/lib/AsmParser/LLParser.cpp b/lib/AsmParser/LLParser.cpp
new file mode 100644
index 0000000000..eefdc6c239
--- /dev/null
+++ b/lib/AsmParser/LLParser.cpp
@@ -0,0 +1,3158 @@
+//===-- LLParser.cpp - Parser Class ---------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines the parser class for .ll files.
+//
+//===----------------------------------------------------------------------===//
+
+#include "LLParser.h"
+#include "llvm/AutoUpgrade.h"
+#include "llvm/CallingConv.h"
+#include "llvm/Constants.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/InlineAsm.h"
+#include "llvm/Instructions.h"
+#include "llvm/Module.h"
+#include "llvm/ValueSymbolTable.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/Support/raw_ostream.h"
+using namespace llvm;
+
+// ValID - Represents a reference of a definition of some sort with no type.
+// There are several cases where we have to parse the value but where the type
+// can depend on later context.  This may either
+// be a numeric reference or a symbolic (%var) reference.  This is just a
+// discriminated union.
+//
+// Note that I can't implement this class in a straight forward manner with
+// constructors and stuff because it goes in a union.
+//
+namespace llvm {
+  struct ValID {
+    enum {
+      t_LocalID, t_GlobalID,      // ID in UIntVal.
+      t_LocalName, t_GlobalName,  // Name in StrVal.
+      t_APSInt, t_APFloat,        // Value in APSIntVal/APFloatVal.
+      t_Null, t_Undef, t_Zero,    // No value.
+      t_Constant,                 // Value in ConstantVal.
+      t_InlineAsm                 // Value in StrVal/StrVal2/UIntVal.
+    } Kind;
+    
+    LLParser::LocTy Loc;
+    unsigned UIntVal;
+    std::string StrVal, StrVal2;
+    APSInt APSIntVal;
+    APFloat APFloatVal;
+    Constant *ConstantVal;
+    ValID() : APFloatVal(0.0) {}
+  };
+}
+
+/// Parse: module ::= toplevelentity*
+Module *LLParser::Run() {
+  M = new Module(Lex.getFilename());
+  
+  if (ParseTopLevelEntities() ||
+      ValidateEndOfModule()) {
+    delete M;
+    return 0;
+  }
+  
+  return M;
+}
+
+/// ValidateEndOfModule - Do final validity and sanity checks at the end of the
+/// module.
+bool LLParser::ValidateEndOfModule() {
+  if (!ForwardRefTypes.empty())
+    return Error(ForwardRefTypes.begin()->second.second,
+                 "use of undefined type named '" +
+                 ForwardRefTypes.begin()->first + "'");
+  if (!ForwardRefTypeIDs.empty())
+    return Error(ForwardRefTypeIDs.begin()->second.second,
+                 "use of undefined type '%" +
+                 utostr(ForwardRefTypeIDs.begin()->first) + "'");
+  
+  if (!ForwardRefVals.empty())
+    return Error(ForwardRefVals.begin()->second.second,
+                 "use of undefined value '@" + ForwardRefVals.begin()->first +
+                 "'");
+  
+  if (!ForwardRefValIDs.empty())
+    return Error(ForwardRefValIDs.begin()->second.second,
+                 "use of undefined value '@" +
+                 utostr(ForwardRefValIDs.begin()->first) + "'");
+  
+  // Look for intrinsic functions and CallInst that need to be upgraded
+  for (Module::iterator FI = M->begin(), FE = M->end(); FI != FE; )
+    UpgradeCallsToIntrinsic(FI++); // must be post-increment, as we remove
+  
+  return false;
+}
+
+//===----------------------------------------------------------------------===//
+// Top-Level Entities
+//===----------------------------------------------------------------------===//
+
+bool LLParser::ParseTopLevelEntities() {
+  Lex.Lex();
+  while (1) {
+    switch (Lex.getKind()) {
+    default:         return TokError("expected top-level entity");
+    case lltok::Eof: return false;
+    //case lltok::kw_define:
+    case lltok::kw_declare: if (ParseDeclare()) return true; break;
+    case lltok::kw_define:  if (ParseDefine()) return true; break;
+    case lltok::kw_module:  if (ParseModuleAsm()) return true; break;
+    case lltok::kw_target:  if (ParseTargetDefinition()) return true; break;
+    case lltok::kw_deplibs: if (ParseDepLibs()) return true; break;
+    case lltok::kw_type:    if (ParseUnnamedType()) return true; break;
+    case lltok::StringConstant: // FIXME: REMOVE IN LLVM 3.0
+    case lltok::LocalVar:   if (ParseNamedType()) return true; break;
+    case lltok::GlobalVar:  if (ParseNamedGlobal()) return true; break;
+
+    // The Global variable production with no name can have many different
+    // optional leading prefixes, the production is:
+    // GlobalVar ::= OptionalLinkage OptionalVisibility OptionalThreadLocal
+    //               OptionalAddrSpace ('constant'|'global') ...
+    case lltok::kw_internal:      // OptionalLinkage
+    case lltok::kw_weak:          // OptionalLinkage
+    case lltok::kw_linkonce:      // OptionalLinkage
+    case lltok::kw_appending:     // OptionalLinkage
+    case lltok::kw_dllexport:     // OptionalLinkage
+    case lltok::kw_common:        // OptionalLinkage
+    case lltok::kw_dllimport:     // OptionalLinkage
+    case lltok::kw_extern_weak:   // OptionalLinkage
+    case lltok::kw_external: {    // OptionalLinkage
+      unsigned Linkage, Visibility;
+      if (ParseOptionalLinkage(Linkage) ||
+          ParseOptionalVisibility(Visibility) ||
+          ParseGlobal("", 0, Linkage, true, Visibility))
+        return true;
+      break;
+    }
+    case lltok::kw_default:       // OptionalVisibility
+    case lltok::kw_hidden:        // OptionalVisibility
+    case lltok::kw_protected: {   // OptionalVisibility
+      unsigned Visibility;
+      if (ParseOptionalVisibility(Visibility) ||
+          ParseGlobal("", 0, 0, false, Visibility))
+        return true;
+      break;
+    }
+        
+    case lltok::kw_thread_local:  // OptionalThreadLocal
+    case lltok::kw_addrspace:     // OptionalAddrSpace
+    case lltok::kw_constant:      // GlobalType
+    case lltok::kw_global:        // GlobalType
+      if (ParseGlobal("", 0, 0, false, 0)) return true;
+      break;
+    }
+  }
+}
+
+
+/// toplevelentity
+///   ::= 'module' 'asm' STRINGCONSTANT
+bool LLParser::ParseModuleAsm() {
+  assert(Lex.getKind() == lltok::kw_module);
+  Lex.Lex();
+  
+  if (ParseToken(lltok::kw_asm, "expected 'module asm'")) return true;
+  
+  if (Lex.getKind() != lltok::StringConstant)
+    return TokError("expected 'module asm \"foo\"'");
+  
+  const std::string &AsmSoFar = M->getModuleInlineAsm();
+  if (AsmSoFar.empty())
+    M->setModuleInlineAsm(Lex.getStrVal());
+  else
+    M->setModuleInlineAsm(AsmSoFar+"\n"+Lex.getStrVal());
+  Lex.Lex();
+  return false;
+}
+
+/// toplevelentity
+///   ::= 'target' 'triple' '=' STRINGCONSTANT
+///   ::= 'target' 'datalayout' '=' STRINGCONSTANT
+bool LLParser::ParseTargetDefinition() {
+  assert(Lex.getKind() == lltok::kw_target);
+  switch (Lex.Lex()) {
+  default: return TokError("unknown target property");
+  case lltok::kw_triple:
+    Lex.Lex();
+    if (ParseToken(lltok::equal, "expected '=' after target triple"))
+      return true;
+    if (Lex.getKind() != lltok::StringConstant)
+      return TokError("expected string after target triple '='");
+    M->setTargetTriple(Lex.getStrVal());
+    Lex.Lex();
+    return false;
+  case lltok::kw_datalayout:
+    Lex.Lex();
+    if (ParseToken(lltok::equal, "expected '=' after target datalayout"))
+      return true;
+    if (Lex.getKind() != lltok::StringConstant)
+      return TokError("expected string after target datalayout '='");
+    M->setDataLayout(Lex.getStrVal());
+    Lex.Lex();
+    return false;
+  }
+}
+
+/// toplevelentity
+///   ::= 'deplibs' '=' '[' ']'
+///   ::= 'deplibs' '=' '[' STRINGCONSTANT (',' STRINGCONSTANT)* ']'
+bool LLParser::ParseDepLibs() {
+  assert(Lex.getKind() == lltok::kw_deplibs);
+  if (Lex.Lex() != lltok::equal)
+    return TokError("expected '=' after deplibs");
+
+  if (Lex.Lex() != lltok::lsquare)
+    return TokError("expected '=' after deplibs");
+
+  if (Lex.Lex() == lltok::rsquare) {
+    Lex.Lex();
+    return false;
+  }
+  
+  if (Lex.getKind() != lltok::StringConstant)
+    return TokError("expected string in deplib list");
+
+  M->addLibrary(Lex.getStrVal());
+
+  while (Lex.Lex() == lltok::comma) {
+    if (Lex.Lex() != lltok::StringConstant)
+      return TokError("expected string in deplibs list");
+    M->addLibrary(Lex.getStrVal());
+  }
+
+  if (Lex.getKind() != lltok::rsquare)
+    return TokError("expected ']' at end of list");
+  Lex.Lex();
+  return false;
+}
+
+/// toplevelentity
+///   ::= 'type' type
+bool LLParser::ParseUnnamedType() {
+  assert(Lex.getKind() == lltok::kw_type);
+  LocTy TypeLoc = Lex.getLoc();
+  Lex.Lex(); // eat kw_type
+
+  PATypeHolder Ty(Type::VoidTy);
+  if (ParseType(Ty)) return true;
+ 
+  unsigned TypeID = NumberedTypes.size();
+  
+  // We don't allow assigning names to void type
+  if (Ty == Type::VoidTy)
+    return Error(TypeLoc, "can't assign name to the void type");
+  
+  // See if this type was previously referenced.
+  std::map<unsigned, std::pair<PATypeHolder, LocTy> >::iterator
+    FI = ForwardRefTypeIDs.find(TypeID);
+  if (FI != ForwardRefTypeIDs.end()) {
+    cast<DerivedType>(FI->second.first.get())->refineAbstractTypeTo(Ty);
+    Ty = FI->second.first.get();
+    ForwardRefTypeIDs.erase(FI);
+  }
+  
+  NumberedTypes.push_back(Ty);
+  
+  return false;
+}
+
+/// toplevelentity
+///   ::= LocalVar '=' 'type' type
+bool LLParser::ParseNamedType() {
+  std::string Name = Lex.getStrVal();
+  LocTy NameLoc = Lex.getLoc();
+  
+  if (Lex.Lex() != lltok::equal)
+    return TokError("expected '=' after name");
+  if (Lex.Lex() != lltok::kw_type)
+    return TokError("expected 'type' after name");
+  Lex.Lex(); // consume 'type'.
+  
+  PATypeHolder Ty(Type::VoidTy);
+  if (ParseType(Ty)) return true;
+  
+  // We don't allow assigning names to void type
+  if (Ty == Type::VoidTy)
+    return Error(NameLoc, "can't assign name '" + Name + "' to the void type");
+
+  // Set the type name, checking for conflicts as we do so.
+  bool AlreadyExists = M->addTypeName(Name, Ty);
+  if (!AlreadyExists) return false;
+
+  // See if this type is a forward reference.  We need to eagerly resolve
+  // types to allow recursive type redefinitions below.
+  std::map<std::string, std::pair<PATypeHolder, LocTy> >::iterator
+  FI = ForwardRefTypes.find(Name);
+  if (FI != ForwardRefTypes.end()) {
+    cast<DerivedType>(FI->second.first.get())->refineAbstractTypeTo(Ty);
+    Ty = FI->second.first.get();
+    ForwardRefTypes.erase(FI);
+  }
+  
+  // Inserting a name that is already defined, get the existing name.
+  const Type *Existing = M->getTypeByName(Name);
+  assert(Existing && "Conflict but no matching type?!");
+    
+  // Otherwise, this is an attempt to redefine a type. That's okay if
+  // the redefinition is identical to the original.
+  // FIXME: REMOVE REDEFINITIONS IN LLVM 3.0
+  if (Existing == Ty) return false;
+  
+  // Any other kind of (non-equivalent) redefinition is an error.
+  return Error(NameLoc, "redefinition of type named '" + Name + "' of type '" +
+               Ty->getDescription() + "'");
+}
+
+
+/// toplevelentity
+///   ::= 'declare' FunctionHeader
+bool LLParser::ParseDeclare() {
+  assert(Lex.getKind() == lltok::kw_declare);
+  Lex.Lex();
+  
+  Function *F;
+  return ParseFunctionHeader(F, false);
+}
+
+/// toplevelentity
+///   ::= 'define' FunctionHeader '{' ...
+bool LLParser::ParseDefine() {
+  assert(Lex.getKind() == lltok::kw_define);
+  Lex.Lex();
+  
+  Function *F;
+  if (ParseFunctionHeader(F, true)) return true;
+  
+  return ParseFunctionBody(*F);
+}
+
+bool LLParser::ParseGlobalType(bool &IsConstant) {
+  if (Lex.getKind() == lltok::kw_constant)
+    IsConstant = true;
+  else if (Lex.getKind() == lltok::kw_global)
+    IsConstant = false;
+  else
+    return TokError("expected 'global' or 'constant'");
+  Lex.Lex();
+  return false;
+}
+
+/// ParseNamedGlobal:
+///   GlobalVar '=' OptionalVisibility ALIAS ...
+///   GlobalVar '=' OptionalLinkage OptionalVisibility ...   -> global variable
+bool LLParser::ParseNamedGlobal() {
+  assert(Lex.getKind() == lltok::GlobalVar);
+  LocTy NameLoc = Lex.getLoc();
+  std::string Name = Lex.getStrVal();
+  Lex.Lex();
+  
+  bool HasLinkage;
+  unsigned Linkage, Visibility;
+  if (ParseToken(lltok::equal, "expected '=' in global variable") ||
+      ParseOptionalLinkage(Linkage, HasLinkage) ||
+      ParseOptionalVisibility(Visibility))
+    return true;
+  
+  if (HasLinkage || Lex.getKind() != lltok::kw_alias)
+    return ParseGlobal(Name, NameLoc, Linkage, HasLinkage, Visibility);
+  return ParseAlias(Name, NameLoc, Visibility);
+}
+
+/// ParseAlias:
+///   ::= GlobalVar '=' OptionalVisibility 'alias' OptionalLinkage Aliasee
+/// Aliasee
+///   ::= TypeAndValue | 'bitcast' '(' TypeAndValue 'to' Type ')'
+///
+/// Everything through visibility has already been parsed.
+///
+bool LLParser::ParseAlias(const std::string &Name, LocTy NameLoc,
+                          unsigned Visibility) {
+  assert(Lex.getKind() == lltok::kw_alias);
+  Lex.Lex();
+  unsigned Linkage;
+  LocTy LinkageLoc = Lex.getLoc();
+  if (ParseOptionalLinkage(Linkage))
+    return true;
+
+  if (Linkage != GlobalValue::ExternalLinkage &&
+      Linkage != GlobalValue::WeakLinkage &&
+      Linkage != GlobalValue::InternalLinkage)
+    return Error(LinkageLoc, "invalid linkage type for alias");
+  
+  Constant *Aliasee;
+  LocTy AliaseeLoc = Lex.getLoc();
+  if (Lex.getKind() != lltok::kw_bitcast) {
+    if (ParseGlobalTypeAndValue(Aliasee)) return true;
+  } else {
+    // The bitcast dest type is not present, it is implied by the dest type.
+    ValID ID;
+    if (ParseValID(ID)) return true;
+    if (ID.Kind != ValID::t_Constant)
+      return Error(AliaseeLoc, "invalid aliasee");
+    Aliasee = ID.ConstantVal;
+  }
+  
+  if (!isa<PointerType>(Aliasee->getType()))
+    return Error(AliaseeLoc, "alias must have pointer type");
+
+  // Okay, create the alias but do not insert it into the module yet.
+  GlobalAlias* GA = new GlobalAlias(Aliasee->getType(),
+                                    (GlobalValue::LinkageTypes)Linkage, Name,
+                                    Aliasee);
+  GA->setVisibility((GlobalValue::VisibilityTypes)Visibility);
+  
+  // See if this value already exists in the symbol table.  If so, it is either
+  // a redefinition or a definition of a forward reference.
+  if (GlobalValue *Val =
+        cast_or_null<GlobalValue>(M->getValueSymbolTable().lookup(Name))) {
+    // See if this was a redefinition.  If so, there is no entry in
+    // ForwardRefVals.
+    std::map<std::string, std::pair<GlobalValue*, LocTy> >::iterator
+      I = ForwardRefVals.find(Name);
+    if (I == ForwardRefVals.end())
+      return Error(NameLoc, "redefinition of global named '@" + Name + "'");
+
+    // Otherwise, this was a definition of forward ref.  Verify that types
+    // agree.
+    if (Val->getType() != GA->getType())
+      return Error(NameLoc,
+              "forward reference and definition of alias have different types");
+    
+    // If they agree, just RAUW the old value with the alias and remove the
+    // forward ref info.
+    Val->replaceAllUsesWith(GA);
+    Val->eraseFromParent();
+    ForwardRefVals.erase(I);
+  }
+  
+  // Insert into the module, we know its name won't collide now.
+  M->getAliasList().push_back(GA);
+  assert(GA->getNameStr() == Name && "Should not be a name conflict!");
+  
+  return false;
+}
+
+/// ParseGlobal
+///   ::= GlobalVar '=' OptionalLinkage OptionalVisibility OptionalThreadLocal
+///       OptionalAddrSpace GlobalType Type Const
+///   ::= OptionalLinkage OptionalVisibility OptionalThreadLocal
+///       OptionalAddrSpace GlobalType Type Const
+///
+/// Everything through visibility has been parsed already.
+///
+bool LLParser::ParseGlobal(const std::string &Name, LocTy NameLoc,
+                           unsigned Linkage, bool HasLinkage,
+                           unsigned Visibility) {
+  unsigned AddrSpace;
+  bool ThreadLocal, IsConstant;
+  LocTy TyLoc;
+    
+  PATypeHolder Ty(Type::VoidTy);
+  if (ParseOptionalToken(lltok::kw_thread_local, ThreadLocal) ||
+      ParseOptionalAddrSpace(AddrSpace) ||
+      ParseGlobalType(IsConstant) ||
+      ParseType(Ty, TyLoc))
+    return true;
+  
+  // If the linkage is specified and is external, then no initializer is
+  // present.
+  Constant *Init = 0;
+  if (!HasLinkage || (Linkage != GlobalValue::DLLImportLinkage &&
+                      Linkage != GlobalValue::ExternalWeakLinkage &&
+                      Linkage != GlobalValue::ExternalLinkage)) {
+    if (ParseGlobalValue(Ty, Init))
+      return true;
+  }
+
+  if (isa<FunctionType>(Ty) || Ty == Type::LabelTy)
+    return Error(TyLoc, "invald type for global variable");
+  
+  GlobalVariable *GV = 0;
+
+  // See if the global was forward referenced, if so, use the global.
+  if (!Name.empty() && (GV = M->getGlobalVariable(Name, true))) {
+    if (!ForwardRefVals.erase(Name))
+      return Error(NameLoc, "redefinition of global '@" + Name + "'");
+  } else {
+    std::map<unsigned, std::pair<GlobalValue*, LocTy> >::iterator
+      I = ForwardRefValIDs.find(NumberedVals.size());
+    if (I != ForwardRefValIDs.end()) {
+      GV = cast<GlobalVariable>(I->second.first);
+      ForwardRefValIDs.erase(I);
+    }
+  }
+
+  if (GV == 0) {
+    GV = new GlobalVariable(Ty, false, GlobalValue::ExternalLinkage, 0, Name,
+                            M, false, AddrSpace);
+  } else {
+    if (GV->getType()->getElementType() != Ty)
+      return Error(TyLoc,
+            "forward reference and definition of global have different types");
+    
+    // Move the forward-reference to the correct spot in the module.
+    M->getGlobalList().splice(M->global_end(), M->getGlobalList(), GV);
+  }
+
+  if (Name.empty())
+    NumberedVals.push_back(GV);
+  
+  // Set the parsed properties on the global.
+  if (Init)
+    GV->setInitializer(Init);
+  GV->setConstant(IsConstant);
+  GV->setLinkage((GlobalValue::LinkageTypes)Linkage);
+  GV->setVisibility((GlobalValue::VisibilityTypes)Visibility);
+  GV->setThreadLocal(ThreadLocal);
+  
+  // Parse attributes on the global.
+  while (Lex.getKind() == lltok::comma) {
+    Lex.Lex();
+    
+    if (Lex.getKind() == lltok::kw_section) {
+      Lex.Lex();
+      GV->setSection(Lex.getStrVal());
+      if (ParseToken(lltok::StringConstant, "expected global section string"))
+        return true;
+    } else if (Lex.getKind() == lltok::kw_align) {
+      unsigned Alignment;
+      if (ParseOptionalAlignment(Alignment)) return true;
+      GV->setAlignment(Alignment);
+    } else {
+      TokError("unknown global variable property!");
+    }
+  }
+  
+  return false;
+}
+
+
+//===----------------------------------------------------------------------===//
+// GlobalValue Reference/Resolution Routines.
+//===----------------------------------------------------------------------===//
+
+/// GetGlobalVal - Get a value with the specified name or ID, creating a
+/// forward reference record if needed.  This can return null if the value
+/// exists but does not have the right type.
+GlobalValue *LLParser::GetGlobalVal(const std::string &Name, const Type *Ty,
+                                    LocTy Loc) {
+  const PointerType *PTy = dyn_cast<PointerType>(Ty);
+  if (PTy == 0) {
+    Error(Loc, "global variable reference must have pointer type");
+    return 0;
+  }
+  
+  // Look this name up in the normal function symbol table.
+  GlobalValue *Val =
+    cast_or_null<GlobalValue>(M->getValueSymbolTable().lookup(Name));
+  
+  // If this is a forward reference for the value, see if we already created a
+  // forward ref record.
+  if (Val == 0) {
+    std::map<std::string, std::pair<GlobalValue*, LocTy> >::iterator
+      I = ForwardRefVals.find(Name);
+    if (I != ForwardRefVals.end())
+      Val = I->second.first;
+  }
+  
+  // If we have the value in the symbol table or fwd-ref table, return it.
+  if (Val) {
+    if (Val->getType() == Ty) return Val;
+    Error(Loc, "'@" + Name + "' defined with type '" +
+          Val->getType()->getDescription() + "'");
+    return 0;
+  }
+  
+  // Otherwise, create a new forward reference for this value and remember it.
+  GlobalValue *FwdVal;
+  if (const FunctionType *FT = dyn_cast<FunctionType>(PTy->getElementType()))
+    FwdVal = Function::Create(FT, GlobalValue::ExternalWeakLinkage, Name, M);
+  else
+    FwdVal = new GlobalVariable(PTy->getElementType(), false,
+                                GlobalValue::ExternalWeakLinkage, 0, Name, M);
+  
+  ForwardRefVals[Name] = std::make_pair(FwdVal, Loc);
+  return FwdVal;
+}
+
+GlobalValue *LLParser::GetGlobalVal(unsigned ID, const Type *Ty, LocTy Loc) {
+  const PointerType *PTy = dyn_cast<PointerType>(Ty);
+  if (PTy == 0) {
+    Error(Loc, "global variable reference must have pointer type");
+    return 0;
+  }
+  
+  GlobalValue *Val = ID < NumberedVals.size() ? NumberedVals[ID] : 0;
+  
+  // If this is a forward reference for the value, see if we already created a
+  // forward ref record.
+  if (Val == 0) {
+    std::map<unsigned, std::pair<GlobalValue*, LocTy> >::iterator
+      I = ForwardRefValIDs.find(ID);
+    if (I != ForwardRefValIDs.end())
+      Val = I->second.first;
+  }
+  
+  // If we have the value in the symbol table or fwd-ref table, return it.
+  if (Val) {
+    if (Val->getType() == Ty) return Val;
+    Error(Loc, "'@" + utostr(ID) + "' defined with type '" +
+          Val->getType()->getDescription() + "'");
+    return 0;
+  }
+  
+  // Otherwise, create a new forward reference for this value and remember it.
+  GlobalValue *FwdVal;
+  if (const FunctionType *FT = dyn_cast<FunctionType>(PTy->getElementType()))
+    FwdVal = Function::Create(FT, GlobalValue::ExternalWeakLinkage, "", M);
+  else
+    FwdVal = new GlobalVariable(PTy->getElementType(), false,
+                                GlobalValue::ExternalWeakLinkage, 0, "", M);
+  
+  ForwardRefValIDs[ID] = std::make_pair(FwdVal, Loc);
+  return FwdVal;
+}
+
+
+//===----------------------------------------------------------------------===//
+// Helper Routines.
+//===----------------------------------------------------------------------===//
+
+/// ParseToken - If the current token has the specified kind, eat it and return
+/// success.  Otherwise, emit the specified error and return failure.
+bool LLParser::ParseToken(lltok::Kind T, const char *ErrMsg) {
+  if (Lex.getKind() != T)
+    return TokError(ErrMsg);
+  Lex.Lex();
+  return false;
+}
+
+bool LLParser::ParseUnsigned(unsigned &Val) {
+  if (Lex.getKind() != lltok::APSInt || Lex.getAPSIntVal().isSigned())
+    return TokError("expected integer");
+  uint64_t Val64 = Lex.getAPSIntVal().getLimitedValue(0xFFFFFFFFULL+1);
+  if (Val64 != unsigned(Val64))
+    return TokError("expected 32-bit integer (too large)");
+  Val = Val64;
+  Lex.Lex();
+  return false;
+}
+
+
+/// ParseOptionalAddrSpace
+///   := /*empty*/
+///   := 'addrspace' '(' uint32 ')'
+bool LLParser::ParseOptionalAddrSpace(unsigned &AddrSpace) {
+  AddrSpace = 0;
+  bool HasAddrSpace;
+  ParseOptionalToken(lltok::kw_addrspace, HasAddrSpace);
+  if (!HasAddrSpace)
+    return false;
+  
+  return ParseToken(lltok::lparen, "expected '(' in address space") ||
+         ParseUnsigned(AddrSpace) ||
+         ParseToken(lltok::rparen, "expected ')' in address space");
+}  
+
+/// ParseOptionalAttrs - Parse a potentially empty attribute list.  AttrKind
+/// indicates what kind of attribute list this is: 0: function arg, 1: result,
+/// 2: function attr.
+bool LLParser::ParseOptionalAttrs(unsigned &Attrs, unsigned AttrKind) {
+  Attrs = Attribute::None;
+  LocTy AttrLoc = Lex.getLoc();
+  
+  while (1) {
+    switch (Lex.getKind()) {
+    case lltok::kw_sext:
+    case lltok::kw_zext:
+      // Treat these as signext/zeroext unless they are function attrs.
+      // FIXME: REMOVE THIS IN LLVM 3.0
+      if (AttrKind != 2) {
+        if (Lex.getKind() == lltok::kw_sext)
+          Attrs |= Attribute::SExt;
+        else
+          Attrs |= Attribute::ZExt;
+        break;
+      }
+      // FALL THROUGH.
+    default:  // End of attributes.
+      if (AttrKind != 2 && (Attrs & Attribute::FunctionOnly))
+        return Error(AttrLoc, "invalid use of function-only attribute");
+        
+      if (AttrKind != 0 && (Attrs & Attribute::ParameterOnly))
+        return Error(AttrLoc, "invalid use of parameter-only attribute");
+        
+      return false;
+    case lltok::kw_zeroext:      Attrs |= Attribute::ZExt; break;
+    case lltok::kw_signext:      Attrs |= Attribute::SExt; break;
+    case lltok::kw_inreg:        Attrs |= Attribute::InReg; break;
+    case lltok::kw_sret:         Attrs |= Attribute::StructRet; break;
+    case lltok::kw_noalias:      Attrs |= Attribute::NoAlias; break;
+    case lltok::kw_nocapture:    Attrs |= Attribute::NoCapture; break;
+    case lltok::kw_byval:        Attrs |= Attribute::ByVal; break;
+    case lltok::kw_nest:         Attrs |= Attribute::Nest; break;
+
+    case lltok::kw_noreturn:     Attrs |= Attribute::NoReturn; break;
+    case lltok::kw_nounwind:     Attrs |= Attribute::NoUnwind; break;
+    case lltok::kw_noinline:     Attrs |= Attribute::NoInline; break;
+    case lltok::kw_readnone:     Attrs |= Attribute::ReadNone; break;
+    case lltok::kw_readonly:     Attrs |= Attribute::ReadOnly; break;
+    case lltok::kw_alwaysinline: Attrs |= Attribute::AlwaysInline; break;
+    case lltok::kw_optsize:      Attrs |= Attribute::OptimizeForSize; break;
+    case lltok::kw_ssp:          Attrs |= Attribute::StackProtect; break;
+    case lltok::kw_sspreq:       Attrs |= Attribute::StackProtectReq; break;
+
+        
+    case lltok::kw_align: {
+      unsigned Alignment;
+      if (ParseOptionalAlignment(Alignment))
+        return true;
+      Attrs |= Attribute::constructAlignmentFromInt(Alignment);
+      continue;
+    }
+    }
+    Lex.Lex();
+  }
+}
+
+/// ParseOptionalLinkage
+///   ::= /*empty*/
+///   ::= 'internal'
+///   ::= 'weak'
+///   ::= 'linkonce'
+///   ::= 'appending'
+///   ::= 'dllexport'
+///   ::= 'common'
+///   ::= 'dllimport'
+///   ::= 'extern_weak'
+///   ::= 'external'
+bool LLParser::ParseOptionalLinkage(unsigned &Res, bool &HasLinkage) {
+  HasLinkage = false;
+  switch (Lex.getKind()) {
+  default:                    Res = GlobalValue::ExternalLinkage; return false;
+  case lltok::kw_internal:    Res = GlobalValue::InternalLinkage; break;
+  case lltok::kw_weak:        Res = GlobalValue::WeakLinkage; break;
+  case lltok::kw_linkonce:    Res = GlobalValue::LinkOnceLinkage; break;
+  case lltok::kw_appending:   Res = GlobalValue::AppendingLinkage; break;
+  case lltok::kw_dllexport:   Res = GlobalValue::DLLExportLinkage; break;
+  case lltok::kw_common:      Res = GlobalValue::CommonLinkage; break;
+  case lltok::kw_dllimport:   Res = GlobalValue::DLLImportLinkage; break;
+  case lltok::kw_extern_weak: Res = GlobalValue::ExternalWeakLinkage; break;
+  case lltok::kw_external:    Res = GlobalValue::ExternalLinkage; break;
+  }
+  Lex.Lex();
+  HasLinkage = true;
+  return false;
+}
+
+/// ParseOptionalVisibility
+///   ::= /*empty*/
+///   ::= 'default'
+///   ::= 'hidden'
+///   ::= 'protected'
+/// 
+bool LLParser::ParseOptionalVisibility(unsigned &Res) {
+  switch (Lex.getKind()) {
+  default:                  Res = GlobalValue::DefaultVisibility; return false;
+  case lltok::kw_default:   Res = GlobalValue::DefaultVisibility; break;
+  case lltok::kw_hidden:    Res = GlobalValue::HiddenVisibility; break;
+  case lltok::kw_protected: Res = GlobalValue::ProtectedVisibility; break;
+  }
+  Lex.Lex();
+  return false;
+}
+
+/// ParseOptionalCallingConv
+///   ::= /*empty*/
+///   ::= 'ccc'
+///   ::= 'fastcc'
+///   ::= 'coldcc'
+///   ::= 'x86_stdcallcc'
+///   ::= 'x86_fastcallcc'
+///   ::= 'cc' UINT
+/// 
+bool LLParser::ParseOptionalCallingConv(unsigned &CC) {
+  switch (Lex.getKind()) {
+  default:                       CC = CallingConv::C; return false;
+  case lltok::kw_ccc:            CC = CallingConv::C; break;
+  case lltok::kw_fastcc:         CC = CallingConv::Fast; break;
+  case lltok::kw_coldcc:         CC = CallingConv::Cold; break;
+  case lltok::kw_x86_stdcallcc:  CC = CallingConv::X86_StdCall; break;
+  case lltok::kw_x86_fastcallcc: CC = CallingConv::X86_FastCall; break;
+  case lltok::kw_cc:             Lex.Lex(); return ParseUnsigned(CC);
+  }
+  Lex.Lex();
+  return false;
+}
+
+/// ParseOptionalAlignment
+///   ::= /* empty */
+///   ::= 'align' 4
+bool LLParser::ParseOptionalAlignment(unsigned &Alignment) {
+  Alignment = 0;
+  bool HasAlignment;
+  if (ParseOptionalToken(lltok::kw_align, HasAlignment)) return true;
+  
+  return HasAlignment && ParseUnsigned(Alignment);
+}
+
+/// ParseOptionalCommaAlignment
+///   ::= /* empty */
+///   ::= ',' 'align' 4
+bool LLParser::ParseOptionalCommaAlignment(unsigned &Alignment) {
+  Alignment = 0;
+  bool HasComma;
+  ParseOptionalToken(lltok::comma, HasComma);
+  if (!HasComma)
+    return false;
+  
+  return ParseToken(lltok::kw_align, "expected 'align'") ||
+         ParseUnsigned(Alignment);
+}
+
+/// ParseIndexList
+///    ::=  (',' uint32)+
+bool LLParser::ParseIndexList(SmallVectorImpl<unsigned> &Indices) {
+  if (Lex.getKind() != lltok::comma)
+    return TokError("expected ',' as start of index list");
+  
+  while (Lex.getKind() == lltok::comma) {
+    Lex.Lex();
+    unsigned Idx;
+    if (ParseUnsigned(Idx)) return true;
+    Indices.push_back(Idx);
+  }
+  
+  return false;
+}
+
+//===----------------------------------------------------------------------===//
+// Type Parsing.
+//===----------------------------------------------------------------------===//
+
+/// ParseType - Parse and resolve a full type.
+bool LLParser::ParseType(PATypeHolder &Result) {
+  if (ParseTypeRec(Result)) return true;
+  
+  // Verify no unresolved uprefs.
+  if (!UpRefs.empty())
+    return Error(UpRefs.back().Loc, "invalid unresolved type up reference");
+  //  GEN_ERROR("Invalid upreference in type: " + (*$3)->getDescription());
+  
+  return false;
+}
+
+/// HandleUpRefs - Every time we finish a new layer of types, this function is
+/// called.  It loops through the UpRefs vector, which is a list of the
+/// currently active types.  For each type, if the up-reference is contained in
+/// the newly completed type, we decrement the level count.  When the level
+/// count reaches zero, the up-referenced type is the type that is passed in:
+/// thus we can complete the cycle.
+///
+PATypeHolder LLParser::HandleUpRefs(const Type *ty) {
+  // If Ty isn't abstract, or if there are no up-references in it, then there is
+  // nothing to resolve here.
+  if (!ty->isAbstract() || UpRefs.empty()) return ty;
+  
+  PATypeHolder Ty(ty);
+#if 0
+  errs() << "Type '" << Ty->getDescription()
+         << "' newly formed.  Resolving upreferences.\n"
+         << UpRefs.size() << " upreferences active!\n";
+#endif
+  
+  // If we find any resolvable upreferences (i.e., those whose NestingLevel goes
+  // to zero), we resolve them all together before we resolve them to Ty.  At
+  // the end of the loop, if there is anything to resolve to Ty, it will be in
+  // this variable.
+  OpaqueType *TypeToResolve = 0;
+  
+  for (unsigned i = 0; i != UpRefs.size(); ++i) {
+    // Determine if 'Ty' directly contains this up-references 'LastContainedTy'.
+    bool ContainsType =
+      std::find(Ty->subtype_begin(), Ty->subtype_end(),
+                UpRefs[i].LastContainedTy) != Ty->subtype_end();
+    
+#if 0
+    errs() << "  UR#" << i << " - TypeContains(" << Ty->getDescription() << ", "
+           << UpRefs[i].LastContainedTy->getDescription() << ") = "
+           << (ContainsType ? "true" : "false")
+           << " level=" << UpRefs[i].NestingLevel << "\n";
+#endif
+    if (!ContainsType)
+      continue;
+    
+    // Decrement level of upreference
+    unsigned Level = --UpRefs[i].NestingLevel;
+    UpRefs[i].LastContainedTy = Ty;
+    
+    // If the Up-reference has a non-zero level, it shouldn't be resolved yet.
+    if (Level != 0)
+      continue;
+    
+#if 0
+    errs() << "  * Resolving upreference for " << UpRefs[i].UpRefTy << "\n";
+#endif
+    if (!TypeToResolve)
+      TypeToResolve = UpRefs[i].UpRefTy;
+    else
+      UpRefs[i].UpRefTy->refineAbstractTypeTo(TypeToResolve);
+    UpRefs.erase(UpRefs.begin()+i);     // Remove from upreference list.
+    --i;                                // Do not skip the next element.
+  }
+  
+  if (TypeToResolve)
+    TypeToResolve->refineAbstractTypeTo(Ty);
+  
+  return Ty;
+}
+
+
+/// ParseTypeRec - The recursive function used to process the internal
+/// implementation details of types.
+bool LLParser::ParseTypeRec(PATypeHolder &Result) {
+  switch (Lex.getKind()) {
+  default:
+    return TokError("expected type");
+  case lltok::Type:
+    // TypeRec ::= 'float' | 'void' (etc)
+    Result = Lex.getTyVal();
+    Lex.Lex(); 
+    break;
+  case lltok::kw_opaque:
+    // TypeRec ::= 'opaque'
+    Result = OpaqueType::get();
+    Lex.Lex();
+    break;
+  case lltok::lbrace:
+    // TypeRec ::= '{' ... '}'
+    if (ParseStructType(Result, false))
+      return true;
+    break;
+  case lltok::lsquare:
+    // TypeRec ::= '[' ... ']'
+    Lex.Lex(); // eat the lsquare.
+    if (ParseArrayVectorType(Result, false))
+      return true;
+    break;
+  case lltok::less: // Either vector or packed struct.
+    // TypeRec ::= '<' ... '>'
+    if (Lex.Lex() == lltok::lbrace) {
+      if (ParseStructType(Result, true))
+        return true;
+      if (Lex.getKind() != lltok::greater)
+        return TokError("expected '>' at end of packed struct");
+      Lex.Lex();
+    } else if (ParseArrayVectorType(Result, true))
+      return true;
+    break;
+  case lltok::LocalVar:
+