Initial checkin of TableGen utility

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

6 files changed, 1704 insertions, 0 deletions

diff --git a/utils/TableGen/FileLexer.l b/utils/TableGen/FileLexer.l
new file mode 100644
index 0000000000..c7e4346c0f
--- /dev/null
+++ b/utils/TableGen/FileLexer.l
@@ -0,0 +1,66 @@
+/*===-- FileLexer.l - Scanner for TableGen Files ----------------*- C++ -*-===//
+//
+//
+//===------------------------------------------------------------------------=*/
+
+%option prefix="File"
+%option yylineno
+%option nostdinit
+%option never-interactive
+%option batch
+%option noyywrap
+%option nodefault
+%option 8bit
+%option outfile="Lexer.cpp"
+%option ecs
+%option noreject
+%option noyymore
+
+
+%{
+#include "Record.h"
+typedef std::pair<Record*, std::vector<Init*>*> SubClassRefTy;
+#include "FileParser.h"
+
+// ParseInt - This has to handle the special case of binary numbers 0b0101
+static int ParseInt(const char *Str) {
+  if (Str[0] == '0' && Str[1] == 'b')
+    return strtol(Str+2, 0, 2);
+  return strtol(Str, 0, 0); 
+}
+
+%}
+
+Comment     \/\/.*
+
+Identifier  [a-zA-Z_][0-9a-zA-Z_]*
+Integer     [-+]?[0-9]+|0x[0-9a-fA-F]+|0b[01]+
+StringVal   \"[^"]*\"
+
+%%
+
+{Comment}      { /* Ignore comments */ }
+
+int            { return INT; }
+bit            { return BIT; }
+bits           { return BITS; }
+string         { return STRING; }
+list           { return LIST; }
+
+class          { return CLASS; }
+def            { return DEF; }
+field          { return FIELD; }
+set            { return SET; }
+in             { return IN; }
+
+{Identifier}   { Filelval.StrVal = new std::string(yytext, yytext+yyleng);
+                 return ID; }
+
+{StringVal}    { Filelval.StrVal = new std::string(yytext+1, yytext+yyleng-1);
+                 return STRVAL; }
+
+{Integer}      { Filelval.IntVal = ParseInt(Filetext); return INTVAL; }
+
+[ \t\n]+       { /* Ignore whitespace */ }
+.              { return Filetext[0]; }
+%%
diff --git a/utils/TableGen/FileParser.y b/utils/TableGen/FileParser.y
new file mode 100644
index 0000000000..624a797895
--- /dev/null
+++ b/utils/TableGen/FileParser.y
@@ -0,0 +1,445 @@
+//===-- FileParser.y - Parser for TableGen files ----------------*- C++ -*-===//
+//
+//  This file implements the bison parser for Table Generator files...
+//
+//===------------------------------------------------------------------------=//
+
+%{
+#include "Record.h"
+#include <iostream>
+#include <algorithm>
+#include <string>
+#include <stdio.h>
+#define YYERROR_VERBOSE 1
+
+int yyerror(const char *ErrorMsg);
+int yylex();
+extern FILE *Filein;
+extern int Filelineno;
+int Fileparse();
+static Record *CurRec = 0;
+
+typedef std::pair<Record*, std::vector<Init*>*> SubClassRefTy;
+
+static std::vector<std::pair<std::pair<std::string, std::vector<unsigned>*>,
+                             Init*> > SetStack;
+
+void ParseFile() {
+  FILE *F = stdin;
+
+  Filein = F;
+  Filelineno = 1;
+  Fileparse();
+  Filein = stdin;
+}
+
+static std::ostream &err() {
+  return std::cerr << "Parsing Line #" << Filelineno << ": ";
+}
+
+static void addValue(const RecordVal &RV) {
+  if (CurRec->getValue(RV.getName())) {
+    err() << "Value '" << RV.getName() << "' multiply defined!\n";
+    abort();
+  }
+
+  CurRec->addValue(RV);
+}
+
+static void addSuperClass(Record *SC) {
+  if (CurRec->isSubClassOf(SC)) {
+    err() << "Already subclass of '" << SC->getName() << "'!\n";
+    abort();
+  }
+  CurRec->addSuperClass(SC);
+}
+
+static void setValue(const std::string &ValName, 
+		     std::vector<unsigned> *BitList, Init *V) {
+  if (!V) return ;
+
+  RecordVal *RV = CurRec->getValue(ValName);
+  if (RV == 0) {
+    err() << "Value '" << ValName << "' unknown!\n";
+    abort();
+  }
+  
+  // 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) {
+    BitsInit *CurVal = dynamic_cast<BitsInit*>(RV->getValue());
+    if (CurVal == 0) {
+      err() << "Value '" << ValName << "' is not a bits type!\n";
+      abort();
+    }
+
+    // Convert the incoming value to a bits type of the appropriate size...
+    Init *BI = V->convertInitializerTo(new BitsRecTy(BitList->size()));
+    if (BI == 0) {
+      V->convertInitializerTo(new BitsRecTy(BitList->size()));
+      err() << "Initializer '" << *V << "' not compatible with bit range!\n";
+      abort();
+    }
+
+    // We should have a BitsInit type now...
+    assert(dynamic_cast<BitsInit*>(BI) != 0 || &(std::cerr << *BI) == 0);
+    BitsInit *BInit = (BitsInit*)BI;
+
+    BitsInit *NewVal = new BitsInit(CurVal->getNumBits());
+
+    for (unsigned i = 0, e = CurVal->getNumBits(); i != e; ++i)
+      NewVal->setBit(i, CurVal->getBit(i));
+
+    // Loop over bits, assigning values as appopriate...
+    for (unsigned i = 0, e = BitList->size(); i != e; ++i) {
+      unsigned Bit = (*BitList)[i];
+      NewVal->setBit(Bit, BInit->getBit(i));
+    }
+    V = NewVal;
+  }
+
+  if (RV->setValue(V)) {
+    err() << "Value '" << ValName << "' of type '" << *RV->getType()
+	  << "' is incompatible with initializer '" << *V << "'!\n";
+    abort();
+  }
+}
+
+static void addSubClass(Record *SC, const std::vector<Init*> &TemplateArgs) {
+  // 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)
+    addValue(Vals[i]);
+
+  const std::vector<std::string> &TArgs = SC->getTemplateArgs();
+
+  // Ensure that an appropriate number of template arguments are specified...
+  if (TArgs.size() < TemplateArgs.size()) {
+    err() << "ERROR: More template args specified thang expected!\n";
+    abort();
+  } else {    // This class expects template arguments...
+    // Loop over all of the template arguments, setting them to the specified
+    // value or leaving them as the default as neccesary.
+    for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
+      if (i < TemplateArgs.size()) {  // A value is specified for this temp-arg?
+	// Set it now.
+	setValue(TArgs[i], 0, TemplateArgs[i]);
+      } else if (!CurRec->getValue(TArgs[i])->getValue()->isComplete()) {
+	err() << "ERROR: Value not specified for template argument #"
+	      << i << " (" << TArgs[i] << ") of subclass '" << SC->getName()
+	      << "'!\n";
+	abort();
+      }
+    }
+  }
+
+
+  // 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)
+    addSuperClass(SCs[i]);
+  addSuperClass(SC);
+}
+
+
+%}
+
+%union {
+  std::string          *StrVal;
+  int                   IntVal;
+  RecTy                *Ty;
+  Init                 *Initializer;
+  std::vector<Init*>   *FieldList;
+  std::vector<Record*> *RecPtr;
+  std::vector<unsigned>*BitList;
+  Record               *Rec;
+  SubClassRefTy        *SubClassRef;
+  std::vector<SubClassRefTy> *SubClassList;
+};
+
+%token INT BIT STRING BITS LIST CLASS DEF FIELD SET IN
+%token <IntVal>      INTVAL
+%token <StrVal>      ID STRVAL
+
+%type <Ty>           Type
+%type <RecPtr>       DefList DefListNE
+%type <Rec>          ClassInst DefInst Object ObjectBody ClassID DefID
+
+%type <SubClassRef>  SubClassRef
+%type <SubClassList> ClassList ClassListNE
+%type <IntVal>       OptPrefix
+%type <Initializer>  Value OptValue
+%type <FieldList>    ValueList ValueListNE
+%type <BitList>      BitList OptBitList RBitList
+%type <StrVal>       Declaration
+
+%start File
+%%
+
+ClassID : ID {
+    $$ = Records.getClass(*$1);
+    if ($$ == 0) {
+      err() << "Couldn't find class '" << *$1 << "'!\n";
+      abort();
+    }
+    delete $1;
+  };
+
+DefID : ID {
+    $$ = Records.getDef(*$1);
+    if ($$ == 0) {
+      err() << "Couldn't find def '" << *$1 << "'!\n";
+      abort();
+    }
+    delete $1;
+  };
+
+
+// TableGen types...
+Type : STRING {                       // string type
+    $$ = new StringRecTy();
+  } | BIT {                           // bit type
+    $$ = new BitRecTy();
+  } | BITS '<' INTVAL '>' {           // bits<x> type
+    $$ = new BitsRecTy($3);
+  } | INT {                           // int type
+    $$ = new IntRecTy();
+  } | LIST '<' ClassID '>' {          // list<x> type
+    $$ = new ListRecTy($3);
+  } | ClassID {                       // Record Type
+    $$ = new RecordRecTy($1);
+  };
+
+OptPrefix : /*empty*/ { $$ = 0; } | FIELD { $$ = 1; };
+
+OptValue : /*empty*/ { $$ = 0; } | '=' Value { $$ = $2; };
+
+Value : INTVAL {
+    $$ = new IntInit($1);
+  } | STRVAL {
+    $$ = new StringInit(*$1);
+    delete $1;
+  } | '?' {
+    $$ = new UnsetInit();
+  } | '{' ValueList '}' {
+    BitsInit *Init = new BitsInit($2->size());
+    for (unsigned i = 0, e = $2->size(); i != e; ++i) {
+      struct Init *Bit = (*$2)[i]->convertInitializerTo(new BitRecTy());
+      if (Bit == 0) {
+	err() << "Element #" << i << " (" << *(*$2)[i]
+	      << ") is not convertable to a bit!\n";
+	abort();
+      }
+      Init->setBit($2->size()-i-1, Bit);
+    }
+    $$ = Init;
+    delete $2;
+  } | ID {
+    if (const RecordVal *RV = CurRec->getValue(*$1)) {
+      $$ = new VarInit(*$1, RV->getType());
+    } else if (Record *D = Records.getDef(*$1)) {
+      $$ = new DefInit(D);
+    } else {
+      err() << "Variable not defined: '" << *$1 << "'!\n";
+      abort();
+    }
+    
+    delete $1;
+  } | Value '{' BitList '}' {
+    $$ = $1->convertInitializerBitRange(*$3);
+    if ($$ == 0) {
+      err() << "Invalid bit range for value '" << *$1 << "'!\n";
+      abort();
+    }
+    delete $3;
+  } | '[' DefList ']' {
+    $$ = new ListInit(*$2);
+    delete $2;
+  };
+
+DefList : /*empty */ {
+    $$ = new std::vector<Record*>();
+  } | DefListNE {
+    $$ = $1;
+  };
+DefListNE : DefID {
+    $$ = new std::vector<Record*>();
+    $$->push_back($1);
+  } | DefListNE ',' DefID {
+    ($$=$1)->push_back($3);
+  };
+
+
+RBitList : INTVAL {
+    $$ = new std::vector<unsigned>();
+    $$->push_back($1);
+  } | INTVAL '-' INTVAL {
+    if ($1 < $3 || $1 < 0 || $3 < 0) {
+      err() << "Invalid bit range: " << $1 << "-" << $3 << "!\n";
+      abort();
+    }
+    $$ = new std::vector<unsigned>();
+    for (int i = $1; i >= $3; --i)
+      $$->push_back(i);
+  } | INTVAL INTVAL {
+    $2 = -$2;
+    if ($1 < $2 || $1 < 0 || $2 < 0) {
+      err() << "Invalid bit range: " << $1 << "-" << $2 << "!\n";
+      abort();
+    }
+    $$ = new std::vector<unsigned>();
+    for (int i = $1; i >= $2; --i)
+      $$->push_back(i);
+  } | RBitList ',' INTVAL {
+    ($$=$1)->push_back($3);
+  } | RBitList ',' INTVAL '-' INTVAL {
+    if ($3 < $5 || $3 < 0 || $5 < 0) {
+      err() << "Invalid bit range: " << $3 << "-" << $5 << "!\n";
+      abort();
+    }
+    $$ = $1;
+    for (int i = $3; i >= $5; --i)
+      $$->push_back(i);
+  } | RBitList ',' INTVAL INTVAL {
+    $4 = -$4;
+    if ($3 < $4 || $3 < 0 || $4 < 0) {
+      err() << "Invalid bit range: " << $3 << "-" << $4 << "!\n";
+      abort();
+    }
+    $$ = $1;
+    for (int i = $3; i >= $4; --i)
+      $$->push_back(i);
+  };
+
+BitList : RBitList { $$ = $1; std::reverse($1->begin(), $1->end()); };
+
+OptBitList : /*empty*/ { $$ = 0; } | '{' BitList '}' { $$ = $2; };
+
+
+
+ValueList : /*empty*/ {
+    $$ = new std::vector<Init*>();
+  } | ValueListNE {
+    $$ = $1;
+  };
+
+ValueListNE : Value {
+    $$ = new std::vector<Init*>();
+    $$->push_back($1);
+  } | ValueListNE ',' Value {
+    ($$ = $1)->push_back($3);
+  };
+
+Declaration : OptPrefix Type ID OptValue {
+  addValue(RecordVal(*$3, $2, $1));
+  setValue(*$3, 0, $4);
+  $$ = $3;
+};
+
+BodyItem : Declaration ';' {
+  delete $1;
+} | SET ID OptBitList '=' Value ';' {
+  setValue(*$2, $3, $5);
+  delete $2;
+  delete $3;
+};
+
+BodyList : /*empty*/ | BodyList BodyItem;
+Body : ';' | '{' BodyList '}';
+
+SubClassRef : ClassID {
+    $$ = new SubClassRefTy($1, new std::vector<Init*>());
+  } | ClassID '<' ValueListNE '>' {
+    $$ = new SubClassRefTy($1, $3);
+  };
+
+ClassListNE : SubClassRef {
+    $$ = new std::vector<SubClassRefTy>();
+    $$->push_back(*$1);
+    delete $1;
+  }
+  | ClassListNE ',' SubClassRef {
+    ($$=$1)->push_back(*$3);
+    delete $3;
+  };
+
+ClassList : /*empty */ {
+    $$ = new std::vector<SubClassRefTy>();
+  }
+  | ':' ClassListNE {
+    $$ = $2;
+  };
+
+DeclListNE : Declaration {
+  CurRec->addTemplateArg(*$1);
+  delete $1;
+} | DeclListNE ',' Declaration {
+  CurRec->addTemplateArg(*$3);
+  delete $3;
+};
+
+TemplateArgList : '<' DeclListNE '>' {};
+OptTemplateArgList : /*empty*/ | TemplateArgList;
+
+ObjectBody : ID {
+           CurRec = new Record(*$1);
+           delete $1;
+         } OptTemplateArgList ClassList {
+           for (unsigned i = 0, e = $4->size(); i != e; ++i) {
+	     addSubClass((*$4)[i].first, *(*$4)[i].second);
+	     delete (*$4)[i].second;  // Delete the template list
+	   }
+           delete $4;
+
+	   // Process any variables on the set stack...
+	   for (unsigned i = 0, e = SetStack.size(); i != e; ++i)
+	     setValue(SetStack[i].first.first, SetStack[i].first.second,
+		      SetStack[i].second);
+         } Body {
+  CurRec->resolveReferences();
+  $$ = CurRec;
+  CurRec = 0;
+};
+
+ClassInst : CLASS ObjectBody {
+  if (Records.getClass($2->getName())) {
+    err() << "Class '" << $2->getName() << "' already defined!\n";
+    abort();
+  }
+  Records.addClass($$ = $2);
+};
+
+DefInst : DEF ObjectBody {
+  // TODO: If ObjectBody has template arguments, it's an error.
+  if (Records.getDef($2->getName())) {
+    err() << "Def '" << $2->getName() << "' already defined!\n";
+    abort();
+  }
+  Records.addDef($$ = $2);
+};
+
+
+Object : ClassInst | DefInst;
+
+// Support Set commands wrapping objects...
+Object : SET ID OptBitList '=' Value IN {
+            SetStack.push_back(std::make_pair(std::make_pair(*$2, $3), $5));
+	    delete $2;
+          } '{' ObjectList '}' {
+	    delete SetStack.back().first.second; // Delete OptBitList
+	    SetStack.pop_back();
+  };
+
+ObjectList : Object {} | ObjectList Object {};
+
+File : ObjectList {};
+
+%%
+
+int yyerror(const char *ErrorMsg) {
+  err() << "Error parsing: " << ErrorMsg << "\n";
+  abort();
+}
diff --git a/utils/TableGen/Makefile b/utils/TableGen/Makefile
new file mode 100644
index 0000000000..a9c235037e
--- /dev/null
+++ b/utils/TableGen/Makefile
@@ -0,0 +1,23 @@
+LEVEL = ../..
+TOOLNAME = tblgen
+USEDLIBS = support.a
+
+include $(LEVEL)/Makefile.common
+
+clean::
+	-rm -f FileParser.cpp FileParser.h FileLexer.cpp CommandLine.cpp
+	-rm -f FileParser.output
+
+test::
+	$(TOOLEXENAME_G) < X86.td
+	# -parse
+
+	@echo "enum {"
+	@$(TOOLEXENAME_G) < X86.td -class=Register
+	@echo 
+	@echo "};"
+
+	@echo "enum {"
+	@$(TOOLEXENAME_G) < X86.td -class=Instruction
+	@echo 
+	@echo "};"
diff --git a/utils/TableGen/Record.cpp b/utils/TableGen/Record.cpp
new file mode 100644
index 0000000000..8324bad5c1
--- /dev/null
+++ b/utils/TableGen/Record.cpp
@@ -0,0 +1,371 @@
+//===- Record.cpp - Record implementation ---------------------------------===//
+//
+//
+//===----------------------------------------------------------------------===//
+
+#include "Record.h"
+
+//===----------------------------------------------------------------------===//
+//    Type implementations
+//===----------------------------------------------------------------------===//
+
+void RecTy::dump() const { print(std::cerr); }
+
+Init *BitRecTy::convertValue(BitsInit *BI) {
+  if (BI->getNumBits() != 1) return 0; // Only accept if just one bit!
+  return BI->getBit(0);
+}
+
+Init *BitRecTy::convertValue(IntInit *II) {
+  int Val = II->getValue();
+  if (Val != 0 && Val != 1) return 0;  // Only accept 0 or 1 for a bit!
+  delete II;
+  
+  return new BitInit(Val != 0); 
+}
+
+Init *BitRecTy::convertValue(VarInit *VI) {
+  if (dynamic_cast<BitRecTy*>(VI->getType()))
+    return VI;  // Accept variable if it is already of bit type!
+  return 0;
+}
+
+Init *BitsRecTy::convertValue(UnsetInit *UI) {
+  BitsInit *Ret = new BitsInit(Size);
+
+  for (unsigned i = 0; i != Size; ++i)
+    Ret->setBit(i, new UnsetInit());
+  return Ret;
+}
+
+Init *BitsRecTy::convertValue(BitInit *UI) {
+  if (Size != 1) return 0;  // Can only convert single bit...
+  BitsInit *Ret = new BitsInit(1);
+  Ret->setBit(0, UI);
+  return Ret;
+}
+
+// convertValue from Int initializer to bits type: Split the integer up into the
+// appropriate bits...
+//
+Init *BitsRecTy::convertValue(IntInit *II) {
+  int Value = II->getValue();
+  delete II;
+
+  BitsInit *Ret = new BitsInit(Size);
+  for (unsigned i = 0; i != Size; ++i)
+    Ret->setBit(i, new BitInit(Value & (1 << i)));
+  return Ret;
+}
+
+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(VarInit *VI) {
+  if (BitsRecTy *BRT = dynamic_cast<BitsRecTy*>(VI->getType()))
+    if (BRT->Size == Size) {
+      BitsInit *Ret = new BitsInit(Size);
+      for (unsigned i = 0; i != Size; ++i)
+	Ret->setBit(i, new VarBitInit(VI, i));
+      return Ret;
+    }
+  if (Size == 1 && dynamic_cast<BitRecTy*>(VI->getType())) {
+    BitsInit *Ret = new BitsInit(1);
+    Ret->setBit(0, VI);
+    return Ret;
+  }
+      
+  return 0;
+}
+
+
+Init *IntRecTy::convertValue(BitsInit *BI) {
+  int 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 new IntInit(Result);
+}
+
+Init *IntRecTy::convertValue(VarInit *VI) {
+  if (dynamic_cast<IntRecTy*>(VI->getType()))
+    return VI;  // Accept variable if already of the right type!
+  return 0;
+}
+
+Init *StringRecTy::convertValue(VarInit *VI) {
+  if (dynamic_cast<StringRecTy*>(VI->getType()))
+    return VI;  // Accept variable if already of the right type!
+  return 0;
+}
+
+void ListRecTy::print(std::ostream &OS) const {
+  OS << "list<" << Class->getName() << ">";
+}
+
+Init *ListRecTy::convertValue(ListInit *LI) {
+  // Verify that all of the elements of the list are subclasses of the
+  // appopriate class!
+  for (unsigned i = 0, e = LI->getSize(); i != e; ++i)
+    if (!LI->getElement(i)->isSubClassOf(Class))
+      return 0;
+  return LI;
+}
+
+void RecordRecTy::print(std::ostream &OS) const {
+  OS << Rec->getName();
+}
+
+Init *RecordRecTy::convertValue(DefInit *DI) {
+  // Ensure that DI is a subclass of Rec.
+  if (!DI->getDef()->isSubClassOf(Rec))
+    return 0;
+  return DI;
+}
+
+//===----------------------------------------------------------------------===//
+//    Initializer implementations
+//===----------------------------------------------------------------------===//
+
+void Init::dump() const { return print(std::cerr); }
+
+Init *BitsInit::convertInitializerBitRange(const std::vector<unsigned> &Bits) {
+  BitsInit *BI = new BitsInit(Bits.size());
+  for (unsigned i = 0, e = Bits.size(); i != e; ++i) {
+    if (Bits[i] >= getNumBits()) {
+      delete BI;
+      return 0;
+    }
+    BI->setBit(i, getBit(Bits[i]));
+  }
+  return BI;
+}
+
+void BitsInit::print(std::ostream &OS) const {
+  //if (!printInHex(OS)) return;
+  if (!printAsVariable(OS)) return;
+  if (!printAsUnset(OS)) return;
+
+  OS << "{ ";
+  for (unsigned i = 0, e = getNumBits(); i != e; ++i) {
+    if (i) OS << ", ";
+    getBit(e-i-1)->print(OS);
+  }
+  OS << " }";
+}
+
+bool BitsInit::printInHex(std::ostream &OS) const {
+  // First, attempt to convert the value into an integer value...
+  int Result = 0;
+  for (unsigned i = 0, e = getNumBits(); i != e; ++i) 
+    if (BitInit *Bit = dynamic_cast<BitInit*>(getBit(i))) {
+      Result |= Bit->getValue() << i;
+    } else {
+      return true;
+    }
+
+  OS << "0x" << std::hex << Result << std::dec;
+  return false;
+}
+
+bool BitsInit::printAsVariable(std::ostream &OS) const {
+  // Get the variable that we may be set equal to...
+  assert(getNumBits() != 0);
+  VarBitInit *FirstBit = dynamic_cast<VarBitInit*>(getBit(0));
+  if (FirstBit == 0) return true;
+  VarInit *Var = FirstBit->getVariable();
+
+  // Check to make sure the types are compatible.
+  BitsRecTy *Ty = dynamic_cast<BitsRecTy*>(Var->getType());
+  if (Ty == 0) return true;
+  if (Ty->getNumBits() != getNumBits()) return true; // Incompatible types!
+
+  // Check to make sure all bits are referring to the right bits in the variable
+  for (unsigned i = 0, e = getNumBits(); i != e; ++i) {
+    VarBitInit *Bit = dynamic_cast<VarBitInit*>(getBit(i));
+    if (Bit == 0 || Bit->getVariable() != Var || Bit->getBitNum() != i)
+      return true;
+  }
+
+  OS << Var->getName();
+  return false;
+}
+
+bool BitsInit::printAsUnset(std::ostream &OS) const {
+  for (unsigned i = 0, e = getNumBits(); i != e; ++i) 
+    if (!dynamic_cast<UnsetInit*>(getBit(i)))
+      return true;
+  OS << "?";
+  return false;
+}
+
+Init *IntInit::convertInitializerBitRange(const std::vector<unsigned> &Bits) {
+  BitsInit *BI = new BitsInit(Bits.size());
+
+  for (unsigned i = 0, e = Bits.size(); i != e; ++i) {
+    if (Bits[i] >= 32) {
+      delete BI;
+      return 0;
+    }
+    BI->setBit(i, new BitInit(Value & (1 << Bits[i])));
+  }
+  return BI;
+}
+
+void ListInit::print(std::ostream &OS) const {
+  OS << "[";
+  for (unsigned i = 0, e = Records.size(); i != e; ++i) {
+    if (i) OS << ", ";
+    OS << Records[i]->getName();
+  }
+  OS << "]";
+}
+
+Init *VarInit::convertInitializerBitRange(const std::vector<unsigned> &Bits) {
+  BitsRecTy *T = dynamic_cast<BitsRecTy*>(Ty);
+  if (T == 0) return 0;  // Cannot subscript a non-bits variable...
+  unsigned NumBits = T->getNumBits();
+
+  BitsInit *BI = new BitsInit(Bits.size());
+  for (unsigned i = 0, e = Bits.size(); i != e; ++i) {
+    if (Bits[i] >= NumBits) {
+      delete BI;
+      return 0;
+    }
+    BI->setBit(i, new VarBitInit(this, Bits[i]));
+  }
+  return BI;
+}
+
+Init *BitsInit::resolveReferences(Record &R) {
+  bool Changed = false;
+  BitsInit *New = new BitsInit(getNumBits());
+
+  for (unsigned i = 0, e = Bits.size(); i != e; ++i) {
+    Init *B;
+    New->setBit(i, getBit(i));
+    do {
+      B = New->getBit(i);
+      New->setBit(i, B->resolveReferences(R));
+      Changed |= B != New->getBit(i);
+    } while (B != New->getBit(i));
+  }
+
+  if (Changed)
+    return New;
+  delete New;
+  return this;
+}
+
+
+
+Init *VarBitInit::resolveReferences(Record &R) {
+  if (R.isTemplateArg(getVariable()->getName()))
+    return this;
+
+  RecordVal *RV = R.getValue(getVariable()->getName());
+  assert(RV && "Reference to a non-existant variable?");
+  assert(dynamic_cast<BitsInit*>(RV->getValue()));
+  BitsInit *BI = (BitsInit*)RV->getValue();
+  
+  assert(getBitNum() < BI->getNumBits() && "Bit reference out of range!");
+  Init *B = BI->getBit(getBitNum());
+
+  if (!dynamic_cast<UnsetInit*>(B))  // If the bit is not set...
+    return B;                        // Replace the VarBitInit with it.
+  return this;
+}
+
+void DefInit::print(std::ostream &OS) const {
+  OS << Def->getName();
+}
+
+//===----------------------------------------------------------------------===//
+//    Other implementations
+//===----------------------------------------------------------------------===//
+
+RecordVal::RecordVal(const std::string &N, RecTy *T, unsigned P)
+  : Name(N), Ty(T), Prefix(P) {
+  Value = Ty->convertValue(new UnsetInit());
+  assert(Value && "Cannot create unset value for current type!");
+}
+
+void RecordVal::dump() const { std::cerr << *this; }
+
+void RecordVal::print(std::ostream &OS, bool PrintSem) const {
+  if (getPrefix()) OS << "field ";
+  OS << *getType() << " " << getName();
+  if (getValue()) {
+    OS << " = " << *getValue();
+  }
+  if (PrintSem) OS << ";\n";
+}
+
+// resolveReferences - If there are any field references that refer to fields
+// that have been filled in, we can propagate the values now.
+//
+void Record::resolveReferences() {
+  for (unsigned i = 0, e = Values.size(); i != e; ++i)
+    Values[i].setValue(Values[i].getValue()->resolveReferences(*this));
+}
+
+void Record::dump() const { std::cerr << *this; }
+
+std::ostream &operator<<(std::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";
+}
+
+void RecordKeeper::dump() const { std::cerr << *this; }
+
+std::ostream &operator<<(std::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;
+}
diff --git a/utils/TableGen/Record.h b/utils/TableGen/Record.h
new file mode 100644
index 0000000000..a3f8c0bd85
--- /dev/null
+++ b/utils/TableGen/Record.h
@@ -0,0 +1,448 @@
+//===- Record.h - Classes to represent Table Records ------------*- C++ -*-===//
+//
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef RECORD_H
+#define RECORD_H
+
+#include <string>
+#include <vector>
+#include <map>
+#include <iostream>
+class Init;
+class UnsetInit;
+class BitInit;
+class BitsInit;
+class IntInit;
+class StringInit;
+class ListInit;
+class VarInit;
+class VarBitInit;
+class DefInit;
+class Record;
+
+//===----------------------------------------------------------------------===//
+//  Type Classes
+//===----------------------------------------------------------------------===//
+
+struct RecTy {
+  virtual ~RecTy() {}
+
+  virtual Init *convertValue( UnsetInit *UI) { return 0; }
+  virtual Init *convertValue(   BitInit *BI) { return 0; }
+  virtual Init *convertValue(  BitsInit *BI) { return 0; }
+  virtual Init *convertValue(   IntInit *II) { return 0; }
+  virtual Init *convertValue(StringInit *SI) { return 0; }
+  virtual Init *convertValue(  ListInit *LI) { return 0; }
+  virtual Init *convertValue(   VarInit *VI) { return 0; }
+  virtual Init *convertValue(VarBitInit *VB) { return 0; }
+  virtual Init *convertValue(   DefInit *DI) { return 0; }
+
+  virtual void print(std::ostream &OS) const = 0;
+  void dump() const;
+};
+
+inline std::ostream &operator<<(std::ostream &OS, const RecTy &Ty) {
+  Ty.print(OS);
+  return OS;
+}
+
+struct BitRecTy : public RecTy {
+  Init *convertValue(UnsetInit *UI) { return (Init*)UI; }
+  Init *convertValue(BitInit *BI) { return (Init*)BI; }
+  Init *convertValue(BitsInit *BI);
+  Init *convertValue(IntInit *II);
+  Init *convertValue(VarInit *VI);
+
+  void print(std::ostream &OS) const { OS << "bit"; }
+};
+
+class BitsRecTy : public RecTy {
+  unsigned Size;
+public:
+  BitsRecTy(unsigned Sz) : Size(Sz) {}
+
+  unsigned getNumBits() const { return Size; }
+
+  Init *convertValue(UnsetInit *UI);
+  Init *convertValue(BitInit *UI);
+  Init *convertValue(BitsInit *BI);
+  Init *convertValue(IntInit *II);
+  Init *convertValue(VarInit *VI);
+
+  void print(std::ostream &OS) const { OS << "bits<" << Size << ">"; }
+};
+
+struct IntRecTy : public RecTy {
+  Init *convertValue(UnsetInit *UI) { return (Init*)UI; }
+  Init *convertValue(IntInit *II) { return (Init*)II; }
+  Init *convertValue(BitsInit *BI);
+  Init *convertValue(VarInit *VI);
+
+  void print(std::ostream &OS) const { OS << "int"; }
+};
+
+struct StringRecTy : public RecTy {
+  Init *convertValue(UnsetInit *UI) { return (Init*)UI; }
+  Init *convertValue(StringInit *SI) { return (Init*)SI; }
+  Init *convertValue(VarInit *VI);
+  void print(std::ostream &OS) const { OS << "string"; }
+};
+
+class ListRecTy : public RecTy {
+  Record *Class;
+public:
+  ListRecTy(Record *C) : Class(C) {}
+  Init *convertValue(UnsetInit *UI) { return (Init*)UI; }
+  Init *convertValue(ListInit *LI);
+  
+  void print(std::ostream &OS) const;
+};
+
+class RecordRecTy : public RecTy {
+  Record *Rec;
+public:
+  RecordRecTy(Record *R) : Rec(R) {}
+
+  Init *convertValue(UnsetInit *UI) { return (Init*)UI; }
+  Init *convertValue(   DefInit *DI);
+
+  void print(std::ostream &OS) const;
+};
+
+//===----------------------------------------------------------------------===//
+//  Initializer Classes
+//===----------------------------------------------------------------------===//
+
+struct Init {
+  virtual ~Init() {}
+
+  virtual bool isComplete() const = 0;
+  virtual void print(std::ostream &OS) const = 0;
+  void dump() const;
+
+  virtual Init *convertInitializerTo(RecTy *Ty) = 0;
+  virtual Init *convertInitializerBitRange(const std::vector<unsigned> &Bits) {
+    return 0;
+  }
+
+  virtual Init *resolveReferences(Record &R) { return this; }
+};
+
+inline std::ostream &operator<<(std::ostream &OS, const Init &I) {
+  I.print(OS); return OS;
+}
+
+struct UnsetInit : public Init {
+  virtual Init *convertInitializerTo(RecTy *Ty) {
+    return Ty->convertValue(this);
+  }
+
+  virtual bool isComplete() const { return false; }
+  virtual void print(std::ostream &OS) const { OS << "?"; }
+};
+
+class BitInit : public Init {
+  bool Value;
+public:
+  BitInit(bool V) : Value(V) {}
+
+  bool getValue() const { return Value; }
+
+  virtual Init *convertInitializerTo(RecTy *Ty) {
+    return Ty->convertValue(this);
+  }
+
+  virtual bool isComplete() const { return true; }
+  virtual void print(std::ostream &OS) const { OS << (Value ? "1" : "0"); }
+};
+
+class BitsInit : public Init {
+  std::vector<Init*> Bits;
+public:
+  BitsInit(unsigned Size) : Bits(Size) {}
+
+  unsigned getNumBits() const { return Bits.size(); }
+
+  Init *getBit(unsigned Bit) const {
+    assert(Bit < Bits.size() && "Bit index out of range!");
+    return Bits[Bit];
+  }
+  void setBit(unsigned Bit, Init *V) {
+    assert(Bit < Bits.size() && "Bit index out of range!");
+    Bits[Bit] = V;
+  }
+
+  virtual Init *convertInitializerTo(RecTy *Ty) {
+    return Ty->convertValue(this);
+  }
+  virtual Init *convertInitializerBitRange(const std::vector<unsigned> &Bits);
+
+  virtual bool isComplete() const {
+    for (unsigned i = 0; i != getNumBits(); ++i)
+      if (!getBit(i)->isComplete()) return false;
+    return true;
+  }
+  virtual void print(std::ostream &OS) const;
+
+  virtual Init *resolveReferences(Record &R);
+
+  // printXX - Print this bitstream with the specified format, returning true if
+  // it is not possible.
+  bool printInHex(std::ostream &OS) const;
+  bool printAsVariable(std::ostream &OS) const;
+  bool printAsUnset(std::ostream &OS) const;
+};
+
+class IntInit : public Init {
+  int Value;
+public:
+  IntInit(int V) : Value(V) {}
+
+  int getValue() const { return Value; }
+
+  virtual Init *convertInitializerTo(RecTy *Ty) {
+    return Ty->convertValue(this);
+  }
+  virtual Init *convertInitializerBitRange(const std::vector<unsigned> &Bits);
+
+  virtual bool isComplete() const { return true; }
+  virtual void print(std::ostream &OS) const { OS << Value; }
+};
+
+class StringInit : public Init {
+  std::string Value;
+public:
+  StringInit(const std::string &V) : Value(V) {}
+
+  virtual Init *convertInitializerTo(RecTy *Ty) {
+    return Ty->convertValue(this);
+  }
+
+  virtual bool isComplete() const { return true; }
+  virtual void print(std::ostream &OS) const { OS << "\"" << Value << "\""; }
+};
+
+class ListInit : public Init {
+  std::vector<Record*> Records;
+public:
+  ListInit(std::vector<Record*> &Rs) {
+    Records.swap(Rs);
+  }
+
+  unsigned getSize() const { return Records.size(); }
+  Record  *getElement(unsigned i) const {
+    assert(i < Records.size() && "List element index out of range!");
+    return Records[i];
+  }
+
+  virtual Init *convertInitializerTo(RecTy *Ty) {
+    return Ty->convertValue(this);
+  }
+
+  virtual bool isComplete() const { return true; }
+  virtual void print(std::ostream &OS) const;
+};
+
+class VarInit : public Init {
+  std::string VarName;
+  RecTy *Ty;
+public:
+  VarInit(const std::string &VN, RecTy *T) : VarName(VN), Ty(T) {}
+  
+  virtual Init *convertInitializerTo(RecTy *Ty) {
+    return Ty->convertValue(this);
+  }
+
+  const std::string &getName() const { return VarName; }
+  RecTy *getType() const { return Ty; }
+
+  virtual Init *convertInitializerBitRange(const std::vector<unsigned> &Bits);
+  
+  virtual bool isComplete() const { return true; }
+  virtual void print(std::ostream &OS) const { OS << VarName; }
+};
+
+class VarBitInit : public Init {
+  VarInit *VI;
+  unsigned Bit;
+public:
+  VarBitInit(VarInit *V, unsigned B) : VI(V), Bit(B) {}
+
+  virtual Init *convertInitializerTo(RecTy *Ty) {
+    return Ty->convertValue(this);
+  }
+
+  VarInit *getVariable() const { return VI; }
+  unsigned getBitNum() const { return Bit; }
+  
+  virtual bool isComplete() const { return true; }
+  virtual void print(std::ostream &OS) const {
+    VI->print(OS); OS << "{" << Bit << "}";
+  }
+  virtual Init *resolveReferences(Record &R);
+};
+
+class DefInit : public Init {
+  Record *Def;
+public:
+  DefInit(Record *D) : Def(D) {}
+  
+  virtual Init *convertInitializerTo(RecTy *Ty) {
+    return Ty->convertValue(this);
+  }
+
+  Record *getDef() const { return Def; }
+
+  //virtual Init *convertInitializerBitRange(const std::vector<unsigned> &Bits);
+  
+  virtual bool isComplete() const { return true; }
+  virtual void print(std::ostream &OS) const;
+};
+
+
+
+//===----------------------------------------------------------------------===//
+//  High-Level Classes
+//===----------------------------------------------------------------------===//
+
+class RecordVal {
+  std::string Name;
+  RecTy *Ty;
+  unsigned Prefix;
+  Init *Value;
+public:
+  RecordVal(const std::string &N, RecTy *T, unsigned P);
+  ~RecordVal() { /*delete Ty; delete Value; Bad for copy ctor!*/ }
+
+  const std::string &getName() const { return Name; }
+
+  unsigned getPrefix() const { return Prefix; }
+  RecTy *getType() const { return Ty; }
+  Init *getValue() const { return Value; }
+
+  bool setValue(Init *V) {
+    if (V) {
+      Value = V->convertInitializerTo(Ty);
+      return Value == 0;
+    }
+    Value = 0;
+    return false;
+  }
+
+  void dump() const;
+  void print(std::ostream &OS, bool PrintSem = true) const;
+};
+
+inline std::ostream &operator<<(std::ostream &OS, const RecordVal &RV) {
+  RV.print(OS << "  ");
+  return OS;
+}
+
+struct Record {
+  const std::string Name;
+  std::vector<std::string> TemplateArgs;
+  std::vector<RecordVal> Values;
+  std::vector<Record*> SuperClasses;
+public:
+
+  Record(const std::string &N) : Name(N) {}
+  ~Record() {}
+
+  const std::string &getName() const { return Name; }
+  const std::vector<std::string> &getTemplateArgs() const {
+    return TemplateArgs;
+  }
+  const std::vector<RecordVal> &getValues() const { return Values; }
+  const std::vector<Record*>   &getSuperClasses() const { return SuperClasses; }
+
+  bool isTemplateArg(const std::string &Name) const {
+    for (unsigned i = 0, e = TemplateArgs.size(); i != e; ++i)
+      if (TemplateArgs[i] == Name) return true;
+    return false;
+  }
+
+  const RecordVal *getValue(const std::string &Name) const {
+    for (unsigned i = 0, e = Values.size(); i != e; ++i)
+      if (Values[i].getName() == Name) return &Values[i];
+    return 0;
+  }
+  RecordVal *getValue(const std::string &Name) {
+    for (unsigned i = 0, e = Values.size(); i != e; ++i)
+      if (Values[i].getName() == Name) return &Values[i];
+    return 0;
+  }
+
+  void addTemplateArg(const std::string &Name) {
+    assert(!isTemplateArg(Name) && "Template arg already defined!");
+    TemplateArgs.push_back(Name);
+  }
+
+  void addValue(const RecordVal &RV) {
+    assert(getValue(RV.getName()) == 0 && "Value already added!");
+    Values.push_back(RV);
+  }
+
+  bool isSubClassOf(Record *R) const {
+    for (unsigned i = 0, e = SuperClasses.size(); i != e; ++i)
+      if (SuperClasses[i] == R)
+	return true;
+    return false;
+  }
+
+  void addSuperClass(Record *R) {
+    assert(!isSubClassOf(R) && "Already subclassing record!");
+    SuperClasses.push_back(R);
+  }
+
+  // resolveReferences - If there are any field references that refer to fields
+  // that have been filled in, we can propagate the values now.
+  //
+  void resolveReferences();
+
+  void dump() const;
+};
+
+std::ostream &operator<<(std::ostream &OS, const Record &R);
+
+class RecordKeeper {
+  std::map<std::string, Record*> Classes, Defs;
+public:
+  ~RecordKeeper() {
+    for (std::map<std::string, Record*>::iterator I = Classes.begin(),
+	   E = Classes.end(); I != E; ++I)
+      delete I->second;
+    for (std::map<std::string, Record*>::iterator I = Defs.begin(),
+	   E = Defs.end(); I != E; ++I)
+      delete I->second;
+  }
+  
+  const std::map<std::string, Record*> &getClasses() const { return Classes; }
+  const std::map<std::string, Record*> &getDefs() const { return Defs; }
+
+  Record *getClass(const std::string &Name) const {
+    std::map<std::string, Record*>::const_iterator I = Classes.find(Name);
+    return I == Classes.end() ? 0 : I->second;
+  }
+  Record *getDef(const std::string &Name) const {
+    std::map<std::string, Record*>::const_iterator I = Defs.find(Name);
+    return I == Defs.end() ? 0 : I->second;
+  }
+  void addClass(Record *R) {
+    assert(getClass(R->getName()) == 0 && "Class already exists!");
+    Classes.insert(std::make_pair(R->getName(), R));
+  }
+  void addDef(Record *R) {
+    assert(getDef(R->getName()) == 0 && "Def already exists!");
+    Defs.insert(std::make_pair(R->getName(), R));
+  }
+
+  void dump() const;
+};
+
+std::ostream &operator<<(std::ostream &OS, const RecordKeeper &RK);
+
+extern RecordKeeper Records;
+
+#endif
diff --git a/utils/TableGen/TableGen.cpp b/utils/TableGen/TableGen.cpp
new file mode 100644
index 0000000000..a66ffe6765
--- /dev/null
+++ b/utils/TableGen/TableGen.cpp
@@ -0,0 +1,351 @@
+#include "Record.h"
+#include "Support/CommandLine.h"
+#include <algorithm>
+
+static cl::opt<std::string> Class("class", cl::desc("Print Enum list for this class"));
+static cl::opt<bool>        Parse("parse");
+
+void ParseFile();
+
+RecordKeeper Records;
+
+static Init *getBit(Record *R, unsigned BitNo) {
+  const std::vector<RecordVal> &V = R->getValues();
+  for (unsigned i = 0, e = V.size(); i != e; ++i)
+    if (V[i].getPrefix()) {
+      assert(dynamic_cast<BitsInit*>(V[i].getValue()) &&
+	     "Can only handle fields of bits<> type!");
+      BitsInit *I = (BitsInit*)V[i].getValue();
+      if (BitNo < I->getNumBits())
+	return I->getBit(BitNo);
+      BitNo -= I->getNumBits();
+    }
+
+  std::cerr << "Cannot find requested bit!\n";
+  abort();
+  return 0;
+}
+
+static unsigned getNumBits(Record *R) {
+  const std::vector<RecordVal> &V = R->getValues();
+  unsigned Num = 0;
+  for (unsigned i = 0, e = V.size(); i != e; ++i)
+    if (V[i].getPrefix()) {
+      assert(dynamic_cast<BitsInit*>(V[i].getValue()) &&
+	     "Can only handle fields of bits<> type!");
+      Num += ((BitsInit*)V[i].getValue())->getNumBits();
+    }
+  return Num;
+}
+
+static bool BitsAreFixed(Record *I1, Record *I2, unsigned BitNo) {
+  return dynamic_cast<BitInit*>(getBit(I1, BitNo)) &&
+         dynamic_cast<BitInit*>(getBit(I2, BitNo));
+}
+
+static bool BitsAreEqual(Record *I1, Record *I2, unsigned BitNo) {
+  BitInit *Bit1 = dynamic_cast<BitInit*>(getBit(I1, BitNo));
+  BitInit *Bit2 = dynamic_cast<BitInit*>(getBit(I2, BitNo));
+
+  return Bit1 && Bit2 && Bit1->getValue() == Bit2->getValue();
+}
+
+static bool BitRangesEqual(Record *I1, Record *I2,
+			   unsigned Start, unsigned End) {
+  for (unsigned i = Start; i != End; ++i)
+    if (!BitsAreEqual(I1, I2, i))
+      return false;
+  return true;
+}
+
+static unsigned getFirstFixedBit(Record *R, unsigned FirstFixedBit) {
+  // Look for the first bit of the pair that are required to be 0 or 1.
+  while (!dynamic_cast<BitInit*>(getBit(R, FirstFixedBit)))
+    ++FirstFixedBit;
+  return FirstFixedBit;
+}
+
+static void FindInstDifferences(Record *I1, Record *I2,
+				unsigned FirstFixedBit, unsigned MaxBits,
+				unsigned &FirstVaryingBitOverall,
+				unsigned &LastFixedBitOverall) {
+  // Compare the first instruction to the rest of the instructions, looking for
+  // fields that differ.
+  //
+  unsigned FirstVaryingBit = FirstFixedBit;
+  while (FirstVaryingBit < MaxBits && BitsAreEqual(I1, I2, FirstVaryingBit))
+    ++FirstVaryingBit;
+
+  unsigned LastFixedBit = FirstVaryingBit;
+  while (LastFixedBit < MaxBits && BitsAreFixed(I1, I2, LastFixedBit))
+    ++LastFixedBit;
+  
+  if (FirstVaryingBit < FirstVaryingBitOverall)
+    FirstVaryingBitOverall = FirstVaryingBit;
+  if (LastFixedBit < LastFixedBitOverall)
+    LastFixedBitOverall = LastFixedBit;
+}
+
+static bool getBitValue(Record *R, unsigned BitNo) {
+  Init *I = getBit(R, BitNo);
+  assert(dynamic_cast<BitInit*>(I) && "Bit should be fixed!");
+  return ((BitInit*)I)->getValue();
+}
+
+struct BitComparator {
+  unsigned BitBegin, BitEnd;
+  BitComparator(unsigned B, unsigned E) : BitBegin(B), BitEnd(E) {}
+
+  bool operator()(Record *R1, Record *R2) { // Return true if R1 is less than R2
+    for (unsigned i = BitBegin; i != BitEnd; ++i) {
+      bool V1 = getBitValue(R1, i), V2 = getBitValue(R2, i);
+      if (V1 < V2)
+	return true;
+      else if (V2 < V1)
+	return false;
+    }
+    return false;
+  }
+};
+
+static void PrintRange(std::vector<Record*>::iterator I, 
+		       std::vector<Record*>::iterator E) {
+  while (I != E) std::cerr << **I++;
+}
+
+static bool getMemoryBit(unsigned char *M, unsigned i) {
+  return (M[i/8] & (1 << (i&7))) != 0;
+}
+
+static unsigned getFirstFixedBitInSequence(std::vector<Record*>::iterator IB,
+					   std::vector<Record*>::iterator IE,
+					   unsigned StartBit) {
+  unsigned FirstFixedBit = 0;
+  for (std::vector<Record*>::iterator I = IB; I != IE; ++I)
+    FirstFixedBit = std::max(FirstFixedBit, getFirstFixedBit(*I, StartBit));
+  return FirstFixedBit;
+}
+
+// ParseMachineCode - Try to split the vector of instructions (which is
+// intentially taken by-copy) in half, narrowing down the possible instructions
+// that we may have found.  Eventually, this list will get pared down to zero or
+// one instruction, in which case we have a match or failure.
+//
+static Record *ParseMachineCode(std::vector<Record*>::iterator InstsB, 
+				std::vector<Record*>::iterator InstsE,
+				unsigned char *M) {
+  assert(InstsB != InstsE && "Empty range?");
+  if (InstsB+1 == InstsE) {
+    // Only a single instruction, see if we match it...
+    Record *Inst = *InstsB;
+    for (unsigned i = 0, e = getNumBits(Inst); i != e; ++i)
+      if (BitInit *BI = dynamic_cast<BitInit*>(getBit(Inst, i)))
+	if (getMemoryBit(M, i) != BI->getValue())
+	  return 0;
+    return Inst;
+  }
+
+  unsigned MaxBits = ~0;
+  for (std::vector<Record*>::iterator I = InstsB; I != InstsE; ++I)
+    MaxBits = std::min(MaxBits, getNumBits(*I));
+
+  unsigned FirstFixedBit = getFirstFixedBitInSequence(InstsB, InstsE, 0);
+  unsigned FirstVaryingBit, LastFixedBit;
+  do {
+    FirstVaryingBit = ~0;
+    LastFixedBit = ~0;
+    for (std::vector<Record*>::iterator I = InstsB+1; I != InstsE; ++I)
+      FindInstDifferences(*InstsB, *I, FirstFixedBit, MaxBits,
+			  FirstVaryingBit, LastFixedBit);
+    if (FirstVaryingBit == MaxBits) {
+      std::cerr << "ERROR: Could not find bit to distinguish between "
+		<< "the following entries!\n";
+      PrintRange(InstsB, InstsE);
+    }
+
+#if 0
+    std::cerr << "FVB: " << FirstVaryingBit << " - " << LastFixedBit
+	      << ": " << InstsE-InstsB << "\n";
+#endif
+
+    FirstFixedBit = getFirstFixedBitInSequence(InstsB, InstsE, FirstVaryingBit);
+  } while (FirstVaryingBit != FirstFixedBit);
+
+  //std::cerr << "\n\nXXXXXXXXXXXXXXXXX\n\n";
+  //PrintRange(InstsB, InstsE);
+
+  // Sort the Insts list so that the entries have all of the bits in the range
+  // [FirstVaryingBit,LastFixedBit) sorted.  These bits are all guaranteed to be
+  // set to either 0 or 1 (BitInit values), which simplifies things.
+  //
+  std::sort(InstsB, InstsE, BitComparator(FirstVaryingBit, LastFixedBit));
+
+  // Once the list is sorted by these bits, split the bit list into smaller
+  // lists, and recurse on each one.
+  //
+  std::vector<Record*>::iterator RangeBegin = InstsB;
+  Record *Match = 0;
+  while (RangeBegin != InstsE) {
+    std::vector<Record*>::iterator RangeEnd = RangeBegin+1;
+    while (RangeEnd != InstsE &&
+          BitRangesEqual(*RangeBegin, *RangeEnd, FirstVaryingBit, LastFixedBit))
+      ++RangeEnd;
+    
+    // We just identified a range of equal instructions.  If this range is the
+    // input range, we were not able to distinguish between the instructions in
+    // the set.  Print an error and exit!
+    //
+    if (RangeBegin == InstsB && RangeEnd == InstsE) {
+      std::cerr << "Error: Could not distinguish among the following insts!:\n";
+      PrintRange(InstsB, InstsE);
+      abort();
+    }
+    
+    if (Record *R = ParseMachineCode(RangeBegin, RangeEnd, M)) {
+      if (Match) {
+	std::cerr << "Error: Multiple matches found:\n";
+	PrintRange(InstsB, InstsE);
+      }
+
+      assert(Match == 0 && "Multiple matches??");
+      Match = R;
+    }
+    RangeBegin = RangeEnd;
+  }
+
+  return Match;
+}
+
+static void PrintValue(Record *I, unsigned char *Ptr, const RecordVal &Val) {
+  assert(dynamic_cast<BitsInit*>(Val.getValue()) &&
+	 "Can only handle undefined bits<> types!");
+  BitsInit *BI = (BitsInit*)Val.getValue();
+  assert(BI->getNumBits() <= 32 && "Can only handle fields up to 32 bits!");
+
+  unsigned Value = 0;
+  const std::vector<RecordVal> &Vals = I->getValues();
+
+  // Start by filling in fixed values...
+  for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i)
+    if (BitInit *B = dynamic_cast<BitInit*>(BI->getBit(i)))
+      Value |= B->getValue() << i;
+  
+  // Loop over all of the fields in the instruction adding in any
+  // contributions to this value (due to bit references).
+  //
+  unsigned Offset = 0;
+  for (unsigned f = 0, e = Vals.size(); f != e; ++f)
+    if (Vals[f].getPrefix()) {
+      BitsInit *FieldInit = (BitsInit*)Vals[f].getValue();
+      if (&Vals[f] == &Val) {
+	// Read the bits directly now...
+	for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i)
+	  Value |= getMemoryBit(Ptr, Offset+i) << i;
+	break;
+      }
+      
+      // Scan through the field looking for bit initializers of the current
+      // variable...
+      for (unsigned i = 0, e = FieldInit->getNumBits(); i != e; ++i)
+	if (VarBitInit *VBI =
+	    dynamic_cast<VarBitInit*>(FieldInit->getBit(i))) {
+	  if (VBI->getVariable()->getName() == Val.getName())
+	    Value |= getMemoryBit(Ptr, Offset+i) << VBI->getBitNum();
+	}	
+      Offset += FieldInit->getNumBits();
+    }
+
+  std::cout << "0x" << std::hex << Value << std::dec;
+}
+
+static void PrintInstruction(Record *I, unsigned char *Ptr) {
+  std::cout << "Inst " << getNumBits(I)/8 << " bytes: "
+	    << "\t" << I->getName() << "\t" << *I->getValue("Name")->getValue()
+	    << "\t";
+  
+  const std::vector<RecordVal> &Vals = I->getValues();
+  for (unsigned i = 0, e = Vals.size(); i != e; ++i)
+    if (!Vals[i].getValue()->isComplete()) {
+      std::cout << Vals[i].getName() << "=";
+      PrintValue(I, Ptr, Vals[i]);
+      std::cout << "\t";
+    }
+  
+  std::cout << "\n";// << *I;
+}
+
+static void ParseMachineCode() {
+  unsigned char Buffer[] = { 0x55,             // push EBP
+			     0x89, 0xE5,       // mov EBP, ESP
+			     //0x83, 0xEC, 0x08, // sub ESP, 0x8
+			     0xE8, 1, 2, 3, 4, // call +0x04030201
+			     0x89, 0xEC,       // mov ESP, EBP
+			     0x5D,             // pop EBP
+			     0xC3,             // ret
+			     0x90,             // nop
+			     0xC9,             // leave
+			     0x89, 0xF6,       // mov ESI, ESI
+			     0xB8, 1, 2, 3, 4, // mov EAX, 0x04030201
+			     0x68, 1, 2, 3, 4, // push 0x04030201
+			     0x5e,             // pop ESI
+			     0xFF, 0xD0,       // call EAX
+			     0x85, 0xC0,       // test EAX, EAX
+			     0xF4,             // hlt
+  };
+  
+  std::vector<Record*> Insts;
+
+  const std::map<std::string, Record*> &Defs = Records.getDefs();
+  Record *Inst = Records.getClass("Instruction");
+  assert(Inst && "Couldn't find Instruction class!");
+
+  for (std::map<std::string, Record*>::const_iterator I = Defs.begin(),
+	 E = Defs.end(); I != E; ++I)
+    if (I->second->isSubClassOf(Inst))
+      Insts.push_back(I->second);
+
+  unsigned char *BuffPtr = Buffer;
+  while (1) {
+    Record *R = ParseMachineCode(Insts.begin(), Insts.end(), BuffPtr);
+    if (R == 0) {
+      std::cout << "Parse failed!\n";
+      return;
+    }
+    PrintInstruction(R, BuffPtr);
+
+    unsigned Bits = getNumBits(R);
+    assert((Bits & 7) == 0 && "Instruction is not an even number of bytes!");
+    BuffPtr += Bits/8;
+  }
+}
+
+
+int main(int argc, char **argv) {
+  cl::ParseCommandLineOptions(argc, argv);
+  ParseFile();
+
+  if (Parse) {
+    ParseMachineCode();
+    return 0;
+  }
+
+  if (Class == "") {
+    std::cout << Records;           // No argument, dump all contents
+  } else {
+    Record *R = Records.getClass(Class);
+    if (R == 0) {
+      std::cerr << "Cannot find class '" << Class << "'!\n";
+      abort();
+    }
+
+    const std::map<std::string, Record*> &Defs = Records.getDefs();
+    for (std::map<std::string, Record*>::const_iterator I = Defs.begin(),
+	   E = Defs.end(); I != E; ++I) {
+      if (I->second->isSubClassOf(R)) {
+	std::cout << I->first << ", ";
+      }
+    }
+    std::cout << "\n";
+  }
+  return 0;
+}