Move TableGen's parser and entry point into a library

This is the first step towards splitting LLVM and Clang's tblgen executables.

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

11 files changed, 5077 insertions, 1 deletions

diff --git a/lib/CMakeLists.txt b/lib/CMakeLists.txt
index d8a9b7365bf..fb63c63f327 100644
--- a/lib/CMakeLists.txt
+++ b/lib/CMakeLists.txt
@@ -1,4 +1,4 @@
-# `Support' library is added on the top-level CMakeLists.txt
+# `Support' and `TableGen' libraries are added on the top-level CMakeLists.txt
 
 add_subdirectory(VMCore)
 add_subdirectory(CodeGen)
diff --git a/lib/TableGen/CMakeLists.txt b/lib/TableGen/CMakeLists.txt
new file mode 100644
index 00000000000..0db41346911
--- /dev/null
+++ b/lib/TableGen/CMakeLists.txt
@@ -0,0 +1,16 @@
+## FIXME: This only requires RTTI because tblgen uses it.  Fix that.
+set(LLVM_REQUIRES_RTTI 1)
+set(LLVM_REQUIRES_EH 1)
+
+add_llvm_library(LLVMTableGen
+  Error.cpp
+  Main.cpp
+  Record.cpp
+  TableGenBackend.cpp
+  TGLexer.cpp
+  TGParser.cpp
+  )
+
+add_llvm_library_dependencies(LLVMTableGen
+  LLVMSupport
+  )
diff --git a/lib/TableGen/Error.cpp b/lib/TableGen/Error.cpp
new file mode 100644
index 00000000000..5b2cbbfec4b
--- /dev/null
+++ b/lib/TableGen/Error.cpp
@@ -0,0 +1,39 @@
+//===- Error.cpp - tblgen error handling helper routines --------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains error handling helper routines to pretty-print diagnostic
+// messages from tblgen.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/TableGen/Error.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace llvm {
+
+SourceMgr SrcMgr;
+
+void PrintError(SMLoc ErrorLoc, const Twine &Msg) {
+  SrcMgr.PrintMessage(ErrorLoc, Msg, "error");
+}
+
+void PrintError(const char *Loc, const Twine &Msg) {
+  SrcMgr.PrintMessage(SMLoc::getFromPointer(Loc), Msg, "error");
+}
+
+void PrintError(const Twine &Msg) {
+  errs() << "error:" << Msg << "\n";
+}
+
+void PrintError(const TGError &Error) {
+  PrintError(Error.getLoc(), Error.getMessage());
+}
+
+} // end namespace llvm
diff --git a/lib/TableGen/Main.cpp b/lib/TableGen/Main.cpp
new file mode 100644
index 00000000000..01bc55e9898
--- /dev/null
+++ b/lib/TableGen/Main.cpp
@@ -0,0 +1,124 @@
+//===- Main.cpp - Top-Level TableGen implementation -----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// TableGen is a tool which can be used to build up a description of something,
+// then invoke one or more "tablegen backends" to emit information about the
+// description in some predefined format.  In practice, this is used by the LLVM
+// code generators to automate generation of a code generator through a
+// high-level description of the target.
+//
+//===----------------------------------------------------------------------===//
+
+#include "TGParser.h"
+#include "llvm/ADT/OwningPtr.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/ToolOutputFile.h"
+#include "llvm/Support/system_error.h"
+#include "llvm/TableGen/Error.h"
+#include "llvm/TableGen/Record.h"
+#include "llvm/TableGen/TableGenAction.h"
+#include <algorithm>
+#include <cstdio>
+using namespace llvm;
+
+namespace {
+  cl::opt<std::string>
+  OutputFilename("o", cl::desc("Output filename"), cl::value_desc("filename"),
+                 cl::init("-"));
+
+  cl::opt<std::string>
+  DependFilename("d", cl::desc("Dependency filename"), cl::value_desc("filename"),
+                 cl::init(""));
+
+  cl::opt<std::string>
+  InputFilename(cl::Positional, cl::desc("<input file>"), cl::init("-"));
+
+  cl::list<std::string>
+  IncludeDirs("I", cl::desc("Directory of include files"),
+              cl::value_desc("directory"), cl::Prefix);
+}
+
+namespace llvm {
+
+int TableGenMain(char *argv0, TableGenAction &Action) {
+  RecordKeeper Records;
+
+  try {
+    // Parse the input file.
+    OwningPtr<MemoryBuffer> File;
+    if (error_code ec = MemoryBuffer::getFileOrSTDIN(InputFilename.c_str(), File)) {
+      errs() << "Could not open input file '" << InputFilename << "': "
+             << ec.message() <<"\n";
+      return 1;
+    }
+    MemoryBuffer *F = File.take();
+
+    // Tell SrcMgr about this buffer, which is what TGParser will pick up.
+    SrcMgr.AddNewSourceBuffer(F, SMLoc());
+
+    // Record the location of the include directory so that the lexer can find
+    // it later.
+    SrcMgr.setIncludeDirs(IncludeDirs);
+
+    TGParser Parser(SrcMgr, Records);
+
+    if (Parser.ParseFile())
+      return 1;
+
+    std::string Error;
+    tool_output_file Out(OutputFilename.c_str(), Error);
+    if (!Error.empty()) {
+      errs() << argv0 << ": error opening " << OutputFilename
+        << ":" << Error << "\n";
+      return 1;
+    }
+    if (!DependFilename.empty()) {
+      if (OutputFilename == "-") {
+        errs() << argv0 << ": the option -d must be used together with -o\n";
+        return 1;
+      }
+      tool_output_file DepOut(DependFilename.c_str(), Error);
+      if (!Error.empty()) {
+        errs() << argv0 << ": error opening " << DependFilename
+          << ":" << Error << "\n";
+        return 1;
+      }
+      DepOut.os() << OutputFilename << ":";
+      const std::vector<std::string> &Dependencies = Parser.getDependencies();
+      for (std::vector<std::string>::const_iterator I = Dependencies.begin(),
+                                                          E = Dependencies.end();
+           I != E; ++I) {
+        DepOut.os() << " " << (*I);
+      }
+      DepOut.os() << "\n";
+      DepOut.keep();
+    }
+
+    if (Action(Out.os(), Records))
+      return 1;
+
+    // Declare success.
+    Out.keep();
+    return 0;
+
+  } catch (const TGError &Error) {
+    PrintError(Error);
+  } catch (const std::string &Error) {
+    PrintError(Error);
+  } catch (const char *Error) {
+    PrintError(Error);
+  } catch (...) {
+    errs() << argv0 << ": Unknown unexpected exception occurred.\n";
+  }
+
+  return 1;
+}
+
+}
diff --git a/lib/TableGen/Makefile b/lib/TableGen/Makefile
new file mode 100644
index 00000000000..44724389e1d
--- /dev/null
+++ b/lib/TableGen/Makefile
@@ -0,0 +1,18 @@
+##===- lib/TableGen/Makefile -------------------------------*- Makefile -*-===##
+#
+#                     The LLVM Compiler Infrastructure
+#
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+#
+##===----------------------------------------------------------------------===##
+
+LEVEL = ../..
+LIBRARYNAME = LLVMTableGen
+BUILD_ARCHIVE = 1
+
+## FIXME: This only requires RTTI because tblgen uses it.  Fix that.
+REQUIRES_RTTI = 1
+REQUIRES_EH = 1
+
+include $(LEVEL)/Makefile.common
diff --git a/lib/TableGen/Record.cpp b/lib/TableGen/Record.cpp
new file mode 100644
index 00000000000..b4277973b57
--- /dev/null
+++ b/lib/TableGen/Record.cpp
@@ -0,0 +1,2009 @@
+//===- Record.cpp - Record implementation ---------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Implement the tablegen record classes.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/TableGen/Record.h"
+#include "llvm/TableGen/Error.h"
+#include "llvm/Support/DataTypes.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/Format.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/StringMap.h"
+
+using namespace llvm;
+
+//===----------------------------------------------------------------------===//
+//    std::string wrapper for DenseMap purposes
+//===----------------------------------------------------------------------===//
+
+/// TableGenStringKey - This is a wrapper for std::string suitable for
+/// using as a key to a DenseMap.  Because there isn't a particularly
+/// good way to indicate tombstone or empty keys for strings, we want
+/// to wrap std::string to indicate that this is a "special" string
+/// not expected to take on certain values (those of the tombstone and
+/// empty keys).  This makes things a little safer as it clarifies
+/// that DenseMap is really not appropriate for general strings.
+
+class TableGenStringKey {
+public:
+  TableGenStringKey(const std::string &str) : data(str) {}
+  TableGenStringKey(const char *str) : data(str) {}
+
+  const std::string &str() const { return data; }
+  
+private:
+  std::string data;
+};
+
+/// Specialize DenseMapInfo for TableGenStringKey.
+namespace llvm {
+
+template<> struct DenseMapInfo<TableGenStringKey> {
+  static inline TableGenStringKey getEmptyKey() {
+    TableGenStringKey Empty("<<<EMPTY KEY>>>");
+    return Empty;
+  }
+  static inline TableGenStringKey getTombstoneKey() {
+    TableGenStringKey Tombstone("<<<TOMBSTONE KEY>>>");
+    return Tombstone;
+  }
+  static unsigned getHashValue(const TableGenStringKey& Val) {
+    return HashString(Val.str());
+  }
+  static bool isEqual(const TableGenStringKey& LHS,
+                      const TableGenStringKey& RHS) {
+    return LHS.str() == RHS.str();
+  }
+};
+
+}
+
+//===----------------------------------------------------------------------===//
+//    Type implementations
+//===----------------------------------------------------------------------===//
+
+BitRecTy BitRecTy::Shared;
+IntRecTy IntRecTy::Shared;
+StringRecTy StringRecTy::Shared;
+CodeRecTy CodeRecTy::Shared;
+DagRecTy DagRecTy::Shared;
+
+void RecTy::dump() const { print(errs()); }
+
+ListRecTy *RecTy::getListTy() {
+  if (!ListTy)
+    ListTy = new ListRecTy(this);
+  return ListTy;
+}
+
+Init *BitRecTy::convertValue(BitsInit *BI) {
+  if (BI->getNumBits() != 1) return 0; // Only accept if just one bit!
+  return BI->getBit(0);
+}
+
+bool BitRecTy::baseClassOf(const BitsRecTy *RHS) const {
+  return RHS->getNumBits() == 1;
+}
+
+Init *BitRecTy::convertValue(IntInit *II) {
+  int64_t Val = II->getValue();
+  if (Val != 0 && Val != 1) return 0;  // Only accept 0 or 1 for a bit!
+
+  return BitInit::get(Val != 0);
+}
+
+Init *BitRecTy::convertValue(TypedInit *VI) {
+  if (dynamic_cast<BitRecTy*>(VI->getType()))
+    return VI;  // Accept variable if it is already of bit type!
+  return 0;
+}
+
+BitsRecTy *BitsRecTy::get(unsigned Sz) {
+  static std::vector<BitsRecTy*> Shared;
+  if (Sz >= Shared.size())
+    Shared.resize(Sz + 1);
+  BitsRecTy *&Ty = Shared[Sz];
+  if (!Ty)
+    Ty = new BitsRecTy(Sz);
+  return Ty;
+}
+
+std::string BitsRecTy::getAsString() const {
+  return "bits<" + utostr(Size) + ">";
+}
+
+Init *BitsRecTy::convertValue(UnsetInit *UI) {
+  SmallVector<Init *, 16> NewBits(Size);
+
+  for (unsigned i = 0; i != Size; ++i)
+    NewBits[i] = UnsetInit::get();
+
+  return BitsInit::get(NewBits);
+}
+
+Init *BitsRecTy::convertValue(BitInit *UI) {
+  if (Size != 1) return 0;  // Can only convert single bit.
+          return BitsInit::get(UI);
+}
+
+/// canFitInBitfield - Return true if the number of bits is large enough to hold
+/// the integer value.
+static bool canFitInBitfield(int64_t Value, unsigned NumBits) {
+  // For example, with NumBits == 4, we permit Values from [-7 .. 15].
+  return (NumBits >= sizeof(Value) * 8) ||
+         (Value >> NumBits == 0) || (Value >> (NumBits-1) == -1);
+}
+
+/// convertValue from Int initializer to bits type: Split the integer up into the
+/// appropriate bits.
+///
+Init *BitsRecTy::convertValue(IntInit *II) {
+  int64_t Value = II->getValue();
+  // Make sure this bitfield is large enough to hold the integer value.
+  if (!canFitInBitfield(Value, Size))
+    return 0;
+
+  SmallVector<Init *, 16> NewBits(Size);
+
+  for (unsigned i = 0; i != Size; ++i)
+    NewBits[i] = BitInit::get(Value & (1LL << i));
+
+  return BitsInit::get(NewBits);
+}
+
+Init *BitsRecTy::convertValue(BitsInit *BI) {
+  // If the number of bits is right, return it.  Otherwise we need to expand or
+  // truncate.
+  if (BI->getNumBits() == Size) return BI;
+  return 0;
+}
+
+Init *BitsRecTy::convertValue(TypedInit *VI) {
+  if (BitsRecTy *BRT = dynamic_cast<BitsRecTy*>(VI->getType()))
+    if (BRT->Size == Size) {
+      SmallVector<Init *, 16> NewBits(Size);
+ 
+      for (unsigned i = 0; i != Size; ++i)
+        NewBits[i] = VarBitInit::get(VI, i);
+      return BitsInit::get(NewBits);
+    }
+
+  if (Size == 1 && dynamic_cast<BitRecTy*>(VI->getType()))
+    return BitsInit::get(VI);
+
+  if (TernOpInit *Tern = dynamic_cast<TernOpInit*>(VI)) {
+    if (Tern->getOpcode() == TernOpInit::IF) {
+      Init *LHS = Tern->getLHS();
+      Init *MHS = Tern->getMHS();
+      Init *RHS = Tern->getRHS();
+
+      IntInit *MHSi = dynamic_cast<IntInit*>(MHS);
+      IntInit *RHSi = dynamic_cast<IntInit*>(RHS);
+
+      if (MHSi && RHSi) {
+        int64_t MHSVal = MHSi->getValue();
+        int64_t RHSVal = RHSi->getValue();
+
+        if (canFitInBitfield(MHSVal, Size) && canFitInBitfield(RHSVal, Size)) {
+          SmallVector<Init *, 16> NewBits(Size);
+
+          for (unsigned i = 0; i != Size; ++i)
+            NewBits[i] =
+              TernOpInit::get(TernOpInit::IF, LHS,
+                              IntInit::get((MHSVal & (1LL << i)) ? 1 : 0),
+                              IntInit::get((RHSVal & (1LL << i)) ? 1 : 0),
+                              VI->getType());
+
+          return BitsInit::get(NewBits);
+        }
+      } else {
+        BitsInit *MHSbs = dynamic_cast<BitsInit*>(MHS);
+        BitsInit *RHSbs = dynamic_cast<BitsInit*>(RHS);
+
+        if (MHSbs && RHSbs) {
+          SmallVector<Init *, 16> NewBits(Size);
+
+          for (unsigned i = 0; i != Size; ++i)
+            NewBits[i] = TernOpInit::get(TernOpInit::IF, LHS,
+                                         MHSbs->getBit(i),
+                                         RHSbs->getBit(i),
+                                         VI->getType());
+
+          return BitsInit::get(NewBits);
+        }
+      }
+    }
+  }
+
+  return 0;
+}
+
+Init *IntRecTy::convertValue(BitInit *BI) {
+  return IntInit::get(BI->getValue());
+}
+
+Init *IntRecTy::convertValue(BitsInit *BI) {
+  int64_t Result = 0;
+  for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i)
+    if (BitInit *Bit = dynamic_cast<BitInit*>(BI->getBit(i))) {
+      Result |= Bit->getValue() << i;
+    } else {
+      return 0;
+    }
+  return IntInit::get(Result);
+}
+
+Init *IntRecTy::convertValue(TypedInit *TI) {
+  if (TI->getType()->typeIsConvertibleTo(this))
+    return TI;  // Accept variable if already of the right type!
+  return 0;
+}
+
+Init *StringRecTy::convertValue(UnOpInit *BO) {
+  if (BO->getOpcode() == UnOpInit::CAST) {
+    Init *L = BO->getOperand()->convertInitializerTo(this);
+    if (L == 0) return 0;
+    if (L != BO->getOperand())
+      return UnOpInit::get(UnOpInit::CAST, L, new StringRecTy);
+    return BO;
+  }
+
+  return convertValue((TypedInit*)BO);
+}
+
+Init *StringRecTy::convertValue(BinOpInit *BO) {
+  if (BO->getOpcode() == BinOpInit::STRCONCAT) {
+    Init *L = BO->getLHS()->convertInitializerTo(this);
+    Init *R = BO->getRHS()->convertInitializerTo(this);
+    if (L == 0 || R == 0) return 0;
+    if (L != BO->getLHS() || R != BO->getRHS())
+      return BinOpInit::get(BinOpInit::STRCONCAT, L, R, new StringRecTy);
+    return BO;
+  }
+
+  return convertValue((TypedInit*)BO);
+}
+
+
+Init *StringRecTy::convertValue(TypedInit *TI) {
+  if (dynamic_cast<StringRecTy*>(TI->getType()))
+    return TI;  // Accept variable if already of the right type!
+  return 0;
+}
+
+std::string ListRecTy::getAsString() const {
+  return "list<" + Ty->getAsString() + ">";
+}
+
+Init *ListRecTy::convertValue(ListInit *LI) {
+  std::vector<Init*> Elements;
+
+  // Verify that all of the elements of the list are subclasses of the
+  // appropriate class!
+  for (unsigned i = 0, e = LI->getSize(); i != e; ++i)
+    if (Init *CI = LI->getElement(i)->convertInitializerTo(Ty))
+      Elements.push_back(CI);
+    else
+      return 0;
+
+  ListRecTy *LType = dynamic_cast<ListRecTy*>(LI->getType());
+  if (LType == 0) {
+    return 0;
+  }
+
+  return ListInit::get(Elements, this);
+}
+
+Init *ListRecTy::convertValue(TypedInit *TI) {
+  // Ensure that TI is compatible with our class.
+  if (ListRecTy *LRT = dynamic_cast<ListRecTy*>(TI->getType()))
+    if (LRT->getElementType()->typeIsConvertibleTo(getElementType()))
+      return TI;
+  return 0;
+}
+
+Init *CodeRecTy::convertValue(TypedInit *TI) {
+  if (TI->getType()->typeIsConvertibleTo(this))
+    return TI;
+  return 0;
+}
+
+Init *DagRecTy::convertValue(TypedInit *TI) {
+  if (TI->getType()->typeIsConvertibleTo(this))
+    return TI;
+  return 0;
+}
+
+Init *DagRecTy::convertValue(UnOpInit *BO) {
+  if (BO->getOpcode() == UnOpInit::CAST) {
+    Init *L = BO->getOperand()->convertInitializerTo(this);
+    if (L == 0) return 0;
+    if (L != BO->getOperand())
+      return UnOpInit::get(UnOpInit::CAST, L, new DagRecTy);
+    return BO;
+  }
+  return 0;
+}
+
+Init *DagRecTy::convertValue(BinOpInit *BO) {
+  if (BO->getOpcode() == BinOpInit::CONCAT) {
+    Init *L = BO->getLHS()->convertInitializerTo(this);
+    Init *R = BO->getRHS()->convertInitializerTo(this);
+    if (L == 0 || R == 0) return 0;
+    if (L != BO->getLHS() || R != BO->getRHS())
+      return BinOpInit::get(BinOpInit::CONCAT, L, R, new DagRecTy);
+    return BO;
+  }
+  return 0;
+}
+
+RecordRecTy *RecordRecTy::get(Record *R) {
+  return &dynamic_cast<RecordRecTy&>(*R->getDefInit()->getType());
+}
+
+std::string RecordRecTy::getAsString() const {
+  return Rec->getName();
+}
+
+Init *RecordRecTy::convertValue(DefInit *DI) {
+  // Ensure that DI is a subclass of Rec.
+  if (!DI->getDef()->isSubClassOf(Rec))
+    return 0;
+  return DI;
+}
+
+Init *RecordRecTy::convertValue(TypedInit *TI) {
+  // Ensure that TI is compatible with Rec.
+  if (RecordRecTy *RRT = dynamic_cast<RecordRecTy*>(TI->getType()))
+    if (RRT->getRecord()->isSubClassOf(getRecord()) ||
+        RRT->getRecord() == getRecord())
+      return TI;
+  return 0;
+}
+
+bool RecordRecTy::baseClassOf(const RecordRecTy *RHS) const {
+  if (Rec == RHS->getRecord() || RHS->getRecord()->isSubClassOf(Rec))
+    return true;
+
+  const std::vector<Record*> &SC = Rec->getSuperClasses();
+  for (unsigned i = 0, e = SC.size(); i != e; ++i)
+    if (RHS->getRecord()->isSubClassOf(SC[i]))
+      return true;
+
+  return false;
+}
+
+
+/// resolveTypes - Find a common type that T1 and T2 convert to.
+/// Return 0 if no such type exists.
+///
+RecTy *llvm::resolveTypes(RecTy *T1, RecTy *T2) {
+  if (!T1->typeIsConvertibleTo(T2)) {
+    if (!T2->typeIsConvertibleTo(T1)) {
+      // If one is a Record type, check superclasses
+      RecordRecTy *RecTy1 = dynamic_cast<RecordRecTy*>(T1);
+      if (RecTy1) {
+        // See if T2 inherits from a type T1 also inherits from
+        const std::vector<Record *> &T1SuperClasses =
+          RecTy1->getRecord()->getSuperClasses();
+        for(std::vector<Record *>::const_iterator i = T1SuperClasses.begin(),
+              iend = T1SuperClasses.end();
+            i != iend;
+            ++i) {
+          RecordRecTy *SuperRecTy1 = RecordRecTy::get(*i);
+          RecTy *NewType1 = resolveTypes(SuperRecTy1, T2);
+          if (NewType1 != 0) {
+            if (NewType1 != SuperRecTy1) {
+              delete SuperRecTy1;
+            }
+            return NewType1;
+          }
+        }
+      }
+      RecordRecTy *RecTy2 = dynamic_cast<RecordRecTy*>(T2);
+      if (RecTy2) {
+        // See if T1 inherits from a type T2 also inherits from
+        const std::vector<Record *> &T2SuperClasses =
+          RecTy2->getRecord()->getSuperClasses();
+        for (std::vector<Record *>::const_iterator i = T2SuperClasses.begin(),
+              iend = T2SuperClasses.end();
+            i != iend;
+            ++i) {
+          RecordRecTy *SuperRecTy2 = RecordRecTy::get(*i);
+          RecTy *NewType2 = resolveTypes(T1, SuperRecTy2);
+          if (NewType2 != 0) {
+            if (NewType2 != SuperRecTy2) {
+              delete SuperRecTy2;
+            }
+            return NewType2;
+          }
+        }
+      }
+      return 0;
+    }
+    return T2;
+  }
+  return T1;
+}
+
+
+//===----------------------------------------------------------------------===//
+//    Initializer implementations
+//===----------------------------------------------------------------------===//
+
+void Init::dump() const { return print(errs()); }
+
+UnsetInit *UnsetInit::get() {
+  static UnsetInit TheInit;
+  return &TheInit;
+}
+
+BitInit *BitInit::get(bool V) {
+  static BitInit True(true);
+  static BitInit False(false);
+
+  return V ? &True : &False;
+}
+
+static void
+ProfileBitsInit(FoldingSetNodeID &ID, ArrayRef<Init *> Range) {
+  ID.AddInteger(Range.size());
+
+  for (ArrayRef<Init *>::iterator i = Range.begin(),
+         iend = Range.end();
+       i != iend;
+       ++i)
+    ID.AddPointer(*i);
+}
+
+BitsInit *BitsInit::get(ArrayRef<Init *> Range) {
+  typedef FoldingSet<BitsInit> Pool;
+  static Pool ThePool;  
+
+  FoldingSetNodeID ID;
+  ProfileBitsInit(ID, Range);
+
+  void *IP = 0;
+  if (BitsInit *I = ThePool.FindNodeOrInsertPos(ID, IP))
+    return I;
+
+  BitsInit *I = new BitsInit(Range);
+  ThePool.InsertNode(I, IP);
+
+  return I;
+}
+
+void BitsInit::Profile(FoldingSetNodeID &ID) const {
+  ProfileBitsInit(ID, Bits);
+}
+
+Init *
+BitsInit::convertInitializerBitRange(const std::vector<unsigned> &Bits) const {
+  SmallVector<Init *, 16> NewBits(Bits.size());
+
+  for (unsigned i = 0, e = Bits.size(); i != e; ++i) {
+    if (Bits[i] >= getNumBits())
+      return 0;
+    NewBits[i] = getBit(Bits[i]);
+  }
+  return BitsInit::get(NewBits);
+}
+
+std::string BitsInit::getAsString() const {
+  std::string Result = "{ ";
+  for (unsigned i = 0, e = getNumBits(); i != e; ++i) {
+    if (i) Result += ", ";
+    if (Init *Bit = getBit(e-i-1))
+      Result += Bit->getAsString();
+    else
+      Result += "*";
+  }
+  return Result + " }";
+}
+
+// resolveReferences - If there are any field references that refer to fields
+// that have been filled in, we can propagate the values now.
+//
+Init *BitsInit::resolveReferences(Record &R, const RecordVal *RV) const {
+  bool Changed = false;
+  SmallVector<Init *, 16> NewBits(getNumBits());
+
+  for (unsigned i = 0, e = Bits.size(); i != e; ++i) {
+    Init *B;
+    Init *CurBit = getBit(i);
+
+    do {
+      B = CurBit;
+      CurBit = CurBit->resolveReferences(R, RV);
+      Changed |= B != CurBit;
+    } while (B != CurBit);
+    NewBits[i] = CurBit;
+  }
+
+  if (Changed)
+    return BitsInit::get(NewBits);
+
+  return const_cast<BitsInit *>(this);
+}
+
+IntInit *IntInit::get(int64_t V) {
+  typedef DenseMap<int64_t, IntInit *> Pool;
+  static Pool ThePool;
+
+  IntInit *&I = ThePool[V];
+  if (!I) I = new IntInit(V);
+  return I;
+}
+
+std::string IntInit::getAsString() const {
+  return itostr(Value);
+}
+
+Init *
+IntInit::convertInitializerBitRange(const std::vector<unsigned> &Bits) const {
+  SmallVector<Init *, 16> NewBits(Bits.size());
+
+  for (unsigned i = 0, e = Bits.size(); i != e; ++i) {
+    if (Bits[i] >= 64)
+      return 0;
+
+    NewBits[i] = BitInit::get(Value & (INT64_C(1) << Bits[i]));
+  }
+  return BitsInit::get(NewBits);
+}
+
+StringInit *StringInit::get(const std::string &V) {
+  typedef StringMap<StringInit *> Pool;
+  static Pool ThePool;
+
+  StringInit *&I = ThePool[V];
+  if (!I) I = new StringInit(V);
+  return I;
+}
+
+CodeInit *CodeInit::get(const std::string &V) {
+  typedef StringMap<CodeInit *> Pool;
+  static Pool ThePool;
+
+  CodeInit *&I = ThePool[V];
+  if (!I) I = new CodeInit(V);
+  return I;
+}
+
+static void ProfileListInit(FoldingSetNodeID &ID,
+                            ArrayRef<Init *> Range,
+                            RecTy *EltTy) {
+  ID.AddInteger(Range.size());
+  ID.AddPointer(EltTy);
+
+  for (ArrayRef<Init *>::iterator i = Range.begin(),
+         iend = Range.end();
+       i != iend;
+       ++i)
+    ID.AddPointer(*i);
+}
+
+ListInit *ListInit::get(ArrayRef<Init *> Range, RecTy *EltTy) {
+  typedef FoldingSet<ListInit> Pool;
+  static Pool ThePool;
+
+  // Just use the FoldingSetNodeID to compute a hash.  Use a DenseMap
+  // for actual storage.
+  FoldingSetNodeID ID;
+  ProfileListInit(ID, Range, EltTy);
+
+  void *IP = 0;
+  if (ListInit *I = ThePool.FindNodeOrInsertPos(ID, IP))
+    return I;
+
+  ListInit *I = new ListInit(Range, EltTy);
+  ThePool.InsertNode(I, IP);
+  return I;
+}
+
+void ListInit::Profile(FoldingSetNodeID &ID) const {
+  ListRecTy *ListType = dynamic_cast<ListRecTy *>(getType());
+  assert(ListType && "Bad type for ListInit!");
+  RecTy *EltTy = ListType->getElementType();
+
+  ProfileListInit(ID, Values, EltTy);
+}
+
+Init *
+ListInit::convertInitListSlice(const std::vector<unsigned> &Elements) const {
+  std::vector<Init*> Vals;
+  for (unsigned i = 0, e = Elements.size(); i != e; ++i) {
+    if (Elements[i] >= getSize())
+      return 0;
+    Vals.push_back(getElement(Elements[i]));
+  }
+  return ListInit::get(Vals, getType());
+}
+
+Record *ListInit::getElementAsRecord(unsigned i) const {
+  assert(i < Values.size() && "List element index out of range!");
+  DefInit *DI = dynamic_cast<DefInit*>(Values[i]);
+  if (DI == 0) throw "Expected record in list!";
+  return DI->getDef();
+}
+
+Init *ListInit::resolveReferences(Record &R, const RecordVal *RV) const {
+  std::vector<Init*> Resolved;
+  Resolved.reserve(getSize());
+  bool Changed = false;
+
+  for (unsigned i = 0, e = getSize(); i != e; ++i) {
+    Init *E;
+    Init *CurElt = getElement(i);
+
+    do {
+      E = CurElt;
+      CurElt = CurElt->resolveReferences(R, RV);
+      Changed |= E != CurElt;
+    } while (E != CurElt);
+    Resolved.push_back(E);
+  }
+
+  if (Changed)
+    return ListInit::get(Resolved, getType());
+  return const_cast<ListInit *>(this);
+}
+
+Init *ListInit::resolveListElementReference(Record &R, const RecordVal *IRV,
+                                            unsigned Elt) const {
+  if (Elt >= getSize())
+    return 0;  // Out of range reference.
+  Init *E = getElement(Elt);
+  // If the element is set to some value, or if we are resolving a reference
+  // to a specific variable and that variable is explicitly unset, then
+  // replace the VarListElementInit with it.
+  if (IRV || !dynamic_cast<UnsetInit*>(E))
+    return E;
+  return 0;
+}
+
+std::string ListInit::getAsString() const {
+  std::string Result = "[";
+  for (unsigned i = 0, e = Values.size(); i != e; ++i) {
+    if (i) Result += ", ";
+    Result += Values[i]->getAsString();
+  }
+  return Result + "]";
+}
+
+Init *OpInit::resolveBitReference(Record &R, const RecordVal *IRV,
+                                  unsigned Bit) const {
+  Init *Folded = Fold(&R, 0);
+
+  if (Folded != this) {
+    TypedInit *Typed = dynamic_cast<TypedInit *>(Folded);
+    if (Typed) {
+      return Typed->resolveBitReference(R, IRV, Bit);
+    }
+  }
+
+  return 0;
+}
+
+Init *OpInit::resolveListElementReference(Record &R, const RecordVal *IRV,
+                                          unsigned Elt) const {
+  Init *Folded = Fold(&R, 0);
+
+  if (Folded != this) {
+    TypedInit *Typed = dynamic_cast<TypedInit *>(Folded);
+    if (Typed) {
+      return Typed->resolveListElementReference(R, IRV, Elt);
+    }
+  }
+
+  return 0;
+}
+
+UnOpInit *UnOpInit::get(UnaryOp opc, Init *lhs, RecTy *Type) {
+  typedef std::pair<std::pair<unsigned, Init *>, RecTy *> Key;
+
+  typedef DenseMap<Key, UnOpInit *> Pool;
+  static Pool ThePool;  
+
+  Key TheKey(std::make_pair(std::make_pair(opc, lhs), Type));
+
+  UnOpInit *&I = ThePool[TheKey];
+  if (!I) I = new UnOpInit(opc, lhs, Type);
+  return I;
+}
+
+Init *UnOpInit::Fold(Record *CurRec, MultiClass *CurMultiClass) const {
+  switch (getOpcode()) {
+  default: assert(0 && "Unknown unop");
+  case CAST: {
+    if (getType()->getAsString() == "string") {
+      StringInit *LHSs = dynamic_cast<StringInit*>(LHS);
+      if (LHSs) {
+        return LHSs;
+      }
+
+      DefInit *LHSd = dynamic_cast<DefInit*>(LHS);
+      if (LHSd) {
+        return StringInit::get(LHSd->getDef()->getName());
+      }
+    } else {
+      StringInit *LHSs = dynamic_cast<StringInit*>(LHS);
+      if (LHSs) {
+        std::string Name = LHSs->getValue();
+
+        // From TGParser::ParseIDValue
+        if (CurRec) {
+          if (const RecordVal *RV = CurRec->getValue(Name)) {
+            if (RV->getType() != getType())
+              throw "type mismatch in cast";
+            return VarInit::get(Name, RV->getType());
+          }
+
+          std::string TemplateArgName = CurRec->getName()+":"+Name;
+          if (CurRec->isTemplateArg(TemplateArgName)) {
+            const RecordVal *RV = CurRec->getValue(TemplateArgName);
+            assert(RV && "Template arg doesn't exist??");
+
+            if (RV->getType() != getType())
+              throw "type mismatch in cast";
+
+            return VarInit::get(TemplateArgName, RV->getType());
+          }
+        }
+
+        if (CurMultiClass) {
+          std::string MCName = CurMultiClass->Rec.getName()+"::"+Name;
+          if (CurMultiClass->Rec.isTemplateArg(MCName)) {
+            const RecordVal *RV = CurMultiClass->Rec.getValue(MCName);
+            assert(RV && "Template arg doesn't exist??");
+
+            if (RV->getType() != getType())
+              throw "type mismatch in cast";
+
+            return VarInit::get(MCName, RV->getType());
+          }
+        }
+
+        if (Record *D = (CurRec->getRecords()).getDef(Name))
+          return DefInit::get(D);
+
+        throw TGError(CurRec->getLoc(), "Undefined reference:'" + Name + "'\n");
+      }
+    }
+    break;
+  }
+  case HEAD: {
+    ListInit *LHSl = dynamic_cast<ListInit*>(LHS);
+    if (LHSl) {
+      if (LHSl->getSize() == 0) {
+        assert(0 && "Empty list in car");
+        return 0;
+      }
+      return LHSl->getElement(0);
+    }
+    break;
+  }
+  case TAIL: {
+    ListInit *LHSl = dynamic_cast<ListInit*>(LHS);
+    if (LHSl) {
+      if (LHSl->getSize() == 0) {
+        assert(0 && "Empty list in cdr");
+        return 0;
+      }
+      // Note the +1.  We can't just pass the result of getValues()
+      // directly.
+      ArrayRef<Init *>::iterator begin = LHSl->getValues().begin()+1;
+      ArrayRef<Init *>::iterator end   = LHSl->getValues().end();
+      ListInit *Result =
+        ListInit::get(ArrayRef<Init *>(begin, end - begin),
+                      LHSl->getType());
+      return Result;
+    }
+    break;
+  }
+  case EMPTY: {
+    ListInit *LHSl = dynamic_cast<ListInit*>(LHS);
+    if (LHSl) {
+      if (LHSl->getSize() == 0) {
+        return IntInit::get(1);
+      } else {
+        return IntInit::get(0);
+      }
+    }
+    StringInit *LHSs = dynamic_cast<StringInit*>(LHS);
+    if (LHSs) {
+      if (LHSs->getValue().empty()) {
+        return IntInit::get(1);
+      } else {
+        return IntInit::get(0);
+      }
+    }
+
+    break;
+  }
+  }
+  return const_cast<UnOpInit *>(this);
+}
+
+Init *UnOpInit::resolveReferences(Record &R, const RecordVal *RV) const {
+  Init *lhs = LHS->resolveReferences(R, RV);
+
+  if (LHS != lhs)
+    return (UnOpInit::get(getOpcode(), lhs, getType()))->Fold(&R, 0);
+  return Fold(&R, 0);
+}
+
+std::string UnOpInit::getAsString() const {
+  std::string Result;
+  switch (Opc) {
+  case CAST: Result = "!cast<" + getType()->getAsString() + ">"; break;
+  case HEAD: Result = "!head"; break;
+  case TAIL: Result = "!tail"; break;
+  case EMPTY: Result = "!empty"; break;
+  }
+  return Result + "(" + LHS->getAsString() + ")";
+}
+
+BinOpInit *BinOpInit::get(BinaryOp opc, Init *lhs,
+                          Init *rhs, RecTy *Type) {
+  typedef std::pair<
+    std::pair<std::pair<unsigned, Init *>, Init *>,
+    RecTy *
+    > Key;
+
+  typedef DenseMap<Key, BinOpInit *> Pool;
+  static Pool ThePool;  
+
+  Key TheKey(std::make_pair(std::make_pair(std::make_pair(opc, lhs), rhs),
+                            Type));
+
+  BinOpInit *&I = ThePool[TheKey];
+  if (!I) I = new BinOpInit(opc, lhs, rhs, Type);
+  return I;
+}
+
+Init *BinOpInit::Fold(Record *CurRec, MultiClass *CurMultiClass) const {
+  switch (getOpcode()) {
+  default: assert(0 && "Unknown binop");
+  case CONCAT: {
+    DagInit *LHSs = dynamic_cast<DagInit*>(LHS);
+    DagInit *RHSs = dynamic_cast<DagInit*>(RHS);
+    if (LHSs && RHSs) {
+      DefInit *LOp = dynamic_cast<DefInit*>(LHSs->getOperator());
+      DefInit *ROp = dynamic_cast<DefInit*>(RHSs->getOperator());
+      if (LOp == 0 || ROp == 0 || LOp->getDef() != ROp->getDef())
+        throw "Concated Dag operators do not match!";
+      std::vector<Init*> Args;
+      std::vector<std::string> ArgNames;
+      for (unsigned i = 0, e = LHSs->getNumArgs(); i != e; ++i) {
+        Args.push_back(LHSs->getArg(i));
+        ArgNames.push_back(LHSs->getArgName(i));
+      }
+      for (unsigned i = 0, e = RHSs->getNumArgs(); i != e; ++i) {
+        Args.push_back(RHSs->getArg(i));
+        ArgNames.push_back(RHSs->getArgName(i));
+      }
+      return DagInit::get(LHSs->getOperator(), "", Args, ArgNames);
+    }
+    break;
+  }
+  case STRCONCAT: {
+    StringInit *LHSs = dynamic_cast<StringInit*>(LHS);
+    StringInit *RHSs = dynamic_cast<StringInit*>(RHS);
+    if (LHSs && RHSs)
+      return StringInit::get(LHSs->getValue() + RHSs->getValue());
+    break;
+  }
+  case EQ: {
+    // try to fold eq comparison for 'bit' and 'int', otherwise fallback
+    // to string objects.
+    IntInit* L =
+      dynamic_cast<IntInit*>(LHS->convertInitializerTo(IntRecTy::get()));
+    IntInit* R =
+      dynamic_cast<IntInit*>(RHS->convertInitializerTo(IntRecTy::get()));
+
+    if (L && R)
+      return IntInit::get(L->getValue() == R->getValue());
+
+    StringInit *LHSs = dynamic_cast<StringInit*>(LHS);
+    StringInit *RHSs = dynamic_cast<StringInit*>(RHS);
+
+    // Make sure we've resolved
+    if (LHSs && RHSs)
+      return IntInit::get(LHSs->getValue() == RHSs->getValue());
+
+    break;
+  }
+  case SHL:
+  case SRA:
+  case SRL: {
+    IntInit *LHSi = dynamic_cast<IntInit*>(LHS);
+    IntInit *RHSi = dynamic_cast<IntInit*>(RHS);
+    if (LHSi && RHSi) {
+      int64_t LHSv = LHSi->getValue(), RHSv = RHSi->getValue();
+      int64_t Result;
+      switch (getOpcode()) {
+      default: assert(0 && "Bad opcode!");
+      case SHL: Result = LHSv << RHSv; break;
+      case SRA: Result = LHSv >> RHSv; break;
+      case SRL: Result = (uint64_t)LHSv >> (uint64_t)RHSv; break;
+      }
+      return IntInit::get(Result);
+    }
+    break;
+  }
+  }
+  return const_cast<BinOpInit *>(this);
+}
+
+Init *BinOpInit::resolveReferences(Record &R, const RecordVal *RV) const {
+  Init *lhs = LHS->resolveReferences(R, RV);
+  Init *rhs = RHS->resolveReferences(R, RV);
+
+  if (LHS != lhs || RHS != rhs)
+    return (BinOpInit::get(getOpcode(), lhs, rhs, getType()))->Fold(&R, 0);
+  return Fold(&R, 0);
+}
+
+std::string BinOpInit::getAsString() const {
+  std::string Result;
+  switch (Opc) {
+  case CONCAT: Result = "!con"; break;
+  case SHL: Result = "!shl"; break;
+  case SRA: Result = "!sra"; break;
+  case SRL: Result = "!srl"; break;
+  case EQ: Result = "!eq"; break;
+  case STRCONCAT: Result = "!strconcat"; break;
+  }
+  return Result + "(" + LHS->getAsString() + ", " + RHS->getAsString() + ")";
+}
+
+TernOpInit *TernOpInit::get(TernaryOp opc, Init *lhs,
+                                  Init *mhs, Init *rhs,
+                                  RecTy *Type) {
+  typedef std::pair<
+    std::pair<
+      std::pair<std::pair<unsigned, RecTy *>, Init *>,
+      Init *
+      >,
+    Init *
+    > Key;
+
+  typedef DenseMap<Key, TernOpInit *> Pool;
+  static Pool ThePool;
+
+  Key TheKey(std::make_pair(std::make_pair(std::make_pair(std::make_pair(opc,
+                                                                         Type),
+                                                          lhs),
+                                           mhs),
+                            rhs));
+
+  TernOpInit *&I = ThePool[TheKey];
+  if (!I) I = new TernOpInit(opc, lhs, mhs, rhs, Type);
+  return I;
+}
+
+static Init *ForeachHelper(Init *LHS, Init *MHS, Init *RHS, RecTy *Type,
+                           Record *CurRec, MultiClass *CurMultiClass);
+
+static Init *EvaluateOperation(OpInit *RHSo, Init *LHS, Init *Arg,
+                               RecTy *Type, Record *CurRec,
+                               MultiClass *CurMultiClass) {
+  std::vector<Init *> NewOperands;
+
+  TypedInit *TArg = dynamic_cast<TypedInit*>(Arg);
+
+  // If this is a dag, recurse
+  if (TArg && TArg->getType()->getAsString() == "dag") {
+    Init *Result = ForeachHelper(LHS, Arg, RHSo, Type,
+                                 CurRec, CurMultiClass);
+    if (Result != 0) {
+      return Result;
+    } else {
+      return 0;
+    }
+  }
+
+  for (int i = 0; i < RHSo->getNumOperands(); ++i) {
+    OpInit *RHSoo = dynamic_cast<OpInit*>(RHSo->getOperand(i));
+
+    if (RHSoo) {
+      Init *Result = EvaluateOperation(RHSoo, LHS, Arg,
+                                       Type, CurRec, CurMultiClass);
+      if (Result != 0) {
+        NewOperands.push_back(Result);
+      } else {
+        NewOperands.push_back(Arg);
+      }
+    } else if (LHS->getAsString() == RHSo->getOperand(i)->getAsString()) {
+      NewOperands.push_back(Arg);
+    } else {
+      NewOperands.push_back(RHSo->getOperand(i));
+    }
+  }
+
+  // Now run the operator and use its result as the new leaf
+  const OpInit *NewOp = RHSo->clone(NewOperands);
+  Init *NewVal = NewOp->Fold(CurRec, CurMultiClass);
+  if (NewVal != NewOp)
+    return NewVal;
+
+  return 0;
+}
+
+static Init *ForeachHelper(Init *LHS, Init *MHS, Init *RHS, RecTy *Type,
+                           Record *CurRec, MultiClass *CurMultiClass) {
+  DagInit *MHSd = dynamic_cast<DagInit*>(MHS);
+  ListInit *MHSl = dynamic_cast<ListInit*>(MHS);
+
+  DagRecTy *DagType = dynamic_cast<DagRecTy*>(Type);
+  ListRecTy *ListType = dynamic_cast<ListRecTy*>(Type);
+
+  OpInit *RHSo = dynamic_cast<OpInit*>(RHS);
+
+  if (!RHSo) {
+    throw TGError(CurRec->getLoc(), "!foreach requires an operator\n");
+  }
+
+  TypedInit *LHSt = dynamic_cast<TypedInit*>(LHS);
+
+  if (!LHSt) {
+    throw TGError(CurRec->getLoc(), "!foreach requires typed variable\n");
+  }
+
+  if ((MHSd && DagType) || (MHSl && ListType)) {
+    if (MHSd) {
+      Init *Val = MHSd->getOperator();
+      Init *Result = EvaluateOperation(RHSo, LHS, Val,
+                                       Type, CurRec, CurMultiClass);
+      if (Result != 0) {
+        Val = Result;
+      }
+
+      std::vector<std::pair<Init *, std::string> > args;
+      for (unsigned int i = 0; i < MHSd->getNumArgs(); ++i) {
+        Init *Arg;
+        std::string ArgName;
+        Arg = MHSd->getArg(i);
+        ArgName = MHSd->getArgName(i);
+
+        // Process args
+        Init *Result = EvaluateOperation(RHSo, LHS, Arg, Type,
+                                         CurRec, CurMultiClass);
+        if (Result != 0) {
+          Arg = Result;
+        }
+
+        // TODO: Process arg names
+        args.push_back(std::make_pair(Arg, ArgName));
+      }
+
+      return DagInit::get(Val, "", args);
+    }
+    if (MHSl) {
+      std::vector<Init *> NewOperands;
+      std::vector<Init *> NewList(MHSl->begin(), MHSl->end());
+
+      for (std::vector<Init *>::iterator li = NewList.begin(),
+             liend = NewList.end();
+           li != liend;
+           ++li) {
+        Init *Item = *li;
+        NewOperands.clear();
+        for(int i = 0; i < RHSo->getNumOperands(); ++i) {
+          // First, replace the foreach variable with the list item
+          if (LHS->getAsString() == RHSo->getOperand(i)->getAsString()) {
+            NewOperands.push_back(Item);
+          } else {
+            NewOperands.push_back(RHSo->getOperand(i));
+          }
+        }
+
+        // Now run the operator and use its result as the new list item
+        const OpInit *NewOp = RHSo->clone(NewOperands);
+        Init *NewItem = NewOp->Fold(CurRec, CurMultiClass);
+        if (NewItem != NewOp)
+          *li = NewItem;
+      }
+      return ListInit::get(NewList, MHSl->getType());
+    }
+  }
+  return 0;
+}
+
+Init *TernOpInit::Fold(Record *CurRec, MultiClass *CurMultiClass) const {
+  switch (getOpcode()) {
+  default: assert(0 && "Unknown binop");
+  case SUBST: {
+    DefInit *LHSd = dynamic_cast<DefInit*>(LHS);
+    VarInit *LHSv = dynamic_cast<VarInit*>(LHS);
+    StringInit *LHSs = dynamic_cast<StringInit*>(LHS);
+
+    DefInit *MHSd = dynamic_cast<DefInit*>(MHS);
+    VarInit *MHSv = dynamic_cast<VarInit*>(MHS);
+    StringInit *MHSs = dynamic_cast<StringInit*>(MHS);
+
+    DefInit *RHSd = dynamic_cast<DefInit*>(RHS);
+    VarInit *RHSv = dynamic_cast<VarInit*>(RHS);
+    StringInit *RHSs = dynamic_cast<StringInit*>(RHS);
+
+    if ((LHSd && MHSd && RHSd)
+        || (LHSv && MHSv && RHSv)
+        || (LHSs && MHSs && RHSs)) {
+      if (RHSd) {
+        Record *Val = RHSd->getDef();
+        if (LHSd->getAsString() == RHSd->getAsString()) {
+          Val = MHSd->getDef();
+        }
+        return DefInit::get(Val);
+      }
+      if (RHSv) {
+        std::string Val = RHSv->getName();
+        if (LHSv->getAsString() == RHSv->getAsString()) {
+          Val = MHSv->getName();
+        }
+        return VarInit::get(Val, getType());
+      }
+      if (RHSs) {
+        std::string Val = RHSs->getValue();
+
+        std::string::size_type found;
+        std::string::size_type idx = 0;
+        do {
+          found = Val.find(LHSs->getValue(), idx);
+          if (found != std::string::npos) {
+            Val.replace(found, LHSs->getValue().size(), MHSs->getValue());
+          }
+          idx = found +  MHSs->getValue().size();
+        } while (found != std::string::npos);
+
+        return StringInit::get(Val);
+      }
+    }
+    break;
+  }
+
+  case FOREACH: {
+    Init *Result = ForeachHelper(LHS, MHS, RHS, getType(),
+                                 CurRec, CurMultiClass);
+    if (Result != 0) {
+      return Result;
+    }
+    break;
+  }
+
+  case IF: {
+    IntInit *LHSi = dynamic_cast<IntInit*>(LHS);
+    if (Init *I = LHS->convertInitializerTo(IntRecTy::get()))
+      LHSi = dynamic_cast<IntInit*>(I);
+    if (LHSi) {
+      if (LHSi->getValue()) {
+        return MHS;
+      } else {
+        return RHS;
+      }
+    }
+    break;
+  }
+  }
+
+  return const_cast<TernOpInit *>(this);
+}
+
+Init *TernOpInit::resolveReferences(Record &R,
+                                    const RecordVal *RV) const {
+  Init *lhs = LHS->resolveReferences(R, RV);
+
+  if (Opc == IF && lhs != LHS) {
+    IntInit *Value = dynamic_cast<IntInit*>(lhs);
+    if (Init *I = lhs->convertInitializerTo(IntRecTy::get()))
+      Value = dynamic_cast<IntInit*>(I);
+    if (Value != 0) {
+      // Short-circuit
+      if (Value->getValue()) {
+        Init *mhs = MHS->resolveReferences(R, RV);
+        return (TernOpInit::get(getOpcode(), lhs, mhs,
+                                RHS, getType()))->Fold(&R, 0);
+      } else {
+        Init *rhs = RHS->resolveReferences(R, RV);
+        return (TernOpInit::get(getOpcode(), lhs, MHS,
+                                rhs, getType()))->Fold(&R, 0);
+      }
+    }
+  }
+
+  Init *mhs = MHS->resolveReferences(R, RV);
+  Init *rhs = RHS->resolveReferences(R, RV);
+
+  if (LHS != lhs || MHS != mhs || RHS != rhs)
+    return (TernOpInit::get(getOpcode(), lhs, mhs, rhs,
+                            getType()))->Fold(&R, 0);
+  return Fold(&R, 0);
+}
+
+std::string TernOpInit::getAsString() const {
+  std::string Result;
+  switch (Opc) {
+  case SUBST: Result = "!subst"; break;
+  case FOREACH: Result = "!foreach"; break;
+  case IF: Result = "!if"; break;
+ }
+  return Result + "(" + LHS->getAsString() + ", " + MHS->getAsString() + ", "
+    + RHS->getAsString() + ")";
+}
+
+RecTy *TypedInit::getFieldType(const std::string &FieldName) const {
+  RecordRecTy *RecordType = dynamic_cast<RecordRecTy *>(getType());
+  if (RecordType) {
+    RecordVal *Field = RecordType->getRecord()->getValue(FieldName);
+    if (Field) {
+      return Field->getType();
+    }
+  }
+  return 0;
+}
+
+Init *
+TypedInit::convertInitializerBitRange(const std::vector<unsigned> &Bits) const {
+  BitsRecTy *T = dynamic_cast<BitsRecTy*>(getType());
+  if (T == 0) return 0;  // Cannot subscript a non-bits variable.
+  unsigned NumBits = T->getNumBits();
+
+  SmallVector<Init *, 16> NewBits(Bits.size());
+  for (unsigned i = 0, e = Bits.size(); i != e; ++i) {
+    if (Bits[i] >= NumBits)
+      return 0;
+
+    NewBits[i] = VarBitInit::get(const_cast<TypedInit *>(this), Bits[i]);
+  }
+  return BitsInit::get(NewBits);
+}
+
+Init *
+TypedInit::convertInitListSlice(const std::vector<unsigned> &Elements) const {
+  ListRecTy *T = dynamic_cast<ListRecTy*>(getType());
+  if (T == 0) return 0;  // Cannot subscript a non-list variable.
+
+  if (Elements.size() == 1)
+    return VarListElementInit::get(const_cast<TypedInit *>(this), Elements[0]);
+
+  std::vector<Init*> ListInits;
+  ListInits.reserve(Elements.size());
+  for (unsigned i = 0, e = Elements.size(); i != e; ++i)
+    ListInits.push_back(VarListElementInit::get(const_cast<TypedInit *>(this),
+                                                Elements[i]));
+  return ListInit::get(ListInits, T);
+}
+
+
+VarInit *VarInit::get(const std::string &VN, RecTy *T) {
+  typedef std::pair<RecTy *, TableGenStringKey> Key;
+  typedef DenseMap<Key, VarInit *> Pool;
+  static Pool ThePool;
+
+  Key TheKey(std::make_pair(T, VN));
+
+  VarInit *&I = ThePool[TheKey];
+  if (!I) I = new VarInit(VN, T);
+  return I;
+}
+
+Init *VarInit::resolveBitReference(Record &R, const RecordVal *IRV,
+                                   unsigned Bit) const {
+  if (R.isTemplateArg(getName())) return 0;
+  if (IRV && IRV->getName() != getName()) return 0;
+
+  RecordVal *RV = R.getValue(getName());
+  assert(RV && "Reference to a non-existent variable?");
+  assert(dynamic_cast<BitsInit*>(RV->getValue()));
+  BitsInit *BI = (BitsInit*)RV->getValue();
+
+  assert(Bit < BI->getNumBits() && "Bit reference out of range!");
+  Init *B = BI->getBit(Bit);
+
+  // If the bit is set to some value, or if we are resolving a reference to a
+  // specific variable and that variable is explicitly unset, then replace the
+  // VarBitInit with it.
+  if (IRV || !dynamic_cast<UnsetInit*>(B))
+    return B;
+  return 0;
+}
+
+Init *VarInit::resolveListElementReference(Record &R,
+                                           const RecordVal *IRV,
+                                           unsigned Elt) const {
+  if (R.isTemplateArg(getName())) return 0;
+  if (IRV && IRV->getName() != getName()) return 0;
+
+  RecordVal *RV = R.getValue(getName());
+  assert(RV && "Reference to a non-existent variable?");
+  ListInit *LI = dynamic_cast<ListInit*>(RV->getValue());
+  if (!LI) {
+    VarInit *VI = dynamic_cast<VarInit*>(RV->getValue());
+    assert(VI && "Invalid list element!");
+    return VarListElementInit::get(VI, Elt);
+  }
+
+  if (Elt >= LI->getSize())
+    return 0;  // Out of range reference.
+  Init *E = LI->getElement(Elt);
+  // If the element is set to some value, or if we are resolving a reference
+  // to a specific variable and that variable is explicitly unset, then
+  // replace the VarListElementInit with it.
+  if (IRV || !dynamic_cast<UnsetInit*>(E))
+    return E;
+  return 0;
+}
+
+
+RecTy *VarInit::getFieldType(const std::string &FieldName) const {
+  if (RecordRecTy *RTy = dynamic_cast<RecordRecTy*>(getType()))
+    if (const RecordVal *RV = RTy->getRecord()->getValue(FieldName))
+      return RV->getType();
+  return 0;
+}
+
+Init *VarInit::getFieldInit(Record &R, const RecordVal *RV,
+                            const std::string &FieldName) const {
+  if (dynamic_cast<RecordRecTy*>(getType()))
+    if (const RecordVal *Val = R.getValue(VarName)) {
+      if (RV != Val && (RV || dynamic_cast<UnsetInit*>(Val->getValue())))
+        return 0;
+      Init *TheInit = Val->getValue();
+      assert(TheInit != this && "Infinite loop detected!");
+      if (Init *I = TheInit->getFieldInit(R, RV, FieldName))
+        return I;
+      else
+        return 0;
+    }
+  return 0;
+}
+
+/// resolveReferences - This method is used by classes that refer to other
+/// variables which may not be defined at the time the expression is formed.
+/// If a value is set for the variable later, this method will be called on
+/// users of the value to allow the value to propagate out.
+///
+Init *VarInit::resolveReferences(Record &R, const RecordVal *RV) const {
+  if (RecordVal *Val = R.getValue(VarName))
+    if (RV == Val || (RV == 0 && !dynamic_cast<UnsetInit*>(Val->getValue())))
+      return Val->getValue();
+  return const_cast<VarInit *>(this);
+}
+
+VarBitInit *VarBitInit::get(TypedInit *T, unsigned B) {
+  typedef std::pair<TypedInit *, unsigned> Key;
+  typedef DenseMap<Key, VarBitInit *> Pool;
+
+  static Pool ThePool;
+
+  Key TheKey(std::make_pair(T, B));
+
+  VarBitInit *&I = ThePool[TheKey];
+  if (!I) I = new VarBitInit(T, B);
+  return I;
+}
+
+std::string VarBitInit::getAsString() const {
+   return TI->getAsString() + "{" + utostr(Bit) + "}";
+}
+
+Init *VarBitInit::resolveReferences(Record &R, const RecordVal *RV) const {
+  if (Init *I = getVariable()->resolveBitReference(R, RV, getBitNum()))
+    return I;
+  return const_cast<VarBitInit *>(this);
+}
+
+VarListElementInit *VarListElementInit::get(TypedInit *T,
+                                            unsigned E) {
+  typedef std::pair<TypedInit *, unsigned> Key;
+  typedef DenseMap<Key, VarListElementInit *> Pool;
+
+  static Pool ThePool;
+
+  Key TheKey(std::make_pair(T, E));
+
+  VarListElementInit *&I = ThePool[TheKey];
+  if (!I) I = new VarListElementInit(T, E);
+  return I;
+}
+
+std::string VarListElementInit::getAsString() const {
+  return TI->getAsString() + "[" + utostr(Element) + "]";
+}
+
+Init *
+VarListElementInit::resolveReferences(Record &R, const RecordVal *RV) const {
+  if (Init *I = getVariable()->resolveListElementReference(R, RV,
+                                                           getElementNum()))
+    return I;
+  return const_cast<VarListElementInit *>(this);
+}
+
+Init *VarListElementInit::resolveBitReference(Record &R, const RecordVal *RV,
+                                              unsigned Bit) const {
+  // FIXME: This should be implemented, to support references like:
+  // bit B = AA[0]{1};
+  return 0;
+}
+
+Init *VarListElementInit:: resolveListElementReference(Record &R,
+                                                       const RecordVal *RV,
+                                                       unsigned Elt) const {
+  Init *Result = TI->resolveListElementReference(R, RV, Element);
+  
+  if (Result) {
+    TypedInit *TInit = dynamic_cast<TypedInit *>(Result);
+    if (TInit) {
+      return TInit->resolveListElementReference(R, RV, Elt);
+    }
+    return Result;
+  }
+ 
+  return 0;
+}
+
+DefInit *DefInit::get(Record *R) {
+  return R->getDefInit();
+}
+
+RecTy *DefInit::getFieldType(const std::string &FieldName) const {
+  if (const RecordVal *RV = Def->getValue(FieldName))
+    return RV->getType();
+  return 0;
+}
+
+Init *DefInit::getFieldInit(Record &R, const RecordVal *RV,
+                            const std::string &FieldName) const {
+  return Def->getValue(FieldName)->getValue();
+}
+
+
+std::string DefInit::getAsString() const {
+  return Def->getName();
+}
+
+FieldInit *FieldInit::get(Init *R, const std::string &FN) {
+  typedef std::pair<Init *, TableGenStringKey> Key;
+  typedef DenseMap<Key, FieldInit *> Pool;
+  static Pool ThePool;  
+
+  Key TheKey(std::make_pair(R, FN));
+
+  FieldInit *&I = ThePool[TheKey];
+  if (!I) I = new FieldInit(R, FN);
+  return I;
+}
+
+Init *FieldInit::resolveBitReference(Record &R, const RecordVal *RV,
+                                     unsigned Bit) const {
+  if (Init *BitsVal = Rec->getFieldInit(R, RV, FieldName))
+    if (BitsInit *BI = dynamic_cast<BitsInit*>(BitsVal)) {
+      assert(Bit < BI->getNumBits() && "Bit reference out of range!");
+      Init *B = BI->getBit(Bit);
+
+      if (dynamic_cast<BitInit*>(B))  // If the bit is set.
+        return B;                     // Replace the VarBitInit with it.
+    }
+  return 0;
+}
+
+Init *FieldInit::resolveListElementReference(Record &R, const RecordVal *RV,
+                                             unsigned Elt) const {
+  if (Init *ListVal = Rec->getFieldInit(R, RV, FieldName))
+    if (ListInit *LI = dynamic_cast<ListInit*>(ListVal)) {
+      if (Elt >= LI->getSize()) return 0;
+      Init *E = LI->getElement(Elt);
+
+      // If the element is set to some value, or if we are resolving a
+      // reference to a specific variable and that variable is explicitly
+      // unset, then replace the VarListElementInit with it.
+      if (RV || !dynamic_cast<UnsetInit*>(E))
+        return E;
+    }
+  return 0;
+}
+
+Init *FieldInit::resolveReferences(Record &R, const RecordVal *RV) const {
+  Init *NewRec = RV ? Rec->resolveReferences(R, RV) : Rec;
+
+  Init *BitsVal = NewRec->getFieldInit(R, RV, FieldName);
+  if (BitsVal) {
+    Init *BVR = BitsVal->resolveReferences(R, RV);
+    return BVR->isComplete() ? BVR : const_cast<FieldInit *>(this);
+  }
+
+  if (NewRec != Rec) {
+    return FieldInit::get(NewRec, FieldName);
+  }
+  return const_cast<FieldInit *>(this);
+}
+
+void ProfileDagInit(FoldingSetNodeID &ID,
+                    Init *V,
+                    const std::string &VN,
+                    ArrayRef<Init *> ArgRange,
+                    ArrayRef<std::string> NameRange) {
+  ID.AddPointer(V);
+  ID.AddString(VN);
+
+  ArrayRef<Init *>::iterator Arg  = ArgRange.begin();
+  ArrayRef<std::string>::iterator  Name = NameRange.begin();
+  while (Arg != ArgRange.end()) {
+    assert(Name != NameRange.end() && "Arg name underflow!");
+    ID.AddPointer(*Arg++);
+    ID.AddString(*Name++);
+  }
+  assert(Name == NameRange.end() && "Arg name overflow!");
+}
+
+DagInit *
+DagInit::get(Init *V, const std::string &VN,
+             ArrayRef<Init *> ArgRange,
+             ArrayRef<std::string> NameRange) {
+  typedef FoldingSet<DagInit> Pool;
+  static Pool ThePool;  
+
+  FoldingSetNodeID ID;
+  ProfileDagInit(ID, V, VN, ArgRange, NameRange);
+
+  void *IP = 0;
+  if (DagInit *I = ThePool.FindNodeOrInsertPos(ID, IP))
+    return I;
+
+  DagInit *I = new DagInit(V, VN, ArgRange, NameRange);
+  ThePool.InsertNode(I, IP);
+
+  return I;
+}
+
+DagInit *
+DagInit::get(Init *V, const std::string &VN,
+             const std::vector<std::pair<Init*, std::string> > &args) {
+  typedef std::pair<Init*, std::string> PairType;
+
+  std::vector<Init *> Args;
+  std::vector<std::string> Names;
+
+  for (std::vector<PairType>::const_iterator i = args.begin(),
+         iend = args.end();
+       i != iend;
+       ++i) {
+    Args.push_back(i->first);
+    Names.push_back(i->second);
+  }
+
+  return DagInit::get(V, VN, Args, Names);
+}
+
+void DagInit::Profile(FoldingSetNodeID &ID) const {
+  ProfileDagInit(ID, Val, ValName, Args, ArgNames);
+}
+
+Init *DagInit::resolveReferences(Record &R, const RecordVal *RV) const {
+  std::vector<Init*> NewArgs;
+  for (unsigned i = 0, e = Args.size(); i != e; ++i)
+    NewArgs.push_back(Args[i]->resolveReferences(R, RV));
+
+  Init *Op = Val->resolveReferences(R, RV);
+
+  if (Args != NewArgs || Op != Val)
+    return DagInit::get(Op, ValName, NewArgs, ArgNames);
+
+  return const_cast<DagInit *>(this);
+}
+
+
+std::string DagInit::getAsString() const {
+  std::string Result = "(" + Val->getAsString();
+  if (!ValName.empty())
+    Result += ":" + ValName;
+  if (Args.size()) {
+    Result += " " + Args[0]->getAsString();
+    if (!ArgNames[0].empty()) Result += ":$" + ArgNames[0];
+    for (unsigned i = 1, e = Args.size(); i != e; ++i) {
+      Result += ", " + Args[i]->getAsString();
+      if (!ArgNames[i].empty()) Result += ":$" + ArgNames[i];
+    }
+  }
+  return Result + ")";
+}
+
+
+//===----------------------------------------------------------------------===//
+//    Other implementations
+//===----------------------------------------------------------------------===//
+
+RecordVal::RecordVal(Init *N, RecTy *T, unsigned P)
+  : Name(N), Ty(T), Prefix(P) {
+  Value = Ty->convertValue(UnsetInit::get());
+  assert(Value && "Cannot create unset value for current type!");
+}
+
+RecordVal::RecordVal(const std::string &N, RecTy *T, unsigned P)
+  : Name(StringInit::get(N)), Ty(T), Prefix(P) {
+  Value = Ty->convertValue(UnsetInit::get());
+  assert(Value && "Cannot create unset value for current type!");
+}
+
+const std::string &RecordVal::getName() const {
+  StringInit *NameString = dynamic_cast<StringInit *>(Name);
+  assert(NameString && "RecordVal name is not a string!");
+  return NameString->getValue();
+}
+
+void RecordVal::dump() const { errs() << *this; }
+
+void RecordVal::print(raw_ostream &OS, bool PrintSem) const {
+  if (getPrefix()) OS << "field ";
+  OS << *getType() << " " << getName();
+
+  if (getValue())
+    OS << " = " << *getValue();
+
+  if (PrintSem) OS << ";\n";
+}
+
+unsigned Record::LastID = 0;
+
+void Record::checkName() {
+  // Ensure the record name has string type.
+  const TypedInit *TypedName = dynamic_cast<const TypedInit *>(Name);
+  assert(TypedName && "Record name is not typed!");
+  RecTy *Type = TypedName->getType();
+  if (dynamic_cast<StringRecTy *>(Type) == 0) {
+    llvm_unreachable("Record name is not a string!");
+  }
+}
+
+DefInit *Record::getDefInit() {
+  if (!TheInit)
+    TheInit = new DefInit(this, new RecordRecTy(this));
+  return TheInit;
+}
+
+const std::string &Record::getName() const {
+  const StringInit *NameString =
+    dynamic_cast<const StringInit *>(Name);
+  assert(NameString && "Record name is not a string!");
+  return NameString->getValue();
+}
+
+void Record::setName(Init *NewName) {
+  if (TrackedRecords.getDef(Name->getAsUnquotedString()) == this) {
+    TrackedRecords.removeDef(Name->getAsUnquotedString());
+    Name = NewName;
+    TrackedRecords.addDef(this);
+  } else {
+    TrackedRecords.removeClass(Name->getAsUnquotedString());
+    Name = NewName;
+    TrackedRecords.addClass(this);
+  }
+  checkName();
+  // Since the Init for the name was changed, see if we can resolve
+  // any of it using members of the Record.
+  Init *ComputedName = Name->resolveReferences(*this, 0);
+  if (ComputedName != Name) {
+    setName(ComputedName);
+  }
+  // DO NOT resolve record values to the name at this point because
+  // there might be default values for arguments of this def.  Those
+  // arguments might not have been resolved yet so we don't want to
+  // prematurely assume values for those arguments were not passed to
+  // this def.
+  //
+  // Nonetheless, it may be that some of this Record's values
+  // reference the record name.  Indeed, the reason for having the
+  // record name be an Init is to provide this flexibility.  The extra
+  // resolve steps after completely instantiating defs takes care of
+  // this.  See TGParser::ParseDef and TGParser::ParseDefm.
+}
+
+void Record::setName(const std::string &Name) {
+  setName(StringInit::get(Name));
+}
+
+/// resolveReferencesTo - If anything in this record refers to RV, replace the
+/// reference to RV with the RHS of RV.  If RV is null, we resolve all possible
+/// references.
+void Record::resolveReferencesTo(const RecordVal *RV) {
+  for (unsigned i = 0, e = Values.size(); i != e; ++i) {
+    if (Init *V = Values[i].getValue())
+      Values[i].setValue(V->resolveReferences(*this, RV));
+  }
+}
+
+void Record::dump() const { errs() << *this; }
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const Record &R) {
+  OS << R.getName();
+
+  const std::vector<std::string> &TArgs = R.getTemplateArgs();
+  if (!TArgs.empty()) {
+    OS << "<";
+    for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
+      if (i) OS << ", ";
+      const RecordVal *RV = R.getValue(TArgs[i]);
+      assert(RV && "Template argument record not found??");
+      RV->print(OS, false);
+    }
+    OS << ">";
+  }
+
+  OS << " {";
+  const std::vector<Record*> &SC = R.getSuperClasses();
+  if (!SC.empty()) {
+    OS << "\t//";
+    for (unsigned i = 0, e = SC.size(); i != e; ++i)
+      OS << " " << SC[i]->getName();
+  }
+  OS << "\n";
+
+  const std::vector<RecordVal> &Vals = R.getValues();
+  for (unsigned i = 0, e = Vals.size(); i != e; ++i)
+    if (Vals[i].getPrefix() && !R.isTemplateArg(Vals[i].getName()))
+      OS << Vals[i];
+  for (unsigned i = 0, e = Vals.size(); i != e; ++i)
+    if (!Vals[i].getPrefix() && !R.isTemplateArg(Vals[i].getName()))
+      OS << Vals[i];
+
+  return OS << "}\n";
+}
+
+/// getValueInit - Return the initializer for a value with the specified name,
+/// or throw an exception if the field does not exist.
+///
+Init *Record::getValueInit(StringRef FieldName) const {
+  const RecordVal *R = getValue(FieldName);
+  if (R == 0 || R->getValue() == 0)
+    throw "Record `" + getName() + "' does not have a field named `" +
+      FieldName.str() + "'!\n";
+  return R->getValue();
+}
+
+
+/// getValueAsString - This method looks up the specified field and returns its
+/// value as a string, throwing an exception if the field does not exist or if
+/// the value is not a string.
+///
+std::string Record::getValueAsString(StringRef FieldName) const {
+  const RecordVal *R = getValue(FieldName);
+  if (R == 0 || R->getValue() == 0)
+    throw "Record `" + getName() + "' does not have a field named `" +
+          FieldName.str() + "'!\n";
+
+  if (StringInit *SI = dynamic_cast<StringInit*>(R->getValue()))
+    return SI->getValue();
+  throw "Record `" + getName() + "', field `" + FieldName.str() +
+        "' does not have a string initializer!";
+}
+
+/// getValueAsBitsInit - This method looks up the specified field and returns
+/// its value as a BitsInit, throwing an exception if the field does not exist
+/// or if the value is not the right type.
+///
+BitsInit *Record::getValueAsBitsInit(StringRef FieldName) const {
+  const RecordVal *R = getValue(FieldName);
+  if (R == 0 || R->getValue() == 0)
+    throw "Record `" + getName() + "' does not have a field named `" +
+          FieldName.str() + "'!\n";
+
+  if (BitsInit *BI = dynamic_cast<BitsInit*>(R->getValue()))
+    return BI;
+  throw "Record `" + getName() + "', field `" + FieldName.str() +
+        "' does not have a BitsInit initializer!";
+}
+
+/// getValueAsListInit - This method looks up the specified field and returns
+/// its value as a ListInit, throwing an exception if the field does not exist
+/// or if the value is not the right type.
+///
+ListInit *Record::getValueAsListInit(StringRef FieldName) const {
+  const RecordVal *R = getValue(FieldName);
+  if (R == 0 || R->getValue() == 0)
+    throw "Record `" + getName() + "' does not have a field named `" +
+          FieldName.str() + "'!\n";
+
+  if (ListInit *LI = dynamic_cast<ListInit*>(R->getValue()))
+    return LI;
+  throw "Record `" + getName() + "', field `" + FieldName.str() +
+        "' does not have a list initializer!";
+}
+
+/// getValueAsListOfDefs - This method looks up the specified field and returns
+/// its value as a vector of records, throwing an exception if the field does
+/// not exist or if the value is not the right type.
+///
+std::vector<Record*>
+Record::getValueAsListOfDefs(StringRef FieldName) const {
+  ListInit *List = getValueAsListInit(FieldName);
+  std::vector<Record*> Defs;
+  for (unsigned i = 0; i < List->getSize(); i++) {
+    if (DefInit *DI = dynamic_cast<DefInit*>(List->getElement(i))) {
+      Defs.push_back(DI->getDef());
+    } else {
+      throw "Record `" + getName() + "', field `" + FieldName.str() +
+            "' list is not entirely DefInit!";
+    }
+  }
+  return Defs;
+}
+
+/// getValueAsInt - This method looks up the specified field and returns its
+/// value as an int64_t, throwing an exception if the field does not exist or if
+/// the value is not the right type.
+///
+int64_t Record::getValueAsInt(StringRef FieldName) const {
+  const RecordVal *R = getValue(FieldName);
+  if (R == 0 || R->getValue() == 0)
+    throw "Record `" + getName() + "' does not have a field named `" +
+          FieldName.str() + "'!\n";
+
+  if (IntInit *II = dynamic_cast<IntInit*>(R->getValue()))
+    return II->getValue();
+  throw "Record `" + getName() + "', field `" + FieldName.str() +
+        "' does not have an int initializer!";
+}
+
+/// getValueAsListOfInts - This method looks up the specified field and returns
+/// its value as a vector of integers, throwing an exception if the field does
+/// not exist or if the value is not the right type.
+///
+std::vector<int64_t>
+Record::getValueAsListOfInts(StringRef FieldName) const {
+  ListInit *List = getValueAsListInit(FieldName);
+  std::vector<int64_t> Ints;
+  for (unsigned i = 0; i < List->getSize(); i++) {
+    if (IntInit *II = dynamic_cast<IntInit*>(List->getElement(i))) {
+      Ints.push_back(II->getValue());
+    } else {
+      throw "Record `" + getName() + "', field `" + FieldName.str() +
+            "' does not have a list of ints initializer!";
+    }
+  }
+  return Ints;
+}
+
+/// getValueAsListOfStrings - This method looks up the specified field and
+/// returns its value as a vector of strings, throwing an exception if the
+/// field does not exist or if the value is not the right type.
+///
+std::vector<std::string>
+Record::getValueAsListOfStrings(StringRef FieldName) const {
+  ListInit *List = getValueAsListInit(FieldName);
+  std::vector<std::string> Strings;
+  for (unsigned i = 0; i < List->getSize(); i++) {
+    if (StringInit *II = dynamic_cast<StringInit*>(List->getElement(i))) {
+      Strings.push_back(II->getValue());
+    } else {
+      throw "Record `" + getName() + "', field `" + FieldName.str() +
+            "' does not have a list of strings initializer!";
+    }
+  }
+  return Strings;
+}
+
+/// getValueAsDef - This method looks up the specified field and returns its
+/// value as a Record, throwing an exception if the field does not exist or if
+/// the value is not the right type.
+///
+Record *Record::getValueAsDef(StringRef FieldName) const {
+  const RecordVal *R = getValue(FieldName);
+  if (R == 0 || R->getValue() == 0)
+    throw "Record `" + getName() + "' does not have a field named `" +
+      FieldName.str() + "'!\n";
+
+  if (DefInit *DI = dynamic_cast<DefInit*>(R->getValue()))
+    return DI->getDef();
+  throw "Record `" + getName() + "', field `" + FieldName.str() +
+        "' does not have a def initializer!";
+}
+
+/// getValueAsBit - This method looks up the specified field and returns its
+/// value as a bit, throwing an exception if the field does not exist or if
+/// the value is not the right type.
+///
+bool Record::getValueAsBit(StringRef FieldName) const {
+  const RecordVal *R = getValue(FieldName);
+  if (R == 0 || R->getValue() == 0)
+    throw "Record `" + getName() + "' does not have a field named `" +
+      FieldName.str() + "'!\n";
+
+  if (BitInit *BI = dynamic_cast<BitInit*>(R->getValue()))
+    return BI->getValue();
+  throw "Record `" + getName() + "', field `" + FieldName.str() +
+        "' does not have a bit initializer!";
+}
+
+/// getValueAsDag - This method looks up the specified field and returns its
+/// value as an Dag, throwing an exception if the field does not exist or if
+/// the value is not the right type.
+///
+DagInit *Record::getValueAsDag(StringRef FieldName) const {
+  const RecordVal *R = getValue(FieldName);
+  if (R == 0 || R->getValue() == 0)
+    throw "Record `" + getName() + "' does not have a field named `" +
+      FieldName.str() + "'!\n";
+
+  if (DagInit *DI = dynamic_cast<DagInit*>(R->getValue()))
+    return DI;
+  throw "Record `" + getName() + "', field `" + FieldName.str() +
+        "' does not have a dag initializer!";
+}
+
+std::string Record::getValueAsCode(StringRef FieldName) const {
+  const RecordVal *R = getValue(FieldName);
+  if (R == 0 || R->getValue() == 0)
+    throw "Record `" + getName() + "' does not have a field named `" +
+      FieldName.str() + "'!\n";
+
+  if (CodeInit *CI = dynamic_cast<CodeInit*>(R->getValue()))
+    return CI->getValue();
+  throw "Record `" + getName() + "', field `" + FieldName.str() +
+    "' does not have a code initializer!";
+}
+
+
+void MultiClass::dump() const {
+  errs() << "Record:\n";
+  Rec.dump();
+
+  errs() << "Defs:\n";
+  for (RecordVector::const_iterator r = DefPrototypes.begin(),
+         rend = DefPrototypes.end();
+       r != rend;
+       ++r) {
+    (*r)->dump();
+  }
+}
+
+
+void RecordKeeper::dump() const { errs() << *this; }
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const RecordKeeper &RK) {
+  OS << "------------- Classes -----------------\n";
+  const std::map<std::string, Record*> &Classes = RK.getClasses();
+  for (std::map<std::string, Record*>::const_iterator I = Classes.begin(),
+         E = Classes.end(); I != E; ++I)
+    OS << "class " << *I->second;
+
+  OS << "------------- Defs -----------------\n";
+  const std::map<std::string, Record*> &Defs = RK.getDefs();
+  for (std::map<std::string, Record*>::const_iterator I = Defs.begin(),
+         E = Defs.end(); I != E; ++I)
+    OS << "def " << *I->second;
+  return OS;
+}
+
+
+/// getAllDerivedDefinitions - This method returns all concrete definitions
+/// that derive from the specified class name.  If a class with the specified
+/// name does not exist, an error is printed and true is returned.
+std::vector<Record*>
+RecordKeeper::getAllDerivedDefinitions(const std::string &ClassName) const {
+  Record *Class = getClass(ClassName);
+  if (!Class)
+    throw "ERROR: Couldn't find the `" + ClassName + "' class!\n";
+
+  std::vector<Record*> Defs;
+  for (std::map<std::string, Record*>::const_iterator I = getDefs().begin(),
+         E = getDefs().end(); I != E; ++I)
+    if (I->second->isSubClassOf(Class))
+      Defs.push_back(I->second);
+
+  return Defs;
+}
+
diff --git a/lib/TableGen/TGLexer.cpp b/lib/TableGen/TGLexer.cpp
new file mode 100644
index 00000000000..0dc1c70136b
--- /dev/null
+++ b/lib/TableGen/TGLexer.cpp
@@ -0,0 +1,435 @@
+//===- TGLexer.cpp - Lexer for TableGen -----------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Implement the Lexer for TableGen.
+//
+//===----------------------------------------------------------------------===//
+
+#include "TGLexer.h"
+#include "llvm/TableGen/Error.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Config/config.h"
+#include "llvm/ADT/StringSwitch.h"
+#include "llvm/ADT/Twine.h"
+#include <cctype>
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+#include <cerrno>
+using namespace llvm;
+
+TGLexer::TGLexer(SourceMgr &SM) : SrcMgr(SM) {
+  CurBuffer = 0;
+  CurBuf = SrcMgr.getMemoryBuffer(CurBuffer);
+  CurPtr = CurBuf->getBufferStart();
+  TokStart = 0;
+}
+
+SMLoc TGLexer::getLoc() const {
+  return SMLoc::getFromPointer(TokStart);
+}
+
+/// ReturnError - Set the error to the specified string at the specified
+/// location.  This is defined to always return tgtok::Error.
+tgtok::TokKind TGLexer::ReturnError(const char *Loc, const Twine &Msg) {
+  PrintError(Loc, Msg);
+  return tgtok::Error;
+}
+
+int TGLexer::getNextChar() {
+  char CurChar = *CurPtr++;
+  switch (CurChar) {
+  default:
+    return (unsigned char)CurChar;
+  case 0: {
+    // A nul character in the stream is either the end of the current buffer or
+    // a random nul in the file.  Disambiguate that here.
+    if (CurPtr-1 != CurBuf->getBufferEnd())
+      return 0;  // Just whitespace.
+    
+    // If this is the end of an included file, pop the parent file off the
+    // include stack.
+    SMLoc ParentIncludeLoc = SrcMgr.getParentIncludeLoc(CurBuffer);
+    if (ParentIncludeLoc != SMLoc()) {
+      CurBuffer = SrcMgr.FindBufferContainingLoc(ParentIncludeLoc);
+      CurBuf = SrcMgr.getMemoryBuffer(CurBuffer);
+      CurPtr = ParentIncludeLoc.getPointer();
+      return getNextChar();
+    }
+    
+    // Otherwise, return end of file.
+    --CurPtr;  // Another call to lex will return EOF again.  
+    return EOF;
+  }
+  case '\n':
+  case '\r':
+    // Handle the newline character by ignoring it and incrementing the line
+    // count.  However, be careful about 'dos style' files with \n\r in them.
+    // Only treat a \n\r or \r\n as a single line.
+    if ((*CurPtr == '\n' || (*CurPtr == '\r')) &&
+        *CurPtr != CurChar)
+      ++CurPtr;  // Eat the two char newline sequence.
+    return '\n';
+  }  
+}
+
+tgtok::TokKind TGLexer::LexToken() {
+  TokStart = CurPtr;
+  // This always consumes at least one character.
+  int CurChar = getNextChar();
+
+  switch (CurChar) {
+  default:
+    // Handle letters: [a-zA-Z_#]
+    if (isalpha(CurChar) || CurChar == '_' || CurChar == '#')
+      return LexIdentifier();
+      
+    // Unknown character, emit an error.
+    return ReturnError(TokStart, "Unexpected character");
+  case EOF: return tgtok::Eof;
+  case ':': return tgtok::colon;
+  case ';': return tgtok::semi;
+  case '.': return tgtok::period;
+  case ',': return tgtok::comma;
+  case '<': return tgtok::less;
+  case '>': return tgtok::greater;
+  case ']': return tgtok::r_square;
+  case '{': return tgtok::l_brace;
+  case '}': return tgtok::r_brace;
+  case '(': return tgtok::l_paren;
+  case ')': return tgtok::r_paren;
+  case '=': return tgtok::equal;
+  case '?': return tgtok::question;
+      
+  case 0:
+  case ' ':
+  case '\t':
+  case '\n':
+  case '\r':
+    // Ignore whitespace.
+    return LexToken();
+  case '/':
+    // If this is the start of a // comment, skip until the end of the line or
+    // the end of the buffer.
+    if (*CurPtr == '/')
+      SkipBCPLComment();
+    else if (*CurPtr == '*') {
+      if (SkipCComment())
+        return tgtok::Error;
+    } else // Otherwise, this is an error.
+      return ReturnError(TokStart, "Unexpected character");
+    return LexToken();
+  case '-': case '+':
+  case '0': case '1': case '2': case '3': case '4': case '5': case '6':
+  case '7': case '8': case '9':  
+    return LexNumber();
+  case '"': return LexString();
+  case '$': return LexVarName();
+  case '[': return LexBracket();
+  case '!': return LexExclaim();
+  }
+}
+
+/// LexString - Lex "[^"]*"
+tgtok::TokKind TGLexer::LexString() {
+  const char *StrStart = CurPtr;
+  
+  CurStrVal = "";
+  
+  while (*CurPtr != '"') {
+    // If we hit the end of the buffer, report an error.
+    if (*CurPtr == 0 && CurPtr == CurBuf->getBufferEnd())
+      return ReturnError(StrStart, "End of file in string literal");
+    
+    if (*CurPtr == '\n' || *CurPtr == '\r')
+      return ReturnError(StrStart, "End of line in string literal");
+    
+    if (*CurPtr != '\\') {
+      CurStrVal += *CurPtr++;
+      continue;
+    }
+
+    ++CurPtr;
+    
+    switch (*CurPtr) {
+    case '\\': case '\'': case '"':
+      // These turn into their literal character.
+      CurStrVal += *CurPtr++;
+      break;
+    case 't':
+      CurStrVal += '\t';
+      ++CurPtr;
+      break;
+    case 'n':
+      CurStrVal += '\n';
+      ++CurPtr;
+      break;
+        
+    case '\n':
+    case '\r':
+      return ReturnError(CurPtr, "escaped newlines not supported in tblgen");
+
+    // If we hit the end of the buffer, report an error.
+    case '\0':
+      if (CurPtr == CurBuf->getBufferEnd())
+        return ReturnError(StrStart, "End of file in string literal");
+      // FALL THROUGH
+    default:
+      return ReturnError(CurPtr, "invalid escape in string literal");
+    }
+  }
+  
+  ++CurPtr;
+  return tgtok::StrVal;
+}
+
+tgtok::TokKind TGLexer::LexVarName() {
+  if (!isalpha(CurPtr[0]) && CurPtr[0] != '_')
+    return ReturnError(TokStart, "Invalid variable name");
+  
+  // Otherwise, we're ok, consume the rest of the characters.
+  const char *VarNameStart = CurPtr++;
+  
+  while (isalpha(*CurPtr) || isdigit(*CurPtr) || *CurPtr == '_')
+    ++CurPtr;
+
+  CurStrVal.assign(VarNameStart, CurPtr);
+  return tgtok::VarName;
+}
+
+
+tgtok::TokKind TGLexer::LexIdentifier() {
+  // The first letter is [a-zA-Z_#].
+  const char *IdentStart = TokStart;
+  
+  // Match the rest of the identifier regex: [0-9a-zA-Z_#]*
+  while (isalpha(*CurPtr) || isdigit(*CurPtr) || *CurPtr == '_' ||
+         *CurPtr == '#')
+    ++CurPtr;
+  
+  
+  // Check to see if this identifier is a keyword.
+  unsigned Len = CurPtr-IdentStart;
+  
+  if (Len == 3 && !memcmp(IdentStart, "int", 3)) return tgtok::Int;
+  if (Len == 3 && !memcmp(IdentStart, "bit", 3)) return tgtok::Bit;
+  if (Len == 4 && !memcmp(IdentStart, "bits", 4)) return tgtok::Bits;
+  if (Len == 6 && !memcmp(IdentStart, "string", 6)) return tgtok::String;
+  if (Len == 4 && !memcmp(IdentStart, "list", 4)) return tgtok::List;
+  if (Len == 4 && !memcmp(IdentStart, "code", 4)) return tgtok::Code;
+  if (Len == 3 && !memcmp(IdentStart, "dag", 3)) return tgtok::Dag;
+  
+  if (Len == 5 && !memcmp(IdentStart, "class", 5)) return tgtok::Class;
+  if (Len == 3 && !memcmp(IdentStart, "def", 3)) return tgtok::Def;
+  if (Len == 4 && !memcmp(IdentStart, "defm", 4)) return tgtok::Defm;
+  if (Len == 10 && !memcmp(IdentStart, "multiclass", 10))
+    return tgtok::MultiClass;
+  if (Len == 5 && !memcmp(IdentStart, "field", 5)) return tgtok::Field;
+  if (Len == 3 && !memcmp(IdentStart, "let", 3)) return tgtok::Let;
+  if (Len == 2 && !memcmp(IdentStart, "in", 2)) return tgtok::In;
+  
+  if (Len == 7 && !memcmp(IdentStart, "include", 7)) {
+    if (LexInclude()) return tgtok::Error;
+    return Lex();
+  }
+    
+  CurStrVal.assign(IdentStart, CurPtr);
+  return tgtok::Id;
+}
+
+/// LexInclude - We just read the "include" token.  Get the string token that
+/// comes next and enter the include.
+bool TGLexer::LexInclude() {
+  // The token after the include must be a string.
+  tgtok::TokKind Tok = LexToken();
+  if (Tok == tgtok::Error) return true;
+  if (Tok != tgtok::StrVal) {
+    PrintError(getLoc(), "Expected filename after include");
+    return true;
+  }
+
+  // Get the string.
+  std::string Filename = CurStrVal;
+  std::string IncludedFile;
+
+  
+  CurBuffer = SrcMgr.AddIncludeFile(Filename, SMLoc::getFromPointer(CurPtr),
+                                    IncludedFile);
+  if (CurBuffer == -1) {
+    PrintError(getLoc(), "Could not find include file '" + Filename + "'");
+    return true;
+  }
+  
+  Dependencies.push_back(IncludedFile);
+  // Save the line number and lex buffer of the includer.
+  CurBuf = SrcMgr.getMemoryBuffer(CurBuffer);
+  CurPtr = CurBuf->getBufferStart();
+  return false;
+}
+
+void TGLexer::SkipBCPLComment() {
+  ++CurPtr;  // skip the second slash.
+  while (1) {
+    switch (*CurPtr) {
+    case '\n':
+    case '\r':
+      return;  // Newline is end of comment.
+    case 0:
+      // If this is the end of the buffer, end the comment.
+      if (CurPtr == CurBuf->getBufferEnd())
+        return;
+      break;
+    }
+    // Otherwise, skip the character.
+    ++CurPtr;
+  }
+}
+
+/// SkipCComment - This skips C-style /**/ comments.  The only difference from C
+/// is that we allow nesting.
+bool TGLexer::SkipCComment() {
+  ++CurPtr;  // skip the star.
+  unsigned CommentDepth = 1;
+  
+  while (1) {
+    int CurChar = getNextChar();
+    switch (CurChar) {
+    case EOF:
+      PrintError(TokStart, "Unterminated comment!");
+      return true;
+    case '*':
+      // End of the comment?
+      if (CurPtr[0] != '/') break;
+      
+      ++CurPtr;   // End the */.
+      if (--CommentDepth == 0)
+        return false;
+      break;
+    case '/':
+      // Start of a nested comment?
+      if (CurPtr[0] != '*') break;
+      ++CurPtr;
+      ++CommentDepth;
+      break;
+    }
+  }
+}
+
+/// LexNumber - Lex:
+///    [-+]?[0-9]+
+///    0x[0-9a-fA-F]+
+///    0b[01]+
+tgtok::TokKind TGLexer::LexNumber() {
+  if (CurPtr[-1] == '0') {
+    if (CurPtr[0] == 'x') {
+      ++CurPtr;
+      const char *NumStart = CurPtr;
+      while (isxdigit(CurPtr[0]))
+        ++CurPtr;
+      
+      // Requires at least one hex digit.
+      if (CurPtr == NumStart)
+        return ReturnError(TokStart, "Invalid hexadecimal number");
+
+      errno = 0;
+      CurIntVal = strtoll(NumStart, 0, 16);
+      if (errno == EINVAL)
+        return ReturnError(TokStart, "Invalid hexadecimal number");
+      if (errno == ERANGE) {
+        errno = 0;
+        CurIntVal = (int64_t)strtoull(NumStart, 0, 16);
+        if (errno == EINVAL)
+          return ReturnError(TokStart, "Invalid hexadecimal number");
+        if (errno == ERANGE)
+          return ReturnError(TokStart, "Hexadecimal number out of range");
+      }
+      return tgtok::IntVal;
+    } else if (CurPtr[0] == 'b') {
+      ++CurPtr;
+      const char *NumStart = CurPtr;
+      while (CurPtr[0] == '0' || CurPtr[0] == '1')
+        ++CurPtr;
+
+      // Requires at least one binary digit.
+      if (CurPtr == NumStart)
+        return ReturnError(CurPtr-2, "Invalid binary number");
+      CurIntVal = strtoll(NumStart, 0, 2);
+      return tgtok::IntVal;
+    }
+  }
+
+  // Check for a sign without a digit.
+  if (!isdigit(CurPtr[0])) {
+    if (CurPtr[-1] == '-')
+      return tgtok::minus;
+    else if (CurPtr[-1] == '+')
+      return tgtok::plus;
+  }
+  
+  while (isdigit(CurPtr[0]))
+    ++CurPtr;
+  CurIntVal = strtoll(TokStart, 0, 10);
+  return tgtok::IntVal;
+}
+
+/// LexBracket - We just read '['.  If this is a code block, return it,
+/// otherwise return the bracket.  Match: '[' and '[{ ( [^}]+ | }[^]] )* }]'
+tgtok::TokKind TGLexer::LexBracket() {
+  if (CurPtr[0] != '{')
+    return tgtok::l_square;
+  ++CurPtr;
+  const char *CodeStart = CurPtr;
+  while (1) {
+    int Char = getNextChar();
+    if (Char == EOF) break;
+    
+    if (Char != '}') continue;
+    
+    Char = getNextChar();
+    if (Char == EOF) break;
+    if (Char == ']') {
+      CurStrVal.assign(CodeStart, CurPtr-2);
+      return tgtok::CodeFragment;
+    }
+  }
+  
+  return ReturnError(CodeStart-2, "Unterminated Code Block");
+}
+
+/// LexExclaim - Lex '!' and '![a-zA-Z]+'.
+tgtok::TokKind TGLexer::LexExclaim() {
+  if (!isalpha(*CurPtr))
+    return ReturnError(CurPtr - 1, "Invalid \"!operator\"");
+  
+  const char *Start = CurPtr++;
+  while (isalpha(*CurPtr))
+    ++CurPtr;
+  
+  // Check to see which operator this is.
+  tgtok::TokKind Kind =
+    StringSwitch<tgtok::TokKind>(StringRef(Start, CurPtr - Start))
+    .Case("eq", tgtok::XEq)
+    .Case("if", tgtok::XIf)
+    .Case("head", tgtok::XHead)
+    .Case("tail", tgtok::XTail)
+    .Case("con", tgtok::XConcat)
+    .Case("shl", tgtok::XSHL)
+    .Case("sra", tgtok::XSRA)
+    .Case("srl", tgtok::XSRL)
+    .Case("cast", tgtok::XCast)
+    .Case("empty", tgtok::XEmpty)
+    .Case("subst", tgtok::XSubst)
+    .Case("foreach", tgtok::XForEach)
+    .Case("strconcat", tgtok::XStrConcat)
+    .Default(tgtok::Error);
+
+  return Kind != tgtok::Error ? Kind : ReturnError(Start-1, "Unknown operator");
+}
+
diff --git a/lib/TableGen/TGLexer.h b/lib/TableGen/TGLexer.h
new file mode 100644
index 00000000000..84d328b12d9
--- /dev/null
+++ b/lib/TableGen/TGLexer.h
@@ -0,0 +1,125 @@
+//===- TGLexer.h - Lexer for TableGen Files ---------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This class represents the Lexer for tablegen files.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef TGLEXER_H
+#define TGLEXER_H
+
+#include "llvm/Support/DataTypes.h"
+#include <string>
+#include <vector>
+#include <cassert>
+
+namespace llvm {
+class MemoryBuffer;
+class SourceMgr;
+class SMLoc;
+class Twine;
+
+namespace tgtok {
+  enum TokKind {
+    // Markers
+    Eof, Error,
+    
+    // Tokens with no info.
+    minus, plus,        // - +
+    l_square, r_square, // [ ]
+    l_brace, r_brace,   // { }
+    l_paren, r_paren,   // ( )
+    less, greater,      // < >
+    colon, semi,        // : ;
+    comma, period,      // , .
+    equal, question,    // = ?
+    
+    // Keywords.
+    Bit, Bits, Class, Code, Dag, Def, Defm, Field, In, Int, Let, List,
+    MultiClass, String,
+    
+    // !keywords.
+    XConcat, XSRA, XSRL, XSHL, XStrConcat, XCast, XSubst,
+    XForEach, XHead, XTail, XEmpty, XIf, XEq,
+
+    // Integer value.
+    IntVal,
+    
+    // String valued tokens.
+    Id, StrVal, VarName, CodeFragment
+  };
+}
+
+/// TGLexer - TableGen Lexer class.
+class TGLexer {
+  SourceMgr &SrcMgr;
+  
+  const char *CurPtr;
+  const MemoryBuffer *CurBuf;
+
+  // Information about the current token.
+  const char *TokStart;
+  tgtok::TokKind CurCode;
+  std::string CurStrVal;  // This is valid for ID, STRVAL, VARNAME, CODEFRAGMENT
+  int64_t CurIntVal;      // This is valid for INTVAL.
+
+  /// CurBuffer - This is the current buffer index we're lexing from as managed
+  /// by the SourceMgr object.
+  int CurBuffer;
+  /// Dependencies - This is the list of all included files.
+  std::vector<std::string> Dependencies;
+  
+public:
+  TGLexer(SourceMgr &SrcMgr);
+  ~TGLexer() {}
+  
+  tgtok::TokKind Lex() {
+    return CurCode = LexToken();
+  }
+
+  const std::vector<std::string> &getDependencies() const {
+    return Dependencies;
+  }
+  
+  tgtok::TokKind getCode() const { return CurCode; }
+
+  const std::string &getCurStrVal() const {
+    assert((CurCode == tgtok::Id || CurCode == tgtok::StrVal || 
+            CurCode == tgtok::VarName || CurCode == tgtok::CodeFragment) &&
+           "This token doesn't have a string value");
+    return CurStrVal;
+  }
+  int64_t getCurIntVal() const {
+    assert(CurCode == tgtok::IntVal && "This token isn't an integer");
+    return CurIntVal;
+  }
+
+  SMLoc getLoc() const;
+  
+private:
+  /// LexToken - Read the next token and return its code.
+  tgtok::TokKind LexToken();
+  
+  tgtok::TokKind ReturnError(const char *Loc, const Twine &Msg);
+  
+  int getNextChar();
+  void SkipBCPLComment();
+  bool SkipCComment();
+  tgtok::TokKind LexIdentifier();
+  bool LexInclude();
+  tgtok::TokKind LexString();
+  tgtok::TokKind LexVarName();
+  tgtok::TokKind LexNumber();
+  tgtok::TokKind LexBracket();
+  tgtok::TokKind LexExclaim();
+};
+  
+} // end namespace llvm
+
+#endif
diff --git a/lib/TableGen/TGParser.cpp b/lib/TableGen/TGParser.cpp
new file mode 100644
index 00000000000..1601a530b18
--- /dev/null
+++ b/lib/TableGen/TGParser.cpp
@@ -0,0 +1,2163 @@
+//===- TGParser.cpp - Parser for TableGen Files ---------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Implement the Parser for TableGen.
+//
+//===----------------------------------------------------------------------===//
+
+#include "TGParser.h"
+#include "llvm/TableGen/Record.h"
+#include "llvm/ADT/StringExtras.h"
+#include <algorithm>
+#include <sstream>
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/CommandLine.h"
+using namespace llvm;
+
+//===----------------------------------------------------------------------===//
+// Support Code for the Semantic Actions.
+//===----------------------------------------------------------------------===//
+
+namespace llvm {
+struct SubClassReference {
+  SMLoc RefLoc;
+  Record *Rec;
+  std::vector<Init*> TemplateArgs;
+  SubClassReference() : Rec(0) {}
+
+  bool isInvalid() const { return Rec == 0; }
+};
+
+struct SubMultiClassReference {
+  SMLoc RefLoc;
+  MultiClass *MC;
+  std::vector<Init*> TemplateArgs;
+  SubMultiClassReference() : MC(0) {}
+
+  bool isInvalid() const { return MC == 0; }
+  void dump() const;
+};
+
+void SubMultiClassReference::dump() const {
+  errs() << "Multiclass:\n";
+
+  MC->dump();
+
+  errs() << "Template args:\n";
+  for (std::vector<Init *>::const_iterator i = TemplateArgs.begin(),
+         iend = TemplateArgs.end();
+       i != iend;
+       ++i) {
+    (*i)->dump();
+  }
+}
+
+} // end namespace llvm
+
+bool TGParser::AddValue(Record *CurRec, SMLoc Loc, const RecordVal &RV) {
+  if (CurRec == 0)
+    CurRec = &CurMultiClass->Rec;
+
+  if (RecordVal *ERV = CurRec->getValue(RV.getName())) {
+    // The value already exists in the class, treat this as a set.
+    if (ERV->setValue(RV.getValue()))
+      return Error(Loc, "New definition of '" + RV.getName() + "' of type '" +
+                   RV.getType()->getAsString() + "' is incompatible with " +
+                   "previous definition of type '" +
+                   ERV->getType()->getAsString() + "'");
+  } else {
+    CurRec->addValue(RV);
+  }
+  return false;
+}
+
+/// SetValue -
+/// Return true on error, false on success.
+bool TGParser::SetValue(Record *CurRec, SMLoc Loc, const std::string &ValName,
+                        const std::vector<unsigned> &BitList, Init *V) {
+  if (!V) return false;
+
+  if (CurRec == 0) CurRec = &CurMultiClass->Rec;
+
+  RecordVal *RV = CurRec->getValue(ValName);
+  if (RV == 0)
+    return Error(Loc, "Value '" + ValName + "' unknown!");
+
+  // Do not allow assignments like 'X = X'.  This will just cause infinite loops
+  // in the resolution machinery.
+  if (BitList.empty())
+    if (VarInit *VI = dynamic_cast<VarInit*>(V))
+      if (VI->getName() == ValName)
+        return false;
+
+  // If we are assigning to a subset of the bits in the value... then we must be
+  // assigning to a field of BitsRecTy, which must have a BitsInit
+  // initializer.
+  //
+  if (!BitList.empty()) {
+    BitsInit *CurVal = dynamic_cast<BitsInit*>(RV->getValue());
+    if (CurVal == 0)
+      return Error(Loc, "Value '" + ValName + "' is not a bits type");
+
+    // Convert the incoming value to a bits type of the appropriate size...
+    Init *BI = V->convertInitializerTo(BitsRecTy::get(BitList.size()));
+    if (BI == 0) {
+      V->convertInitializerTo(BitsRecTy::get(BitList.size()));
+      return Error(Loc, "Initializer is not compatible with bit range");
+    }
+
+    // We should have a BitsInit type now.
+    BitsInit *BInit = dynamic_cast<BitsInit*>(BI);
+    assert(BInit != 0);
+
+    SmallVector<Init *, 16> NewBits(CurVal->getNumBits());
+
+    // Loop over bits, assigning values as appropriate.
+    for (unsigned i = 0, e = BitList.size(); i != e; ++i) {
+      unsigned Bit = BitList[i];
+      if (NewBits[Bit])
+        return Error(Loc, "Cannot set bit #" + utostr(Bit) + " of value '" +
+                     ValName + "' more than once");
+      NewBits[Bit] = BInit->getBit(i);
+    }
+
+    for (unsigned i = 0, e = CurVal->getNumBits(); i != e; ++i)
+      if (NewBits[i] == 0)
+        NewBits[i] = CurVal->getBit(i);
+
+    V = BitsInit::get(NewBits);
+  }
+
+  if (RV->setValue(V))
+   return Error(Loc, "Value '" + ValName + "' of type '" +
+                RV->getType()->getAsString() +
+                "' is incompatible with initializer '" + V->getAsString() +"'");
+  return false;
+}
+
+/// AddSubClass - Add SubClass as a subclass to CurRec, resolving its template
+/// args as SubClass's template arguments.
+bool TGParser::AddSubClass(Record *CurRec, SubClassReference &SubClass) {
+  Record *SC = SubClass.Rec;
+  // Add all of the values in the subclass into the current class.
+  const std::vector<RecordVal> &Vals = SC->getValues();
+  for (unsigned i = 0, e = Vals.size(); i != e; ++i)
+    if (AddValue(CurRec, SubClass.RefLoc, Vals[i]))
+      return true;
+
+  const std::vector<std::string> &TArgs = SC->getTemplateArgs();
+
+  // Ensure that an appropriate number of template arguments are specified.
+  if (TArgs.size() < SubClass.TemplateArgs.size())
+    return Error(SubClass.RefLoc, "More template args specified than expected");
+
+  // Loop over all of the template arguments, setting them to the specified
+  // value or leaving them as the default if necessary.
+  for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
+    if (i < SubClass.TemplateArgs.size()) {
+      // If a value is specified for this template arg, set it now.
+      if (SetValue(CurRec, SubClass.RefLoc, TArgs[i], std::vector<unsigned>(),
+                   SubClass.TemplateArgs[i]))
+        return true;
+
+      // Resolve it next.
+      CurRec->resolveReferencesTo(CurRec->getValue(TArgs[i]));
+
+      // Now remove it.
+      CurRec->removeValue(TArgs[i]);
+
+    } else if (!CurRec->getValue(TArgs[i])->getValue()->isComplete()) {
+      return Error(SubClass.RefLoc,"Value not specified for template argument #"
+                   + utostr(i) + " (" + TArgs[i] + ") of subclass '" +
+                   SC->getName() + "'!");
+    }
+  }
+
+  // Since everything went well, we can now set the "superclass" list for the
+  // current record.
+  const std::vector<Record*> &SCs = SC->getSuperClasses();
+  for (unsigned i = 0, e = SCs.size(); i != e; ++i) {
+    if (CurRec->isSubClassOf(SCs[i]))
+      return Error(SubClass.RefLoc,
+                   "Already subclass of '" + SCs[i]->getName() + "'!\n");
+    CurRec->addSuperClass(SCs[i]);
+  }
+
+  if (CurRec->isSubClassOf(SC))
+    return Error(SubClass.RefLoc,
+                 "Already subclass of '" + SC->getName() + "'!\n");
+  CurRec->addSuperClass(SC);
+  return false;
+}
+
+/// AddSubMultiClass - Add SubMultiClass as a subclass to
+/// CurMC, resolving its template args as SubMultiClass's
+/// template arguments.
+bool TGParser::AddSubMultiClass(MultiClass *CurMC,
+                                SubMultiClassReference &SubMultiClass) {
+  MultiClass *SMC = SubMultiClass.MC;
+  Record *CurRec = &CurMC->Rec;
+
+  const std::vector<RecordVal> &MCVals = CurRec->getValues();
+
+  // Add all of the values in the subclass into the current class.
+  const std::vector<RecordVal> &SMCVals = SMC->Rec.getValues();
+  for (unsigned i = 0, e = SMCVals.size(); i != e; ++i)
+    if (AddValue(CurRec, SubMultiClass.RefLoc, SMCVals[i]))
+      return true;
+
+  int newDefStart = CurMC->DefPrototypes.size();
+
+  // Add all of the defs in the subclass into the current multiclass.
+  for (MultiClass::RecordVector::const_iterator i = SMC->DefPrototypes.begin(),
+         iend = SMC->DefPrototypes.end();
+       i != iend;
+       ++i) {
+    // Clone the def and add it to the current multiclass
+    Record *NewDef = new Record(**i);
+
+    // Add all of the values in the superclass into the current def.
+    for (unsigned i = 0, e = MCVals.size(); i != e; ++i)
+      if (AddValue(NewDef, SubMultiClass.RefLoc, MCVals[i]))
+        return true;
+
+    CurMC->DefPrototypes.push_back(NewDef);
+  }
+
+  const std::vector<std::string> &SMCTArgs = SMC->Rec.getTemplateArgs();
+
+  // Ensure that an appropriate number of template arguments are
+  // specified.
+  if (SMCTArgs.size() < SubMultiClass.TemplateArgs.size())
+    return Error(SubMultiClass.RefLoc,
+                 "More template args specified than expected");
+
+  // Loop over all of the template arguments, setting them to the specified
+  // value or leaving them as the default if necessary.
+  for (unsigned i = 0, e = SMCTArgs.size(); i != e; ++i) {
+    if (i < SubMultiClass.TemplateArgs.size()) {
+      // If a value is specified for this template arg, set it in the
+      // superclass now.
+      if (SetValue(CurRec, SubMultiClass.RefLoc, SMCTArgs[i],
+                   std::vector<unsigned>(),
+                   SubMultiClass.TemplateArgs[i]))
+        return true;
+
+      // Resolve it next.
+      CurRec->resolveReferencesTo(CurRec->getValue(SMCTArgs[i]));
+
+      // Now remove it.
+      CurRec->removeValue(SMCTArgs[i]);
+
+      // If a value is specified for this template arg, set it in the
+      // new defs now.
+      for (MultiClass::RecordVector::iterator j =
+             CurMC->DefPrototypes.begin() + newDefStart,
+             jend = CurMC->DefPrototypes.end();
+           j != jend;
+           ++j) {
+        Record *Def = *j;
+
+        if (SetValue(Def, SubMultiClass.RefLoc, SMCTArgs[i],
+                     std::vector<unsigned>(),
+                     SubMultiClass.TemplateArgs[i]))
+          return true;
+
+        // Resolve it next.
+        Def->resolveReferencesTo(Def->getValue(SMCTArgs[i]));
+
+        // Now remove it
+        Def->removeValue(SMCTArgs[i]);
+      }
+    } else if (!CurRec->getValue(SMCTArgs[i])->getValue()->isComplete()) {
+      return Error(SubMultiClass.RefLoc,
+                   "Value not specified for template argument #"
+                   + utostr(i) + " (" + SMCTArgs[i] + ") of subclass '" +
+                   SMC->Rec.getName() + "'!");
+    }
+  }
+
+  return false;
+}
+
+//===----------------------------------------------------------------------===//
+// Parser Code
+//===----------------------------------------------------------------------===//
+
+/// isObjectStart - Return true if this is a valid first token for an Object.
+static bool isObjectStart(tgtok::TokKind K) {
+  return K == tgtok::Class || K == tgtok::Def ||
+         K == tgtok::Defm || K == tgtok::Let || K == tgtok::MultiClass;
+}
+
+static std::string GetNewAnonymousName() {
+  static unsigned AnonCounter = 0;
+  return "anonymous."+utostr(AnonCounter++);
+}
+
+/// ParseObjectName - If an object name is specified, return it.  Otherwise,
+/// return an anonymous name.
+///   ObjectName ::= ID
+///   ObjectName ::= /*empty*/
+///
+std::string TGParser::ParseObjectName() {
+  if (Lex.getCode() != tgtok::Id)
+    return GetNewAnonymousName();
+
+  std::string Ret = Lex.getCurStrVal();
+  Lex.Lex();
+  return Ret;
+}
+
+
+/// ParseClassID - Parse and resolve a reference to a class name.  This returns
+/// null on error.
+///
+///    ClassID ::= ID
+///
+Record *TGParser::ParseClassID() {
+  if (Lex.getCode() != tgtok::Id) {
+    TokError("expected name for ClassID");
+    return 0;
+  }
+
+  Record *Result = Records.getClass(Lex.getCurStrVal());
+  if (Result == 0)
+    TokError("Couldn't find class '" + Lex.getCurStrVal() + "'");
+
+  Lex.Lex();
+  return Result;
+}
+
+/// ParseMultiClassID - Parse and resolve a reference to a multiclass name.
+/// This returns null on error.
+///
+///    MultiClassID ::= ID
+///
+MultiClass *TGParser::ParseMultiClassID() {
+  if (Lex.getCode() != tgtok::Id) {
+    TokError("expected name for ClassID");
+    return 0;
+  }
+
+  MultiClass *Result = MultiClasses[Lex.getCurStrVal()];
+  if (Result == 0)
+    TokError("Couldn't find class '" + Lex.getCurStrVal() + "'");
+
+  Lex.Lex();
+  return Result;
+}
+
+Record *TGParser::ParseDefmID() {
+  if (Lex.getCode() != tgtok::Id) {
+    TokError("expected multiclass name");
+    return 0;
+  }
+
+  MultiClass *MC = MultiClasses[Lex.getCurStrVal()];
+  if (MC == 0) {
+    TokError("Couldn't find multiclass '" + Lex.getCurStrVal() + "'");
+    return 0;
+  }
+
+  Lex.Lex();
+  return &MC->Rec;
+}
+
+
+/// ParseSubClassReference - Parse a reference to a subclass or to a templated
+/// subclass.  This returns a SubClassRefTy with a null Record* on error.
+///
+///  SubClassRef ::= ClassID
+///  SubClassRef ::= ClassID '<' ValueList '>'
+///
+SubClassReference TGParser::
+ParseSubClassReference(Record *CurRec, bool isDefm) {
+  SubClassReference Result;
+  Result.RefLoc = Lex.getLoc();
+
+  if (isDefm)
+    Result.Rec = ParseDefmID();
+  else
+    Result.Rec = ParseClassID();
+  if (Result.Rec == 0) return Result;
+
+  // If there is no template arg list, we're done.
+  if (Lex.getCode() != tgtok::less)
+    return Result;
+  Lex.Lex();  // Eat the '<'
+
+  if (Lex.getCode() == tgtok::greater) {
+    TokError("subclass reference requires a non-empty list of template values");
+    Result.Rec = 0;
+    return Result;
+  }
+
+  Result.TemplateArgs = ParseValueList(CurRec, Result.Rec);
+  if (Result.TemplateArgs.empty()) {
+    Result.Rec = 0;   // Error parsing value list.
+    return Result;
+  }
+
+  if (Lex.getCode() != tgtok::greater) {
+    TokError("expected '>' in template value list");
+    Result.Rec = 0;
+    return Result;
+  }
+  Lex.Lex();
+
+  return Result;
+}
+
+/// ParseSubMultiClassReference - Parse a reference to a subclass or to a
+/// templated submulticlass.  This returns a SubMultiClassRefTy with a null
+/// Record* on error.
+///
+///  SubMultiClassRef ::= MultiClassID
+///  SubMultiClassRef ::= MultiClassID '<' ValueList '>'
+///
+SubMultiClassReference TGParser::
+ParseSubMultiClassReference(MultiClass *CurMC) {
+  SubMultiClassReference Result;
+  Result.RefLoc = Lex.getLoc();
+
+  Result.MC = ParseMultiClassID();
+  if (Result.MC == 0) return Result;
+
+  // If there is no template arg list, we're done.
+  if (Lex.getCode() != tgtok::less)
+    return Result;
+  Lex.Lex();  // Eat the '<'
+
+  if (Lex.getCode() == tgtok::greater) {
+    TokError("subclass reference requires a non-empty list of template values");
+    Result.MC = 0;
+    return Result;
+  }
+
+  Result.TemplateArgs = ParseValueList(&CurMC->Rec, &Result.MC->Rec);
+  if (Result.TemplateArgs.empty()) {
+    Result.MC = 0;   // Error parsing value list.
+    return Result;
+  }
+
+  if (Lex.getCode() != tgtok::greater) {
+    TokError("expected '>' in template value list");
+    Result.MC = 0;
+    return Result;
+  }
+  Lex.Lex();
+
+  return Result;
+}
+
+/// ParseRangePiece - Parse a bit/value range.
+///   RangePiece ::= INTVAL
+///   RangePiece ::= INTVAL '-' INTVAL
+///   RangePiece ::= INTVAL INTVAL
+bool TGParser::ParseRangePiece(std::vector<unsigned> &Ranges) {
+  if (Lex.getCode() != tgtok::IntVal) {
+    TokError("expected integer or bitrange");
+    return true;
+  }
+  int64_t Start = Lex.getCurIntVal();
+  int64_t End;
+
+  if (Start < 0)
+    return TokError("invalid range, cannot be negative");
+
+  switch (Lex.Lex()) {  // eat first character.
+  default:
+    Ranges.push_back(Start);
+    return false;
+  case tgtok::minus:
+    if (Lex.Lex() != tgtok::IntVal) {
+      TokError("expected integer value as end of range");
+      return true;
+    }
+    End = Lex.getCurIntVal();
+    break;
+  case tgtok::IntVal:
+    End = -Lex.getCurIntVal();
+    break;
+  }
+  if (End < 0)
+    return TokError("invalid range, cannot be negative");
+  Lex.Lex();
+
+  // Add to the range.
+  if (Start < End) {
+    for (; Start <= End; ++Start)
+      Ranges.push_back(Start);
+  } else {
+    for (; Start >= End; --Start)
+      Ranges.push_back(Start);
+  }
+  return false;
+}
+
+/// ParseRangeList - Parse a list of scalars and ranges into scalar values.
+///
+///   RangeList ::= RangePiece (',' RangePiece)*
+///
+std::vector<unsigned> TGParser::ParseRangeList() {
+  std::vector<unsigned> Result;
+
+  // Parse the first piece.
+  if (ParseRangePiece(Result))
+    return std::vector<unsigned>();
+  while (Lex.getCode() == tgtok::comma) {
+    Lex.Lex();  // Eat the comma.
+
+    // Parse the next range piece.
+    if (ParseRangePiece(Result))
+      return std::vector<unsigned>();
+  }
+  return Result;
+}
+
+/// ParseOptionalRangeList - Parse either a range list in <>'s or nothing.
+///   OptionalRangeList ::= '<' RangeList '>'
+///   OptionalRangeList ::= /*empty*/
+bool TGParser::ParseOptionalRangeList(std::vector<unsigned> &Ranges) {
+  if (Lex.getCode() != tgtok::less)
+    return false;
+
+  SMLoc StartLoc = Lex.getLoc();
+  Lex.Lex(); // eat the '<'
+
+  // Parse the range list.
+  Ranges = ParseRangeList();
+  if (Ranges.empty()) return true;
+
+  if (Lex.getCode() != tgtok::greater) {
+    TokError("expected '>' at end of range list");
+    return Error(StartLoc, "to match this '<'");
+  }
+  Lex.Lex();   // eat the '>'.
+  return false;
+}
+
+/// ParseOptionalBitList - Parse either a bit list in {}'s or nothing.
+///   OptionalBitList ::= '{' RangeList '}'
+///   OptionalBitList ::= /*empty*/
+bool TGParser::ParseOptionalBitList(std::vector<unsigned> &Ranges) {
+  if (Lex.getCode() != tgtok::l_brace)
+    return false;
+
+  SMLoc StartLoc = Lex.getLoc();
+  Lex.Lex(); // eat the '{'
+
+  // Parse the range list.
+  Ranges = ParseRangeList();
+  if (Ranges.empty()) return true;
+
+  if (Lex.getCode() != tgtok::r_brace) {
+    TokError("expected '}' at end of bit list");
+    return Error(StartLoc, "to match this '{'");
+  }
+  Lex.Lex();   // eat the '}'.
+  return false;
+}
+
+
+/// ParseType - Parse and return a tblgen type.  This returns null on error.
+///
+///   Type ::= STRING                       // string type
+///   Type ::= BIT                          // bit type
+///   Type ::= BITS '<' INTVAL '>'          // bits<x> type
+///   Type ::= INT                          // int type
+///   Type ::= LIST '<' Type '>'            // list<x> type
+///   Type ::= CODE                         // code type
+///   Type ::= DAG                          // dag type
+///   Type ::= ClassID                      // Record Type
+///
+RecTy *TGParser::ParseType() {
+  switch (Lex.getCode()) {
+  default: TokError("Unknown token when expecting a type"); return 0;
+  case tgtok::String: Lex.Lex(); return StringRecTy::get();
+  case tgtok::Bit:    Lex.Lex(); return BitRecTy::get();
+  case tgtok::Int:    Lex.Lex(); return IntRecTy::get();
+  case tgtok::Code:   Lex.Lex(); return CodeRecTy::get();
+  case tgtok::Dag:    Lex.Lex(); return DagRecTy::get();
+  case tgtok::Id:
+    if (Record *R = ParseClassID()) return RecordRecTy::get(R);
+    return 0;
+  case tgtok::Bits: {
+    if (Lex.Lex() != tgtok::less) { // Eat 'bits'
+      TokError("expected '<' after bits type");
+      return 0;
+    }
+    if (Lex.Lex() != tgtok::IntVal) {  // Eat '<'
+      TokError("expected integer in bits<n> type");
+      return 0;
+    }
+    uint64_t Val = Lex.getCurIntVal();
+    if (Lex.Lex() != tgtok::greater) {  // Eat count.
+      TokError("expected '>' at end of bits<n> type");
+      return 0;
+    }
+    Lex.Lex();  // Eat '>'
+    return BitsRecTy::get(Val);
+  }
+  case tgtok::List: {
+    if (Lex.Lex() != tgtok::less) { // Eat 'bits'
+      TokError("expected '<' after list type");
+      return 0;
+    }
+    Lex.Lex();  // Eat '<'
+    RecTy *SubType = ParseType();
+    if (SubType == 0) return 0;
+
+    if (Lex.getCode() != tgtok::greater) {
+      TokError("expected '>' at end of list<ty> type");
+      return 0;
+    }
+    Lex.Lex();  // Eat '>'
+    return ListRecTy::get(SubType);
+  }
+  }
+}
+
+/// ParseIDValue - Parse an ID as a value and decode what it means.
+///
+///  IDValue ::= ID [def local value]
+///  IDValue ::= ID [def template arg]
+///  IDValue ::= ID [multiclass local value]
+///  IDValue ::= ID [multiclass template argument]
+///  IDValue ::= ID [def name]
+///
+Init *TGParser::ParseIDValue(Record *CurRec) {
+  assert(Lex.getCode() == tgtok::Id && "Expected ID in ParseIDValue");
+  std::string Name = Lex.getCurStrVal();
+  SMLoc Loc = Lex.getLoc();
+  Lex.Lex();
+  return ParseIDValue(CurRec, Name, Loc);
+}
+
+/// ParseIDValue - This is just like ParseIDValue above, but it assumes the ID
+/// has already been read.
+Init *TGParser::ParseIDValue(Record *CurRec,
+                             const std::string &Name, SMLoc NameLoc) {
+  if (CurRec) {
+    if (const RecordVal *RV = CurRec->getValue(Name))
+      return VarInit::get(Name, RV->getType());
+
+    std::string TemplateArgName = CurRec->getName()+":"+Name;
+    if (CurRec->isTemplateArg(TemplateArgName)) {
+      const RecordVal *RV = CurRec->getValue(TemplateArgName);
+      assert(RV && "Template arg doesn't exist??");
+      return VarInit::get(TemplateArgName, RV->getType());
+    }
+  }
+
+  if (CurMultiClass) {
+    std::string MCName = CurMultiClass->Rec.getName()+"::"+Name;
+    if (CurMultiClass->Rec.isTemplateArg(MCName)) {
+      const RecordVal *RV = CurMultiClass->Rec.getValue(MCName);
+      assert(RV && "Template arg doesn't exist??");
+      return VarInit::get(MCName, RV->getType());
+    }
+  }
+
+  if (Record *D = Records.getDef(Name))
+    return DefInit::get(D);
+
+  Error(NameLoc, "Variable not defined: '" + Name + "'");
+  return 0;
+}
+
+/// ParseOperation - Parse an operator.  This returns null on error.
+///
+/// Operation ::= XOperator ['<' Type '>'] '(' Args ')'
+///
+Init *TGParser::ParseOperation(Record *CurRec) {
+  switch (Lex.getCode()) {
+  default:
+    TokError("unknown operation");
+    return 0;
+    break;
+  case tgtok::XHead:
+  case tgtok::XTail:
+  case tgtok::XEmpty:
+  case tgtok::XCast: {  // Value ::= !unop '(' Value ')'
+    UnOpInit::UnaryOp Code;
+    RecTy *Type = 0;
+
+    switch (Lex.getCode()) {
+    default: assert(0 && "Unhandled code!");
+    case tgtok::XCast:
+      Lex.Lex();  // eat the operation
+      Code = UnOpInit::CAST;
+
+      Type = ParseOperatorType();
+
+      if (Type == 0) {
+        TokError("did not get type for unary operator");
+        return 0;
+      }
+
+      break;
+    case tgtok::XHead:
+      Lex.Lex();  // eat the operation
+      Code = UnOpInit::HEAD;
+      break;
+    case tgtok::XTail:
+      Lex.Lex();  // eat the operation
+      Code = UnOpInit::TAIL;
+      break;
+    case tgtok::XEmpty:
+      Lex.Lex();  // eat the operation
+      Code = UnOpInit::EMPTY;
+      Type = IntRecTy::get();
+      break;
+    }
+    if (Lex.getCode() != tgtok::l_paren) {
+      TokError("expected '(' after unary operator");
+      return 0;
+    }
+    Lex.Lex();  // eat the '('
+
+    Init *LHS = ParseValue(CurRec);
+    if (LHS == 0) return 0;
+
+    if (Code == UnOpInit::HEAD
+        || Code == UnOpInit::TAIL
+        || Code == UnOpInit::EMPTY) {
+      ListInit *LHSl = dynamic_cast<ListInit*>(LHS);
+      StringInit *LHSs = dynamic_cast<StringInit*>(LHS);
+      TypedInit *LHSt = dynamic_cast<TypedInit*>(LHS);
+      if (LHSl == 0 && LHSs == 0 && LHSt == 0) {
+        TokError("expected list or string type argument in unary operator");
+        return 0;
+      }
+      if (LHSt) {
+        ListRecTy *LType = dynamic_cast<ListRecTy*>(LHSt->getType());
+        StringRecTy *SType = dynamic_cast<StringRecTy*>(LHSt->getType());
+        if (LType == 0 && SType == 0) {
+          TokError("expected list or string type argumnet in unary operator");
+          return 0;
+        }
+      }
+
+      if (Code == UnOpInit::HEAD
+          || Code == UnOpInit::TAIL) {
+        if (LHSl == 0 && LHSt == 0) {
+          TokError("expected list type argumnet in unary operator");
+          return 0;
+        }
+
+        if (LHSl && LHSl->getSize() == 0) {
+          TokError("empty list argument in unary operator");
+          return 0;
+        }
+        if (LHSl) {
+          Init *Item = LHSl->getElement(0);
+          TypedInit *Itemt = dynamic_cast<TypedInit*>(Item);
+          if (Itemt == 0) {
+            TokError("untyped list element in unary operator");
+            return 0;
+          }
+          if (Code == UnOpInit::HEAD) {
+            Type = Itemt->getType();
+          } else {
+            Type = ListRecTy::get(Itemt->getType());
+          }
+        } else {
+          assert(LHSt && "expected list type argument in unary operator");
+          ListRecTy *LType = dynamic_cast<ListRecTy*>(LHSt->getType());
+          if (LType == 0) {
+            TokError("expected list type argumnet in unary operator");
+            return 0;
+          }
+          if (Code == UnOpInit::HEAD) {
+            Type = LType->getElementType();
+          } else {
+            Type = LType;
+          }
+        }
+      }
+    }
+
+    if (Lex.getCode() != tgtok::r_paren) {
+      TokError("expected ')' in unary operator");
+      return 0;
+    }
+    Lex.Lex();  // eat the ')'
+    return (UnOpInit::get(Code, LHS, Type))->Fold(CurRec, CurMultiClass);
+  }
+
+  case tgtok::XConcat:
+  case tgtok::XSRA:
+  case tgtok::XSRL:
+  case tgtok::XSHL:
+  case tgtok::XEq:
+  case tgtok::XStrConcat: {  // Value ::= !binop '(' Value ',' Value ')'
+    tgtok::TokKind OpTok = Lex.getCode();
+    SMLoc OpLoc = Lex.getLoc();
+    Lex.Lex();  // eat the operation
+
+    BinOpInit::BinaryOp Code;
+    RecTy *Type = 0;
+
+    switch (OpTok) {
+    default: assert(0 && "Unhandled code!");
+    case tgtok::XConcat: Code = BinOpInit::CONCAT;Type = DagRecTy::get(); break;
+    case tgtok::XSRA:    Code = BinOpInit::SRA;   Type = IntRecTy::get(); break;
+    case tgtok::XSRL:    Code = BinOpInit::SRL;   Type = IntRecTy::get(); break;
+    case tgtok::XSHL:    Code = BinOpInit::SHL;   Type = IntRecTy::get(); break;
+    case tgtok::XEq:     Code = BinOpInit::EQ;    Type = BitRecTy::get(); break;
+    case tgtok::XStrConcat:
+      Code = BinOpInit::STRCONCAT;
+      Type = StringRecTy::get();
+      break;
+    }
+
+    if (Lex.getCode() != tgtok::l_paren) {
+      TokError("expected '(' after binary operator");
+      return 0;
+    }
+    Lex.Lex();  // eat the '('
+
+    SmallVector<Init*, 2> InitList;
+
+    InitList.push_back(ParseValue(CurRec));
+    if (InitList.back() == 0) return 0;
+
+    while (Lex.getCode() == tgtok::comma) {
+      Lex.Lex();  // eat the ','
+
+      InitList.push_back(ParseValue(CurRec));
+      if (InitList.back() == 0) return 0;
+    }
+
+    if (Lex.getCode() != tgtok::r_paren) {
+      TokError("expected ')' in operator");
+      return 0;
+    }
+    Lex.Lex();  // eat the ')'
+
+    // We allow multiple operands to associative operators like !strconcat as
+    // shorthand for nesting them.
+    if (Code == BinOpInit::STRCONCAT) {
+      while (InitList.size() > 2) {
+        Init *RHS = InitList.pop_back_val();
+        RHS = (BinOpInit::get(Code, InitList.back(), RHS, Type))
+                           ->Fold(CurRec, CurMultiClass);
+        InitList.back() = RHS;
+      }
+    }
+
+    if (InitList.size() == 2)
+      return (BinOpInit::get(Code, InitList[0], InitList[1], Type))
+        ->Fold(CurRec, CurMultiClass);
+
+    Error(OpLoc, "expected two operands to operator");
+    return 0;
+  }
+
+  case tgtok::XIf:
+  case tgtok::XForEach:
+  case tgtok::XSubst: {  // Value ::= !ternop '(' Value ',' Value ',' Value ')'
+    TernOpInit::TernaryOp Code;
+    RecTy *Type = 0;
+
+    tgtok::TokKind LexCode = Lex.getCode();
+    Lex.Lex();  // eat the operation
+    switch (LexCode) {
+    default: assert(0 && "Unhandled code!");
+    case tgtok::XIf:
+      Code = TernOpInit::IF;
+      break;
+    case tgtok::XForEach:
+      Code = TernOpInit::FOREACH;
+      break;
+    case tgtok::XSubst:
+      Code = TernOpInit::SUBST;
+      break;
+    }
+    if (Lex.getCode() != tgtok::l_paren) {
+      TokError("expected '(' after ternary operator");
+      return 0;
+    }
+    Lex.Lex();  // eat the '('
+
+    Init *LHS = ParseValue(CurRec);
+    if (LHS == 0) return 0;
+
+    if (Lex.getCode() != tgtok::comma) {
+      TokError("expected ',' in ternary operator");
+      return 0;
+    }
+    Lex.Lex();  // eat the ','
+
+    Init *MHS = ParseValue(CurRec);
+    if (MHS == 0) return 0;
+
+    if (Lex.getCode() != tgtok::comma) {
+      TokError("expected ',' in ternary operator");
+      return 0;
+    }
+    Lex.Lex();  // eat the ','
+
+    Init *RHS = ParseValue(CurRec);
+    if (RHS == 0) return 0;
+
+    if (Lex.getCode() != tgtok::r_paren) {
+      TokError("expected ')' in binary operator");
+      return 0;
+    }
+    Lex.Lex();  // eat the ')'
+
+    switch (LexCode) {
+    default: assert(0 && "Unhandled code!");
+    case tgtok::XIf: {
+      // FIXME: The `!if' operator doesn't handle non-TypedInit well at
+      // all. This can be made much more robust.
+      TypedInit *MHSt = dynamic_cast<TypedInit*>(MHS);
+      TypedInit *RHSt = dynamic_cast<TypedInit*>(RHS);
+
+      RecTy *MHSTy = 0;
+      RecTy *RHSTy = 0;
+
+      if (MHSt == 0 && RHSt == 0) {
+        BitsInit *MHSbits = dynamic_cast<BitsInit*>(MHS);
+        BitsInit *RHSbits = dynamic_cast<BitsInit*>(RHS);
+
+        if (MHSbits && RHSbits &&
+            MHSbits->getNumBits() == RHSbits->getNumBits()) {
+          Type = BitRecTy::get();
+          break;
+        } else {
+          BitInit *MHSbit = dynamic_cast<BitInit*>(MHS);
+          BitInit *RHSbit = dynamic_cast<BitInit*>(RHS);
+
+          if (MHSbit && RHSbit) {
+            Type = BitRecTy::get();
+            break;
+          }
+        }
+      } else if (MHSt != 0 && RHSt != 0) {
+        MHSTy = MHSt->getType();
+        RHSTy = RHSt->getType();
+      }
+
+      if (!MHSTy || !RHSTy) {
+        TokError("could not get type for !if");
+        return 0;
+      }
+
+      if (MHSTy->typeIsConvertibleTo(RHSTy)) {
+        Type = RHSTy;
+      } else if (RHSTy->typeIsConvertibleTo(MHSTy)) {
+        Type = MHSTy;
+      } else {
+        TokError("inconsistent types for !if");
+        return 0;
+      }
+      break;
+    }
+    case tgtok::XForEach: {
+      TypedInit *MHSt = dynamic_cast<TypedInit *>(MHS);
+      if (MHSt == 0) {
+        TokError("could not get type for !foreach");
+        return 0;
+      }
+      Type = MHSt->getType();
+      break;
+    }
+    case tgtok::XSubst: {
+      TypedInit *RHSt = dynamic_cast<TypedInit *>(RHS);
+      if (RHSt == 0) {
+        TokError("could not get type for !subst");
+        return 0;
+      }
+      Type = RHSt->getType();
+      break;
+    }
+    }
+    return (TernOpInit::get(Code, LHS, MHS, RHS, Type))->Fold(CurRec,
+                                                             CurMultiClass);
+  }
+  }
+  TokError("could not parse operation");
+  return 0;
+}
+
+/// ParseOperatorType - Parse a type for an operator.  This returns
+/// null on error.
+///
+/// OperatorType ::= '<' Type '>'
+///
+RecTy *TGParser::ParseOperatorType() {
+  RecTy *Type = 0;
+
+  if (Lex.getCode() != tgtok::less) {
+    TokError("expected type name for operator");
+    return 0;
+  }
+  Lex.Lex();  // eat the <
+
+  Type = ParseType();
+
+  if (Type == 0) {
+    TokError("expected type name for operator");
+    return 0;
+  }
+
+  if (Lex.getCode() != tgtok::greater) {
+    TokError("expected type name for operator");
+    return 0;
+  }
+  Lex.Lex();  // eat the >
+
+  return Type;
+}
+
+
+/// ParseSimpleValue - Parse a tblgen value.  This returns null on error.
+///
+///   SimpleValue ::= IDValue
+///   SimpleValue ::= INTVAL
+///   SimpleValue ::= STRVAL+
+///   SimpleValue ::= CODEFRAGMENT
+///   SimpleValue ::= '?'
+///   SimpleValue ::= '{' ValueList '}'
+///   SimpleValue ::= ID '<' ValueListNE '>'
+///   SimpleValue ::= '[' ValueList ']'
+///   SimpleValue ::= '(' IDValue DagArgList ')'
+///   SimpleValue ::= CONCATTOK '(' Value ',' Value ')'
+///   SimpleValue ::= SHLTOK '(' Value ',' Value ')'
+///   SimpleValue ::= SRATOK '(' Value ',' Value ')'
+///   SimpleValue ::= SRLTOK '(' Value ',' Value ')'
+///   SimpleValue ::= STRCONCATTOK '(' Value ',' Value ')'
+///
+Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType) {
+  Init *R = 0;
+  switch (Lex.getCode()) {
+  default: TokError("Unknown token when parsing a value"); break;
+  case tgtok::IntVal: R = IntInit::get(Lex.getCurIntVal()); Lex.Lex(); break;
+  case tgtok::StrVal: {
+    std::string Val = Lex.getCurStrVal();
+    Lex.Lex();
+
+    // Handle multiple consecutive concatenated strings.
+    while (Lex.getCode() == tgtok::StrVal) {
+      Val += Lex.getCurStrVal();
+      Lex.Lex();
+    }
+
+    R = StringInit::get(Val);
+    break;
+  }
+  case tgtok::CodeFragment:
+    R = CodeInit::get(Lex.getCurStrVal());
+    Lex.Lex();
+    break;
+  case tgtok::question:
+    R = UnsetInit::get();
+    Lex.Lex();
+    break;
+  case tgtok::Id: {
+    SMLoc NameLoc = Lex.getLoc();
+    std::string Name = Lex.getCurStrVal();
+    if (Lex.Lex() != tgtok::less)  // consume the Id.
+      return ParseIDValue(CurRec, Name, NameLoc);    // Value ::= IDValue
+
+    // Value ::= ID '<' ValueListNE '>'
+    if (Lex.Lex() == tgtok::greater) {
+      TokError("expected non-empty value list");
+      return 0;
+    }
+
+    // This is a CLASS<initvalslist> expression.  This is supposed to synthesize
+    // a new anonymous definition, deriving from CLASS<initvalslist> with no
+    // body.
+    Record *Class = Records.getClass(Name);
+    if (!Class) {
+      Error(NameLoc, "Expected a class name, got '" + Name + "'");
+      return 0;
+    }
+
+    std::vector<Init*> ValueList = ParseValueList(CurRec, Class);
+    if (ValueList.empty()) return 0;
+
+    if (Lex.getCode() != tgtok::greater) {
+      TokError("expected '>' at end of value list");
+      return 0;
+    }
+    Lex.Lex();  // eat the '>'
+
+    // Create the new record, set it as CurRec temporarily.
+    static unsigned AnonCounter = 0;
+    Record *NewRec = new Record("anonymous.val."+utostr(AnonCounter++),
+                                NameLoc,
+                                Records);
+    SubClassReference SCRef;
+    SCRef.RefLoc = NameLoc;
+    SCRef.Rec = Class;
+    SCRef.TemplateArgs = ValueList;
+    // Add info about the subclass to NewRec.
+    if (AddSubClass(NewRec, SCRef))
+      return 0;
+    NewRec->resolveReferences();
+    Records.addDef(NewRec);
+
+    // The result of the expression is a reference to the new record.
+    return DefInit::get(NewRec);
+  }
+  case tgtok::l_brace: {           // Value ::= '{' ValueList '}'
+    SMLoc BraceLoc = Lex.getLoc();
+    Lex.Lex(); // eat the '{'
+    std::vector<Init*> Vals;
+
+    if (Lex.getCode() != tgtok::r_brace) {
+      Vals = ParseValueList(CurRec);
+      if (Vals.empty()) return 0;
+    }
+    if (Lex.getCode() != tgtok::r_brace) {
+      TokError("expected '}' at end of bit list value");
+      return 0;
+    }
+    Lex.Lex();  // eat the '}'
+
+    SmallVector<Init *, 16> NewBits(Vals.size());
+
+    for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
+      Init *Bit = Vals[i]->convertInitializerTo(BitRecTy::get());
+      if (Bit == 0) {
+        Error(BraceLoc, "Element #" + utostr(i) + " (" + Vals[i]->getAsString()+
+              ") is not convertable to a bit");
+        return 0;
+      }
+      NewBits[Vals.size()-i-1] = Bit;
+    }
+    return BitsInit::get(NewBits);
+  }
+  case tgtok::l_square: {          // Value ::= '[' ValueList ']'
+    Lex.Lex(); // eat the '['
+    std::vector<Init*> Vals;
+
+    RecTy *DeducedEltTy = 0;
+    ListRecTy *GivenListTy = 0;
+
+    if (ItemType != 0) {
+      ListRecTy *ListType = dynamic_cast<ListRecTy*>(ItemType);
+      if (ListType == 0) {
+        std::stringstream s;
+        s << "Type mismatch for list, expected list type, got "
+          << ItemType->getAsString();
+        TokError(s.str());
+        return 0;
+      }
+      GivenListTy = ListType;
+    }
+
+    if (Lex.getCode() != tgtok::r_square) {
+      Vals = ParseValueList(CurRec, 0,
+                            GivenListTy ? GivenListTy->getElementType() : 0);
+      if (Vals.empty()) return 0;
+    }
+    if (Lex.getCode() != tgtok::r_square) {
+      TokError("expected ']' at end of list value");
+      return 0;
+    }
+    Lex.Lex();  // eat the ']'
+
+    RecTy *GivenEltTy = 0;
+    if (Lex.getCode() == tgtok::less) {
+      // Optional list element type
+      Lex.Lex();  // eat the '<'
+
+      GivenEltTy = ParseType();
+      if (GivenEltTy == 0) {
+        // Couldn't parse element type
+        return 0;
+      }
+
+      if (Lex.getCode() != tgtok::greater) {
+        TokError("expected '>' at end of list element type");
+        return 0;
+      }
+      Lex.Lex();  // eat the '>'
+    }
+
+    // Check elements
+    RecTy *EltTy = 0;
+    for (std::vector<Init *>::iterator i = Vals.begin(), ie = Vals.end();
+         i != ie;
+         ++i) {
+      TypedInit *TArg = dynamic_cast<TypedInit*>(*i);
+      if (TArg == 0) {
+        TokError("Untyped list element");
+        return 0;
+      }
+      if (EltTy != 0) {
+        EltTy = resolveTypes(EltTy, TArg->getType());
+        if (EltTy == 0) {
+          TokError("Incompatible types in list elements");
+          return 0;
+        }
+      } else {
+        EltTy = TArg->getType();
+      }
+    }
+
+    if (GivenEltTy != 0) {
+      if (EltTy != 0) {
+        // Verify consistency
+        if (!EltTy->typeIsConvertibleTo(GivenEltTy)) {
+          TokError("Incompatible types in list elements");
+          return 0;
+        }
+      }
+      EltTy = GivenEltTy;
+    }
+
+    if (EltTy == 0) {
+      if (ItemType == 0) {
+        TokError("No type for list");
+        return 0;
+      }
+      DeducedEltTy = GivenListTy->getElementType();
+    } else {
+      // Make sure the deduced type is compatible with the given type
+      if (GivenListTy) {
+        if (!EltTy->typeIsConvertibleTo(GivenListTy->getElementType())) {
+          TokError("Element type mismatch for list");
+          return 0;
+        }
+      }
+      DeducedEltTy = EltTy;
+    }
+
+    return ListInit::get(Vals, DeducedEltTy);
+  }
+  case tgtok::l_paren: {         // Value ::= '(' IDValue DagArgList ')'
+    Lex.Lex();   // eat the '('
+    if (Lex.getCode() != tgtok::Id && Lex.getCode() != tgtok::XCast) {
+      TokError("expected identifier in dag init");
+      return 0;
+    }
+
+    Init *Operator = ParseValue(CurRec);
+    if (Operator == 0) return 0;
+
+    // If the operator name is present, parse it.
+    std::string OperatorName;
+    if (Lex.getCode() == tgtok::colon) {
+      if (Lex.Lex() != tgtok::VarName) { // eat the ':'
+        TokError("expected variable name in dag operator");
+        return 0;
+      }
+      OperatorName = Lex.getCurStrVal();
+      Lex.Lex();  // eat the VarName.
+    }
+
+    std::vector<std::pair<llvm::Init*, std::string> > DagArgs;
+    if (Lex.getCode() != tgtok::r_paren) {
+      DagArgs = ParseDagArgList(CurRec);
+      if (DagArgs.empty()) return 0;
+    }
+
+    if (Lex.getCode() != tgtok::r_paren) {
+      TokError("expected ')' in dag init");
+      return 0;
+    }
+    Lex.Lex();  // eat the ')'
+
+    return DagInit::get(Operator, OperatorName, DagArgs);
+  }
+
+  case tgtok::XHead:
+  case tgtok::XTail:
+  case tgtok::XEmpty:
+  case tgtok::XCast:  // Value ::= !unop '(' Value ')'
+  case tgtok::XConcat:
+  case tgtok::XSRA:
+  case tgtok::XSRL:
+  case tgtok::XSHL:
+  case tgtok::XEq:
+  case tgtok::XStrConcat:   // Value ::= !binop '(' Value ',' Value ')'
+  case tgtok::XIf:
+  case tgtok::XForEach:
+  case tgtok::XSubst: {  // Value ::= !ternop '(' Value ',' Value ',' Value ')'
+    return ParseOperation(CurRec);
+  }
+  }
+
+  return R;
+}
+
+/// ParseValue - Parse a tblgen value.  This returns null on error.
+///
+///   Value       ::= SimpleValue ValueSuffix*
+///   ValueSuffix ::= '{' BitList '}'
+///   ValueSuffix ::= '[' BitList ']'
+///   ValueSuffix ::= '.' ID
+///
+Init *TGParser::ParseValue(Record *CurRec, RecTy *ItemType) {
+  Init *Result = ParseSimpleValue(CurRec, ItemType);
+  if (Result == 0) return 0;
+
+  // Parse the suffixes now if present.
+  while (1) {
+    switch (Lex.getCode()) {
+    default: return Result;
+    case tgtok::l_brace: {
+      SMLoc CurlyLoc = Lex.getLoc();
+      Lex.Lex(); // eat the '{'
+      std::vector<unsigned> Ranges = ParseRangeList();
+      if (Ranges.empty()) return 0;
+
+      // Reverse the bitlist.
+      std::reverse(Ranges.begin(), Ranges.end());
+      Result = Result->convertInitializerBitRange(Ranges);
+      if (Result == 0) {
+        Error(CurlyLoc, "Invalid bit range for value");
+        return 0;
+      }
+
+      // Eat the '}'.
+      if (Lex.getCode() != tgtok::r_brace) {
+        TokError("expected '}' at end of bit range list");
+        return 0;
+      }
+      Lex.Lex();
+      break;
+    }
+    case tgtok::l_square: {
+      SMLoc SquareLoc = Lex.getLoc();
+      Lex.Lex(); // eat the '['
+      std::vector<unsigned> Ranges = ParseRangeList();
+      if (Ranges.empty()) return 0;
+
+      Result = Result->convertInitListSlice(Ranges);
+      if (Result == 0) {
+        Error(SquareLoc, "Invalid range for list slice");
+        return 0;
+      }
+
+      // Eat the ']'.
+      if (Lex.getCode() != tgtok::r_square) {
+        TokError("expected ']' at end of list slice");
+        return 0;
+      }
+      Lex.Lex();
+      break;
+    }
+    case tgtok::period:
+      if (Lex.Lex() != tgtok::Id) {  // eat the .
+        TokError("expected field identifier after '.'");
+        return 0;
+      }
+      if (!Result->getFieldType(Lex.getCurStrVal())) {
+        TokError("Cannot access field '" + Lex.getCurStrVal() + "' of value '" +
+                 Result->getAsString() + "'");
+        return 0;
+      }
+      Result = FieldInit::get(Result, Lex.getCurStrVal());
+      Lex.Lex();  // eat field name
+      break;
+    }
+  }
+}
+
+/// ParseDagArgList - Parse the argument list for a dag literal expression.
+///
+///    ParseDagArgList ::= Value (':' VARNAME)?
+///    ParseDagArgList ::= ParseDagArgList ',' Value (':' VARNAME)?
+std::vector<std::pair<llvm::Init*, std::string> >
+TGParser::ParseDagArgList(Record *CurRec) {
+  std::vector<std::pair<llvm::Init*, std::string> > Result;
+
+  while (1) {
+    Init *Val = ParseValue(CurRec);
+    if (Val == 0) return std::vector<std::pair<llvm::Init*, std::string> >();
+
+    // If the variable name is present, add it.
+    std::string VarName;
+    if (Lex.getCode() == tgtok::colon) {
+      if (Lex.Lex() != tgtok::VarName) { // eat the ':'
+        TokError("expected variable name in dag literal");
+        return std::vector<std::pair<llvm::Init*, std::string> >();
+      }
+      VarName = Lex.getCurStrVal();
+      Lex.Lex();  // eat the VarName.
+    }
+
+    Result.push_back(std::make_pair(Val, VarName));
+
+    if (Lex.getCode() != tgtok::comma) break;
+    Lex.Lex(); // eat the ','
+  }
+
+  return Result;
+}
+
+
+/// ParseValueList - Parse a comma separated list of values, returning them as a
+/// vector.  Note that this always expects to be able to parse at least one
+/// value.  It returns an empty list if this is not possible.
+///
+///   ValueList ::= Value (',' Value)
+///
+std::vector<Init*> TGParser::ParseValueList(Record *CurRec, Record *ArgsRec,
+                                            RecTy *EltTy) {
+  std::vector<Init*> Result;
+  RecTy *ItemType = EltTy;
+  unsigned int ArgN = 0;
+  if (ArgsRec != 0 && EltTy == 0) {
+    const std::vector<std::string> &TArgs = ArgsRec->getTemplateArgs();
+    const RecordVal *RV = ArgsRec->getValue(TArgs[ArgN]);
+    if (!RV) {
+      errs() << "Cannot find template arg " << ArgN << " (" << TArgs[ArgN]
+        << ")\n";
+    }
+    assert(RV && "Template argument record not found??");
+    ItemType = RV->getType();
+    ++ArgN;
+  }
+  Result.push_back(ParseValue(CurRec, ItemType));
+  if (Result.back() == 0) return std::vector<Init*>();
+
+  while (Lex.getCode() == tgtok::comma) {
+    Lex.Lex();  // Eat the comma
+
+    if (ArgsRec != 0 && EltTy == 0) {
+      const std::vector<std::string> &TArgs = ArgsRec->getTemplateArgs();
+      if (ArgN >= TArgs.size()) {
+        TokError("too many template arguments");
+        return std::vector<Init*>();
+      }
+      const RecordVal *RV = ArgsRec->getValue(TArgs[ArgN]);
+      assert(RV && "Template argument record not found??");
+      ItemType = RV->getType();
+      ++ArgN;
+    }
+    Result.push_back(ParseValue(CurRec, ItemType));
+    if (Result.back() == 0) return std::vector<Init*>();
+  }
+
+  return Result;
+}
+
+
+/// ParseDeclaration - Read a declaration, returning the name of field ID, or an
+/// empty string on error.  This can happen in a number of different context's,
+/// including within a def or in the template args for a def (which which case
+/// CurRec will be non-null) and within the template args for a multiclass (in
+/// which case CurRec will be null, but CurMultiClass will be set).  This can
+/// also happen within a def that is within a multiclass, which will set both
+/// CurRec and CurMultiClass.
+///
+///  Declaration ::= FIELD? Type ID ('=' Value)?
+///
+std::string TGParser::ParseDeclaration(Record *CurRec,
+                                       bool ParsingTemplateArgs) {
+  // Read the field prefix if present.
+  bool HasField = Lex.getCode() == tgtok::Field;
+  if (HasField) Lex.Lex();
+
+  RecTy *Type = ParseType();
+  if (Type == 0) return "";
+
+  if (Lex.getCode() != tgtok::Id) {
+    TokError("Expected identifier in declaration");
+    return "";
+  }
+
+  SMLoc IdLoc = Lex.getLoc();
+  std::string DeclName = Lex.getCurStrVal();
+  Lex.Lex();
+
+  if (ParsingTemplateArgs) {
+    if (CurRec) {
+      DeclName = CurRec->getName() + ":" + DeclName;
+    } else {
+      assert(CurMultiClass);
+    }
+    if (CurMultiClass)
+      DeclName = CurMultiClass->Rec.getName() + "::" + DeclName;
+  }
+
+  // Add the value.
+  if (AddValue(CurRec, IdLoc, RecordVal(DeclName, Type, HasField)))
+    return "";
+
+  // If a value is present, parse it.
+  if (Lex.getCode() == tgtok::equal) {
+    Lex.Lex();
+    SMLoc ValLoc = Lex.getLoc();
+    Init *Val = ParseValue(CurRec, Type);
+    if (Val == 0 ||
+        SetValue(CurRec, ValLoc, DeclName, std::vector<unsigned>(), Val))
+      return "";
+  }
+
+  return DeclName;
+}
+
+/// ParseTemplateArgList - Read a template argument list, which is a non-empty
+/// sequence of template-declarations in <>'s.  If CurRec is non-null, these are
+/// template args for a def, which may or may not be in a multiclass.  If null,
+/// these are the template args for a multiclass.
+///
+///    TemplateArgList ::= '<' Declaration (',' Declaration)* '>'
+///
+bool TGParser::ParseTemplateArgList(Record *CurRec) {
+  assert(Lex.getCode() == tgtok::less && "Not a template arg list!");
+  Lex.Lex(); // eat the '<'
+
+  Record *TheRecToAddTo = CurRec ? CurRec : &CurMultiClass->Rec;
+
+  // Read the first declaration.
+  std::string TemplArg = ParseDeclaration(CurRec, true/*templateargs*/);
+  if (TemplArg.empty())
+    return true;
+
+  TheRecToAddTo->addTemplateArg(TemplArg);
+
+  while (Lex.getCode() == tgtok::comma) {
+    Lex.Lex(); // eat the ','
+
+    // Read the following declarations.
+    TemplArg = ParseDeclaration(CurRec, true/*templateargs*/);
+    if (TemplArg.empty())
+      return true;
+    TheRecToAddTo->addTemplateArg(TemplArg);
+  }
+
+  if (Lex.getCode() != tgtok::greater)
+    return TokError("expected '>' at end of template argument list");
+  Lex.Lex(); // eat the '>'.
+  return false;
+}
+
+
+/// ParseBodyItem - Parse a single item at within the body of a def or class.
+///
+///   BodyItem ::= Declaration ';'
+///   BodyItem ::= LET ID OptionalBitList '=' Value ';'
+bool TGParser::ParseBodyItem(Record *CurRec) {
+  if (Lex.getCode() != tgtok::Let) {
+    if (ParseDeclaration(CurRec, false).empty())
+      return true;
+
+    if (Lex.getCode() != tgtok::semi)
+      return TokError("expected ';' after declaration");
+    Lex.Lex();
+    return false;
+  }
+
+  // LET ID OptionalRangeList '=' Value ';'
+  if (Lex.Lex() != tgtok::Id)
+    return TokError("expected field identifier after let");
+
+  SMLoc IdLoc = Lex.getLoc();
+  std::string FieldName = Lex.getCurStrVal();
+  Lex.Lex();  // eat the field name.
+
+  std::vector<unsigned> BitList;
+  if (ParseOptionalBitList(BitList))
+    return true;
+  std::reverse(BitList.begin(), BitList.end());
+
+  if (Lex.getCode() != tgtok::equal)
+    return TokError("expected '=' in let expression");
+  Lex.Lex();  // eat the '='.
+
+  RecordVal *Field = CurRec->getValue(FieldName);
+  if (Field == 0)
+    return TokError("Value '" + FieldName + "' unknown!");
+
+  RecTy *Type = Field->getType();
+
+  Init *Val = ParseValue(CurRec, Type);
+  if (Val == 0) return true;
+
+  if (Lex.getCode() != tgtok::semi)
+    return TokError("expected ';' after let expression");
+  Lex.Lex();
+
+  return SetValue(CurRec, IdLoc, FieldName, BitList, Val);
+}
+
+/// ParseBody - Read the body of a class or def.  Return true on error, false on
+/// success.
+///
+///   Body     ::= ';'
+///   Body     ::= '{' BodyList '}'
+///   BodyList BodyItem*
+///
+bool TGParser::ParseBody(Record *CurRec) {
+  // If this is a null definition, just eat the semi and return.
+  if (Lex.getCode() == tgtok::semi) {
+    Lex.Lex();
+    return false;
+  }
+
+  if (Lex.getCode() != tgtok::l_brace)
+    return TokError("Expected ';' or '{' to start body");
+  // Eat the '{'.
+  Lex.Lex();
+
+  while (Lex.getCode() != tgtok::r_brace)
+    if (ParseBodyItem(CurRec))
+      return true;
+
+  // Eat the '}'.
+  Lex.Lex();
+  return false;
+}
+
+/// ParseObjectBody - Parse the body of a def or class.  This consists of an
+/// optional ClassList followed by a Body.  CurRec is the current def or class
+/// that is being parsed.
+///
+///   ObjectBody      ::= BaseClassList Body
+///   BaseClassList   ::= /*empty*/
+///   BaseClassList   ::= ':' BaseClassListNE
+///   BaseClassListNE ::= SubClassRef (',' SubClassRef)*
+///
+bool TGParser::ParseObjectBody(Record *CurRec) {
+  // If there is a baseclass list, read it.
+  if (Lex.getCode() == tgtok::colon) {
+    Lex.Lex();
+
+    // Read all of the subclasses.
+    SubClassReference SubClass = ParseSubClassReference(CurRec, false);
+    while (1) {
+      // Check for error.
+      if (SubClass.Rec == 0) return true;
+
+      // Add it.
+      if (AddSubClass(CurRec, SubClass))
+        return true;
+
+      if (Lex.getCode() != tgtok::comma) break;
+      Lex.Lex(); // eat ','.
+      SubClass = ParseSubClassReference(CurRec, false);
+    }
+  }
+
+  // Process any variables on the let stack.
+  for (unsigned i = 0, e = LetStack.size(); i != e; ++i)
+    for (unsigned j = 0, e = LetStack[i].size(); j != e; ++j)
+      if (SetValue(CurRec, LetStack[i][j].Loc, LetStack[i][j].Name,
+                   LetStack[i][j].Bits, LetStack[i][j].Value))
+        return true;
+
+  return ParseBody(CurRec);
+}
+
+/// ParseDef - Parse and return a top level or multiclass def, return the record
+/// corresponding to it.  This returns null on error.
+///
+///   DefInst ::= DEF ObjectName ObjectBody
+///
+bool TGParser::ParseDef(MultiClass *CurMultiClass) {
+  SMLoc DefLoc = Lex.getLoc();
+  assert(Lex.getCode() == tgtok::Def && "Unknown tok");
+  Lex.Lex();  // Eat the 'def' token.
+
+  // Parse ObjectName and make a record for it.
+  Record *CurRec = new Record(ParseObjectName(), DefLoc, Records);
+
+  if (!CurMultiClass) {
+    // Top-level def definition.
+
+    // Ensure redefinition doesn't happen.
+    if (Records.getDef(CurRec->getName())) {
+      Error(DefLoc, "def '" + CurRec->getName() + "' already defined");
+      return true;
+    }
+    Records.addDef(CurRec);
+  } else {
+    // Otherwise, a def inside a multiclass, add it to the multiclass.
+    for (unsigned i = 0, e = CurMultiClass->DefPrototypes.size(); i != e; ++i)
+      if (CurMultiClass->DefPrototypes[i]->getName() == CurRec->getName()) {
+        Error(DefLoc, "def '" + CurRec->getName() +
+              "' already defined in this multiclass!");
+        return true;
+      }
+    CurMultiClass->DefPrototypes.push_back(CurRec);
+  }
+
+  if (ParseObjectBody(CurRec))
+    return true;
+
+  if (CurMultiClass == 0)  // Def's in multiclasses aren't really defs.
+    // See Record::setName().  This resolve step will see any new name
+    // for the def that might have been created when resolving
+    // inheritance, values and arguments above.
+    CurRec->resolveReferences();
+
+  // If ObjectBody has template arguments, it's an error.
+  assert(CurRec->getTemplateArgs().empty() && "How'd this get template args?");
+
+  if (CurMultiClass) {
+    // Copy the template arguments for the multiclass into the def.
+    const std::vector<std::string> &TArgs =
+                                CurMultiClass->Rec.getTemplateArgs();
+
+    for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
+      const RecordVal *RV = CurMultiClass->Rec.getValue(TArgs[i]);
+      assert(RV && "Template arg doesn't exist?");
+      CurRec->addValue(*RV);
+    }
+  }
+
+  return false;
+}
+
+
+/// ParseClass - Parse a tblgen class definition.
+///
+///   ClassInst ::= CLASS ID TemplateArgList? ObjectBody
+///
+bool TGParser::ParseClass() {
+  assert(Lex.getCode() == tgtok::Class && "Unexpected token!");
+  Lex.Lex();
+
+  if (Lex.getCode() != tgtok::Id)
+    return TokError("expected class name after 'class' keyword");
+
+  Record *CurRec = Records.getClass(Lex.getCurStrVal());
+  if (CurRec) {
+    // If the body was previously defined, this is an error.
+    if (!CurRec->getValues().empty() ||
+        !CurRec->getSuperClasses().empty() ||
+        !CurRec->getTemplateArgs().empty())
+      return TokError("Class '" + CurRec->getName() + "' already defined");
+  } else {
+    // If this is the first reference to this class, create and add it.
+    CurRec = new Record(Lex.getCurStrVal(), Lex.getLoc(), Records);
+    Records.addClass(CurRec);
+  }
+  Lex.Lex(); // eat the name.
+
+  // If there are template args, parse them.
+  if (Lex.getCode() == tgtok::less)
+    if (ParseTemplateArgList(CurRec))
+      return true;
+
+  // Finally, parse the object body.
+  return ParseObjectBody(CurRec);
+}
+
+/// ParseLetList - Parse a non-empty list of assignment expressions into a list
+/// of LetRecords.
+///
+///   LetList ::= LetItem (',' LetItem)*
+///   LetItem ::= ID OptionalRangeList '=' Value
+///
+std::vector<LetRecord> TGParser::ParseLetList() {
+  std::vector<LetRecord> Result;
+
+  while (1) {
+    if (Lex.getCode() != tgtok::Id) {
+      TokError("expected identifier in let definition");
+      return std::vector<LetRecord>();
+    }
+    std::string Name = Lex.getCurStrVal();
+    SMLoc NameLoc = Lex.getLoc();
+    Lex.Lex();  // Eat the identifier.
+
+    // Check for an optional RangeList.
+    std::vector<unsigned> Bits;
+    if (ParseOptionalRangeList(Bits))
+      return std::vector<LetRecord>();
+    std::reverse(Bits.begin(), Bits.end());
+
+    if (Lex.getCode() != tgtok::equal) {
+      TokError("expected '=' in let expression");
+      return std::vector<LetRecord>();
+    }
+    Lex.Lex();  // eat the '='.
+
+    Init *Val = ParseValue(0);
+    if (Val == 0) return std::vector<LetRecord>();
+
+    // Now that we have everything, add the record.
+    Result.push_back(LetRecord(Name, Bits, Val, NameLoc));
+
+    if (Lex.getCode() != tgtok::comma)
+      return Result;
+    Lex.Lex();  // eat the comma.
+  }
+}
+
+/// ParseTopLevelLet - Parse a 'let' at top level.  This can be a couple of
+/// different related productions. This works inside multiclasses too.
+///
+///   Object ::= LET LetList IN '{' ObjectList '}'
+///   Object ::= LET LetList IN Object
+///
+bool TGParser::ParseTopLevelLet(MultiClass *CurMultiClass) {
+  assert(Lex.getCode() == tgtok::Let && "Unexpected token");
+  Lex.Lex();
+
+  // Add this entry to the let stack.
+  std::vector<LetRecord> LetInfo = ParseLetList();
+  if (LetInfo.empty()) return true;
+  LetStack.push_back(LetInfo);
+
+  if (Lex.getCode() != tgtok::In)
+    return TokError("expected 'in' at end of top-level 'let'");
+  Lex.Lex();
+
+  // If this is a scalar let, just handle it now
+  if (Lex.getCode() != tgtok::l_brace) {
+    // LET LetList IN Object
+    if (ParseObject(CurMultiClass))
+      return true;
+  } else {   // Object ::= LETCommand '{' ObjectList '}'
+    SMLoc BraceLoc = Lex.getLoc();
+    // Otherwise, this is a group let.
+    Lex.Lex();  // eat the '{'.
+
+    // Parse the object list.
+    if (ParseObjectList(CurMultiClass))
+      return true;
+
+    if (Lex.getCode() != tgtok::r_brace) {
+      TokError("expected '}' at end of top level let command");
+      return Error(BraceLoc, "to match this '{'");
+    }
+    Lex.Lex();
+  }
+
+  // Outside this let scope, this let block is not active.
+  LetStack.pop_back();
+  return false;
+}
+
+/// ParseMultiClass - Parse a multiclass definition.
+///
+///  MultiClassInst ::= MULTICLASS ID TemplateArgList?
+///                     ':' BaseMultiClassList '{' MultiClassDef+ '}'
+///
+bool TGParser::ParseMultiClass() {
+  assert(Lex.getCode() == tgtok::MultiClass && "Unexpected token");
+  Lex.Lex();  // Eat the multiclass token.
+
+  if (Lex.getCode() != tgtok::Id)
+    return TokError("expected identifier after multiclass for name");
+  std::string Name = Lex.getCurStrVal();
+
+  if (MultiClasses.count(Name))
+    return TokError("multiclass '" + Name + "' already defined");
+
+  CurMultiClass = MultiClasses[Name] = new MultiClass(Name, 
+                                                      Lex.getLoc(), Records);
+  Lex.Lex();  // Eat the identifier.
+
+  // If there are template args, parse them.
+  if (Lex.getCode() == tgtok::less)
+    if (ParseTemplateArgList(0))
+      return true;
+
+  bool inherits = false;
+
+  // If there are submulticlasses, parse them.
+  if (Lex.getCode() == tgtok::colon) {
+    inherits = true;
+
+    Lex.Lex();
+
+    // Read all of the submulticlasses.
+    SubMultiClassReference SubMultiClass =
+      ParseSubMultiClassReference(CurMultiClass);
+    while (1) {
+      // Check for error.
+      if (SubMultiClass.MC == 0) return true;
+
+      // Add it.
+      if (AddSubMultiClass(CurMultiClass, SubMultiClass))
+        return true;
+
+      if (Lex.getCode() != tgtok::comma) break;
+      Lex.Lex(); // eat ','.
+      SubMultiClass = ParseSubMultiClassReference(CurMultiClass);
+    }
+  }
+
+  if (Lex.getCode() != tgtok::l_brace) {
+    if (!inherits)
+      return TokError("expected '{' in multiclass definition");
+    else if (Lex.getCode() != tgtok::semi)
+      return TokError("expected ';' in multiclass definition");
+    else
+      Lex.Lex();  // eat the ';'.
+  } else {
+    if (Lex.Lex() == tgtok::r_brace)  // eat the '{'.
+      return TokError("multiclass must contain at least one def");
+
+    while (Lex.getCode() != tgtok::r_brace) {
+      switch (Lex.getCode()) {
+        default:
+          return TokError("expected 'let', 'def' or 'defm' in multiclass body");
+        case tgtok::Let:
+        case tgtok::Def:
+        case tgtok::Defm:
+          if (ParseObject(CurMultiClass))
+            return true;
+         break;
+      }
+    }
+    Lex.Lex();  // eat the '}'.
+  }
+
+  CurMultiClass = 0;
+  return false;
+}
+
+/// ParseDefm - Parse the instantiation of a multiclass.
+///
+///   DefMInst ::= DEFM ID ':' DefmSubClassRef ';'
+///
+bool TGParser::ParseDefm(MultiClass *CurMultiClass) {
+  assert(Lex.getCode() == tgtok::Defm && "Unexpected token!");
+
+  std::string DefmPrefix;
+  if (Lex.Lex() == tgtok::Id) {  // eat the defm.
+    DefmPrefix = Lex.getCurStrVal();
+    Lex.Lex();  // Eat the defm prefix.
+  }
+
+  SMLoc DefmPrefixLoc = Lex.getLoc();
+  if (Lex.getCode() != tgtok::colon)
+    return TokError("expected ':' after defm identifier");
+
+  // Keep track of the new generated record definitions.
+  std::vector<Record*> NewRecDefs;
+
+  // This record also inherits from a regular class (non-multiclass)?
+  bool InheritFromClass = false;
+
+  // eat the colon.
+  Lex.Lex();
+
+  SMLoc SubClassLoc = Lex.getLoc();
+  SubClassReference Ref = ParseSubClassReference(0, true);
+
+  while (1) {
+    if (Ref.Rec == 0) return true;
+
+    // To instantiate a multiclass, we need to first get the multiclass, then
+    // instantiate each def contained in the multiclass with the SubClassRef
+    // template parameters.
+    MultiClass *MC = MultiClasses[Ref.Rec->getName()];
+    assert(MC && "Didn't lookup multiclass correctly?");
+    std::vector<Init*> &TemplateVals = Ref.TemplateArgs;
+
+    // Verify that the correct number of template arguments were specified.
+    const std::vector<std::string> &TArgs = MC->Rec.getTemplateArgs();
+    if (TArgs.size() < TemplateVals.size())
+      return Error(SubClassLoc,
+                   "more template args specified than multiclass expects");
+
+    // Loop over all the def's in the multiclass, instantiating each one.
+    for (unsigned i = 0, e = MC->DefPrototypes.size(); i != e; ++i) {
+      Record *DefProto = MC->DefPrototypes[i];
+
+      // Add in the defm name.  If the defm prefix is empty, give each
+      // instantiated def a unique name.  Otherwise, if "#NAME#" exists in the
+      // name, substitute the prefix for #NAME#.  Otherwise, use the defm name
+      // as a prefix.
+      std::string DefName = DefProto->getName();
+      if (DefmPrefix.empty()) {
+        DefName = GetNewAnonymousName();
+      } else {
+        std::string::size_type idx = DefName.find("#NAME#");
+        if (idx != std::string::npos) {
+          DefName.replace(idx, 6, DefmPrefix);
+        } else {
+          // Add the suffix to the defm name to get the new name.
+          DefName = DefmPrefix + DefName;
+        }
+      }
+
+      Record *CurRec = new Record(DefName, DefmPrefixLoc, Records);
+
+      SubClassReference Ref;
+      Ref.RefLoc = DefmPrefixLoc;
+      Ref.Rec = DefProto;
+      AddSubClass(CurRec, Ref);
+
+      // Loop over all of the template arguments, setting them to the specified
+      // value or leaving them as the default if necessary.
+      for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
+        // Check if a value is specified for this temp-arg.
+        if (i < TemplateVals.size()) {
+          // Set it now.
+          if (SetValue(CurRec, DefmPrefixLoc, TArgs[i], std::vector<unsigned>(),
+                       TemplateVals[i]))
+            return true;
+
+          // Resolve it next.
+          CurRec->resolveReferencesTo(CurRec->getValue(TArgs[i]));
+
+          // Now remove it.
+          CurRec->removeValue(TArgs[i]);
+
+        } else if (!CurRec->getValue(TArgs[i])->getValue()->isComplete()) {
+          return Error(SubClassLoc,
+                       "value not specified for template argument #"+
+                       utostr(i) + " (" + TArgs[i] + ") of multiclassclass '" +
+                       MC->Rec.getName() + "'");
+        }
+      }
+
+      // If the mdef is inside a 'let' expression, add to each def.
+      for (unsigned i = 0, e = LetStack.size(); i != e; ++i)
+        for (unsigned j = 0, e = LetStack[i].size(); j != e; ++j)
+          if (SetValue(CurRec, LetStack[i][j].Loc, LetStack[i][j].Name,
+                       LetStack[i][j].Bits, LetStack[i][j].Value)) {
+            Error(DefmPrefixLoc, "when instantiating this defm");
+            return true;
+          }
+
+      // Ensure redefinition doesn't happen.
+      if (Records.getDef(CurRec->getName()))
+        return Error(DefmPrefixLoc, "def '" + CurRec->getName() +
+                     "' already defined, instantiating defm with subdef '" +
+                     DefProto->getName() + "'");
+
+      // Don't create a top level definition for defm inside multiclasses,
+      // instead, only update the prototypes and bind the template args
+      // with the new created definition.
+      if (CurMultiClass) {
+        for (unsigned i = 0, e = CurMultiClass->DefPrototypes.size();
+             i != e; ++i) {
+          if (CurMultiClass->DefPrototypes[i]->getName() == CurRec->getName()) {
+            Error(DefmPrefixLoc, "defm '" + CurRec->getName() +
+                  "' already defined in this multiclass!");
+            return 0;
+          }
+        }
+        CurMultiClass->DefPrototypes.push_back(CurRec);
+
+        // Copy the template arguments for the multiclass into the new def.
+        const std::vector<std::string> &TA =
+          CurMultiClass->Rec.getTemplateArgs();
+
+        for (unsigned i = 0, e = TA.size(); i != e; ++i) {
+          const RecordVal *RV = CurMultiClass->Rec.getValue(TA[i]);
+          assert(RV && "Template arg doesn't exist?");
+          CurRec->addValue(*RV);
+        }
+      } else {
+        Records.addDef(CurRec);
+      }
+
+      NewRecDefs.push_back(CurRec);
+    }
+
+    if (Lex.getCode() != tgtok::comma) break;
+    Lex.Lex(); // eat ','.
+
+    SubClassLoc = Lex.getLoc();
+
+    // A defm can inherit from regular classes (non-multiclass) as
+    // long as they come in the end of the inheritance list.
+    InheritFromClass = (Records.getClass(Lex.getCurStrVal()) != 0);
+
+    if (InheritFromClass)
+      break;
+
+    Ref = ParseSubClassReference(0, true);
+  }
+
+  if (InheritFromClass) {
+    // Process all the classes to inherit as if they were part of a
+    // regular 'def' and inherit all record values.
+    SubClassReference SubClass = ParseSubClassReference(0, false);
+    while (1) {
+      // Check for error.
+      if (SubClass.Rec == 0) return true;
+
+      // Get the expanded definition prototypes and teach them about
+      // the record values the current class to inherit has
+      for (unsigned i = 0, e = NewRecDefs.size(); i != e; ++i) {
+        Record *CurRec = NewRecDefs[i];
+
+        // Add it.
+        if (AddSubClass(CurRec, SubClass))
+          return true;
+
+        // Process any variables on the let stack.
+        for (unsigned i = 0, e = LetStack.size(); i != e; ++i)
+          for (unsigned j = 0, e = LetStack[i].size(); j != e; ++j)
+            if (SetValue(CurRec, LetStack[i][j].Loc, LetStack[i][j].Name,
+                         LetStack[i][j].Bits, LetStack[i][j].Value))
+              return true;
+      }
+
+      if (Lex.getCode() != tgtok::comma) break;
+      Lex.Lex(); // eat ','.
+      SubClass = ParseSubClassReference(0, false);
+    }
+  }
+
+  if (!CurMultiClass)
+    for (unsigned i = 0, e = NewRecDefs.size(); i != e; ++i)
+      // See Record::setName().  This resolve step will see any new
+      // name for the def that might have been created when resolving
+      // inheritance, values and arguments above.
+      NewRecDefs[i]->resolveReferences();
+
+  if (Lex.getCode() != tgtok::semi)
+    return TokError("expected ';' at end of defm");
+  Lex.Lex();
+
+  return false;
+}
+
+/// ParseObject
+///   Object ::= ClassInst
+///   Object ::= DefInst
+///   Object ::= MultiClassInst
+///   Object ::= DefMInst
+///   Object ::= LETCommand '{' ObjectList '}'
+///   Object ::= LETCommand Object
+bool TGParser::ParseObject(MultiClass *MC) {
+  switch (Lex.getCode()) {
+  default:
+    return TokError("Expected class, def, defm, multiclass or let definition");
+  case tgtok::Let:   return ParseTopLevelLet(MC);
+  case tgtok::Def:   return ParseDef(MC);
+  case tgtok::Defm:  return ParseDefm(MC);
+  case tgtok::Class: return ParseClass();
+  case tgtok::MultiClass: return ParseMultiClass();
+  }
+}
+
+/// ParseObjectList
+///   ObjectList :== Object*
+bool TGParser::ParseObjectList(MultiClass *MC) {
+  while (isObjectStart(Lex.getCode())) {
+    if (ParseObject(MC))
+      return true;
+  }
+  return false;
+}
+
+bool TGParser::ParseFile() {
+  Lex.Lex(); // Prime the lexer.
+  if (ParseObjectList()) return true;
+
+  // If we have unread input at the end of the file, report it.
+  if (Lex.getCode() == tgtok::Eof)
+    return false;
+
+  return TokError("Unexpected input at top level");
+}
+
diff --git a/lib/TableGen/TGParser.h b/lib/TableGen/TGParser.h
new file mode 100644
index 00000000000..b408c80b7a1
--- /dev/null
+++ b/lib/TableGen/TGParser.h
@@ -0,0 +1,122 @@
+//===- TGParser.h - Parser for TableGen Files -------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This class represents the Parser for tablegen files.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef TGPARSER_H
+#define TGPARSER_H
+
+#include "TGLexer.h"
+#include "llvm/TableGen/Error.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/Support/SourceMgr.h"
+#include <map>
+
+namespace llvm {
+  class Record;
+  class RecordVal;
+  class RecordKeeper;
+  class RecTy;
+  class Init;
+  struct MultiClass;
+  struct SubClassReference;
+  struct SubMultiClassReference;
+  
+  struct LetRecord {
+    std::string Name;
+    std::vector<unsigned> Bits;
+    Init *Value;
+    SMLoc Loc;
+    LetRecord(const std::string &N, const std::vector<unsigned> &B, Init *V,
+              SMLoc L)
+      : Name(N), Bits(B), Value(V), Loc(L) {
+    }
+  };
+  
+class TGParser {
+  TGLexer Lex;
+  std::vector<std::vector<LetRecord> > LetStack;
+  std::map<std::string, MultiClass*> MultiClasses;
+  
+  /// CurMultiClass - If we are parsing a 'multiclass' definition, this is the 
+  /// current value.
+  MultiClass *CurMultiClass;
+
+  // Record tracker
+  RecordKeeper &Records;
+public:
+  TGParser(SourceMgr &SrcMgr, RecordKeeper &records) : 
+    Lex(SrcMgr), CurMultiClass(0), Records(records) {}
+  
+  /// ParseFile - Main entrypoint for parsing a tblgen file.  These parser
+  /// routines return true on error, or false on success.
+  bool ParseFile();
+  
+  bool Error(SMLoc L, const Twine &Msg) const {
+    PrintError(L, Msg);
+    return true;
+  }
+  bool TokError(const Twine &Msg) const {
+    return Error(Lex.getLoc(), Msg);
+  }
+  const std::vector<std::string> &getDependencies() const {
+    return Lex.getDependencies();
+  }
+private:  // Semantic analysis methods.
+  bool AddValue(Record *TheRec, SMLoc Loc, const RecordVal &RV);
+  bool SetValue(Record *TheRec, SMLoc Loc, const std::string &ValName, 
+                const std::vector<unsigned> &BitList, Init *V);
+  bool AddSubClass(Record *Rec, SubClassReference &SubClass);
+  bool AddSubMultiClass(MultiClass *CurMC,
+                        SubMultiClassReference &SubMultiClass);
+
+private:  // Parser methods.
+  bool ParseObjectList(MultiClass *MC = 0);
+  bool ParseObject(MultiClass *MC);
+  bool ParseClass();
+  bool ParseMultiClass();
+  bool ParseDefm(MultiClass *CurMultiClass);
+  bool ParseDef(MultiClass *CurMultiClass);
+  bool ParseTopLevelLet(MultiClass *CurMultiClass);
+  std::vector<LetRecord> ParseLetList();
+
+  bool ParseObjectBody(Record *CurRec);
+  bool ParseBody(Record *CurRec);
+  bool ParseBodyItem(Record *CurRec);
+
+  bool ParseTemplateArgList(Record *CurRec);
+  std::string ParseDeclaration(Record *CurRec, bool ParsingTemplateArgs);
+
+  SubClassReference ParseSubClassReference(Record *CurRec, bool isDefm);
+  SubMultiClassReference ParseSubMultiClassReference(MultiClass *CurMC);
+
+  Init *ParseIDValue(Record *CurRec);
+  Init *ParseIDValue(Record *CurRec, const std::string &Name, SMLoc NameLoc);
+  Init *ParseSimpleValue(Record *CurRec, RecTy *ItemType = 0);
+  Init *ParseValue(Record *CurRec, RecTy *ItemType = 0);
+  std::vector<Init*> ParseValueList(Record *CurRec, Record *ArgsRec = 0, RecTy *EltTy = 0);
+  std::vector<std::pair<llvm::Init*, std::string> > ParseDagArgList(Record *);
+  bool ParseOptionalRangeList(std::vector<unsigned> &Ranges);
+  bool ParseOptionalBitList(std::vector<unsigned> &Ranges);
+  std::vector<unsigned> ParseRangeList();
+  bool ParseRangePiece(std::vector<unsigned> &Ranges);
+  RecTy *ParseType();
+  Init *ParseOperation(Record *CurRec);
+  RecTy *ParseOperatorType();
+  std::string ParseObjectName();
+  Record *ParseClassID();
+  MultiClass *ParseMultiClassID();
+  Record *ParseDefmID();
+};
+  
+} // end namespace llvm
+
+#endif
diff --git a/lib/TableGen/TableGenBackend.cpp b/lib/TableGen/TableGenBackend.cpp
new file mode 100644
index 00000000000..29588db324c
--- /dev/null
+++ b/lib/TableGen/TableGenBackend.cpp
@@ -0,0 +1,25 @@
+//===- TableGenBackend.cpp - Base class for TableGen Backends ---*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides useful services for TableGen backends...
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/TableGen/TableGenBackend.h"
+#include "llvm/TableGen/Record.h"
+using namespace llvm;
+
+void TableGenBackend::EmitSourceFileHeader(const std::string &Desc,
+                                           raw_ostream &OS) const {
+  OS << "//===- TableGen'erated file -------------------------------------*-"
+       " C++ -*-===//\n//\n// " << Desc << "\n//\n// Automatically generate"
+       "d file, do not edit!\n//\n//===------------------------------------"
+       "----------------------------------===//\n\n";
+}
+