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

1 files changed, 2163 insertions, 0 deletions

diff --git a/lib/TableGen/TGParser.cpp b/lib/TableGen/TGParser.cpp
new file mode 100644
index 0000000000..1601a530b1
--- /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 += L