From e62c1185bee05facc25d1d725434f517261d308b Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Mon, 2 Dec 2002 01:23:04 +0000 Subject: [PATCH] Initial checkin of TableGen utility git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@4843 91177308-0d34-0410-b5e6-96231b3b80d8 --- support/tools/TableGen/FileLexer.l | 66 ++++ support/tools/TableGen/FileParser.y | 445 +++++++++++++++++++++++++++ support/tools/TableGen/Makefile | 23 ++ support/tools/TableGen/Record.cpp | 371 +++++++++++++++++++++++ support/tools/TableGen/Record.h | 448 ++++++++++++++++++++++++++++ support/tools/TableGen/TableGen.cpp | 351 ++++++++++++++++++++++ utils/TableGen/FileLexer.l | 66 ++++ utils/TableGen/FileParser.y | 445 +++++++++++++++++++++++++++ utils/TableGen/Makefile | 23 ++ utils/TableGen/Record.cpp | 371 +++++++++++++++++++++++ utils/TableGen/Record.h | 448 ++++++++++++++++++++++++++++ utils/TableGen/TableGen.cpp | 351 ++++++++++++++++++++++ 12 files changed, 3408 insertions(+) create mode 100644 support/tools/TableGen/FileLexer.l create mode 100644 support/tools/TableGen/FileParser.y create mode 100644 support/tools/TableGen/Makefile create mode 100644 support/tools/TableGen/Record.cpp create mode 100644 support/tools/TableGen/Record.h create mode 100644 support/tools/TableGen/TableGen.cpp create mode 100644 utils/TableGen/FileLexer.l create mode 100644 utils/TableGen/FileParser.y create mode 100644 utils/TableGen/Makefile create mode 100644 utils/TableGen/Record.cpp create mode 100644 utils/TableGen/Record.h create mode 100644 utils/TableGen/TableGen.cpp diff --git a/support/tools/TableGen/FileLexer.l b/support/tools/TableGen/FileLexer.l new file mode 100644 index 00000000000..c7e4346c0fe --- /dev/null +++ b/support/tools/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*> 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/support/tools/TableGen/FileParser.y b/support/tools/TableGen/FileParser.y new file mode 100644 index 00000000000..624a7978953 --- /dev/null +++ b/support/tools/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 +#include +#include +#include +#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*> SubClassRefTy; + +static std::vector*>, + 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 *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(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(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 &TemplateArgs) { + // Add all of the values in the subclass into the current class... + const std::vector &Vals = SC->getValues(); + for (unsigned i = 0, e = Vals.size(); i != e; ++i) + addValue(Vals[i]); + + const std::vector &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 &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 *FieldList; + std::vector *RecPtr; + std::vector*BitList; + Record *Rec; + SubClassRefTy *SubClassRef; + std::vector *SubClassList; +}; + +%token INT BIT STRING BITS LIST CLASS DEF FIELD SET IN +%token INTVAL +%token ID STRVAL + +%type Type +%type DefList DefListNE +%type ClassInst DefInst Object ObjectBody ClassID DefID + +%type SubClassRef +%type ClassList ClassListNE +%type OptPrefix +%type Value OptValue +%type ValueList ValueListNE +%type BitList OptBitList RBitList +%type 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 type + $$ = new BitsRecTy($3); + } | INT { // int type + $$ = new IntRecTy(); + } | LIST '<' ClassID '>' { // list 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(); + } | DefListNE { + $$ = $1; + }; +DefListNE : DefID { + $$ = new std::vector(); + $$->push_back($1); + } | DefListNE ',' DefID { + ($$=$1)->push_back($3); + }; + + +RBitList : INTVAL { + $$ = new std::vector(); + $$->push_back($1); + } | INTVAL '-' INTVAL { + if ($1 < $3 || $1 < 0 || $3 < 0) { + err() << "Invalid bit range: " << $1 << "-" << $3 << "!\n"; + abort(); + } + $$ = new std::vector(); + 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(); + 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(); + } | ValueListNE { + $$ = $1; + }; + +ValueListNE : Value { + $$ = new std::vector(); + $$->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()); + } | ClassID '<' ValueListNE '>' { + $$ = new SubClassRefTy($1, $3); + }; + +ClassListNE : SubClassRef { + $$ = new std::vector(); + $$->push_back(*$1); + delete $1; + } + | ClassListNE ',' SubClassRef { + ($$=$1)->push_back(*$3); + delete $3; + }; + +ClassList : /*empty */ { + $$ = new std::vector(); + } + | ':' 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/support/tools/TableGen/Makefile b/support/tools/TableGen/Makefile new file mode 100644 index 00000000000..a9c235037e2 --- /dev/null +++ b/support/tools/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/support/tools/TableGen/Record.cpp b/support/tools/TableGen/Record.cpp new file mode 100644 index 00000000000..8324bad5c16 --- /dev/null +++ b/support/tools/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(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(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(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(BI->getBit(i))) { + Result |= Bit->getValue() << i; + } else { + return 0; + } + return new IntInit(Result); +} + +Init *IntRecTy::convertValue(VarInit *VI) { + if (dynamic_cast(VI->getType())) + return VI; // Accept variable if already of the right type! + return 0; +} + +Init *StringRecTy::convertValue(VarInit *VI) { + if (dynamic_cast(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 &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(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(getBit(0)); + if (FirstBit == 0) return true; + VarInit *Var = FirstBit->getVariable(); + + // Check to make sure the types are compatible. + BitsRecTy *Ty = dynamic_cast(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(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(getBit(i))) + return true; + OS << "?"; + return false; +} + +Init *IntInit::convertInitializerBitRange(const std::vector &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 &Bits) { + BitsRecTy *T = dynamic_cast(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(RV->getValue())); + BitsInit *BI = (BitsInit*)RV->getValue(); + + assert(getBitNum() < BI->getNumBits() && "Bit reference out of range!"); + Init *B = BI->getBit(getBitNum()); + + if (!dynamic_cast(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 &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 &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 &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 &Classes = RK.getClasses(); + for (std::map::const_iterator I = Classes.begin(), + E = Classes.end(); I != E; ++I) + OS << "class " << *I->second; + + OS << "------------- Defs -----------------\n"; + const std::map &Defs = RK.getDefs(); + for (std::map::const_iterator I = Defs.begin(), + E = Defs.end(); I != E; ++I) + OS << "def " << *I->second; + return OS; +} diff --git a/support/tools/TableGen/Record.h b/support/tools/TableGen/Record.h new file mode 100644 index 00000000000..a3f8c0bd851 --- /dev/null +++ b/support/tools/TableGen/Record.h @@ -0,0 +1,448 @@ +//===- Record.h - Classes to represent Table Records ------------*- C++ -*-===// +// +// +//===----------------------------------------------------------------------===// + +#ifndef RECORD_H +#define RECORD_H + +#include +#include +#include +#include +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 &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 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 &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 &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 Records; +public: + ListInit(std::vector &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 &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 &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 TemplateArgs; + std::vector Values; + std::vector SuperClasses; +public: + + Record(const std::string &N) : Name(N) {} + ~Record() {} + + const std::string &getName() const { return Name; } + const std::vector &getTemplateArgs() const { + return TemplateArgs; + } + const std::vector &getValues() const { return Values; } + const std::vector &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 Classes, Defs; +public: + ~RecordKeeper() { + for (std::map::iterator I = Classes.begin(), + E = Classes.end(); I != E; ++I) + delete I->second; + for (std::map::iterator I = Defs.begin(), + E = Defs.end(); I != E; ++I) + delete I->second; + } + + const std::map &getClasses() const { return Classes; } + const std::map &getDefs() const { return Defs; } + + Record *getClass(const std::string &Name) const { + std::map::const_iterator I = Classes.find(Name); + return I == Classes.end() ? 0 : I->second; + } + Record *getDef(const std::string &Name) const { + std::map::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/support/tools/TableGen/TableGen.cpp b/support/tools/TableGen/TableGen.cpp new file mode 100644 index 00000000000..a66ffe6765c --- /dev/null +++ b/support/tools/TableGen/TableGen.cpp @@ -0,0 +1,351 @@ +#include "Record.h" +#include "Support/CommandLine.h" +#include + +static cl::opt Class("class", cl::desc("Print Enum list for this class")); +static cl::opt Parse("parse"); + +void ParseFile(); + +RecordKeeper Records; + +static Init *getBit(Record *R, unsigned BitNo) { + const std::vector &V = R->getValues(); + for (unsigned i = 0, e = V.size(); i != e; ++i) + if (V[i].getPrefix()) { + assert(dynamic_cast(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 &V = R->getValues(); + unsigned Num = 0; + for (unsigned i = 0, e = V.size(); i != e; ++i) + if (V[i].getPrefix()) { + assert(dynamic_cast(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(getBit(I1, BitNo)) && + dynamic_cast(getBit(I2, BitNo)); +} + +static bool BitsAreEqual(Record *I1, Record *I2, unsigned BitNo) { + BitInit *Bit1 = dynamic_cast(getBit(I1, BitNo)); + BitInit *Bit2 = dynamic_cast(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(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(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::iterator I, + std::vector::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::iterator IB, + std::vector::iterator IE, + unsigned StartBit) { + unsigned FirstFixedBit = 0; + for (std::vector::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::iterator InstsB, + std::vector::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(getBit(Inst, i))) + if (getMemoryBit(M, i) != BI->getValue()) + return 0; + return Inst; + } + + unsigned MaxBits = ~0; + for (std::vector::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::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::iterator RangeBegin = InstsB; + Record *Match = 0; + while (RangeBegin != InstsE) { + std::vector::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(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 &Vals = I->getValues(); + + // Start by filling in fixed values... + for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i) + if (BitInit *B = dynamic_cast(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(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 &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 Insts; + + const std::map &Defs = Records.getDefs(); + Record *Inst = Records.getClass("Instruction"); + assert(Inst && "Couldn't find Instruction class!"); + + for (std::map::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 &Defs = Records.getDefs(); + for (std::map::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; +} diff --git a/utils/TableGen/FileLexer.l b/utils/TableGen/FileLexer.l new file mode 100644 index 00000000000..c7e4346c0fe --- /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*> 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 00000000000..624a7978953 --- /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 +#include +#include +#include +#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*> SubClassRefTy; + +static std::vector*>, + 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 *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(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(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 &TemplateArgs) { + // Add all of the values in the subclass into the current class... + const std::vector &Vals = SC->getValues(); + for (unsigned i = 0, e = Vals.size(); i != e; ++i) + addValue(Vals[i]); + + const std::vector &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 &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 *FieldList; + std::vector *RecPtr; + std::vector*BitList; + Record *Rec; + SubClassRefTy *SubClassRef; + std::vector *SubClassList; +}; + +%token INT BIT STRING BITS LIST CLASS DEF FIELD SET IN +%token INTVAL +%token ID STRVAL + +%type Type +%type DefList DefListNE +%type ClassInst DefInst Object ObjectBody ClassID DefID + +%type SubClassRef +%type ClassList ClassListNE +%type OptPrefix +%type Value OptValue +%type ValueList ValueListNE +%type BitList OptBitList RBitList +%type 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 type + $$ = new BitsRecTy($3); + } | INT { // int type + $$ = new IntRecTy(); + } | LIST '<' ClassID '>' { // list 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(); + } | DefListNE { + $$ = $1; + }; +DefListNE : DefID { + $$ = new std::vector(); + $$->push_back($1); + } | DefListNE ',' DefID { + ($$=$1)->push_back($3); + }; + + +RBitList : INTVAL { + $$ = new std::vector(); + $$->push_back($1); + } | INTVAL '-' INTVAL { + if ($1 < $3 || $1 < 0 || $3 < 0) { + err() << "Invalid bit range: " << $1 << "-" << $3 << "!\n"; + abort(); + } + $$ = new std::vector(); + 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(); + 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(); + } | ValueListNE { + $$ = $1; + }; + +ValueListNE : Value { + $$ = new std::vector(); + $$->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()); + } | ClassID '<' ValueListNE '>' { + $$ = new SubClassRefTy($1, $3); + }; + +ClassListNE : SubClassRef { + $$ = new std::vector(); + $$->push_back(*$1); + delete $1; + } + | ClassListNE ',' SubClassRef { + ($$=$1)->push_back(*$3); + delete $3; + }; + +ClassList : /*empty */ { + $$ = new std::vector(); + } + | ':' 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 00000000000..a9c235037e2 --- /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 00000000000..8324bad5c16 --- /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(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(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(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(BI->getBit(i))) { + Result |= Bit->getValue() << i; + } else { + return 0; + } + return new IntInit(Result); +} + +Init *IntRecTy::convertValue(VarInit *VI) { + if (dynamic_cast(VI->getType())) + return VI; // Accept variable if already of the right type! + return 0; +} + +Init *StringRecTy::convertValue(VarInit *VI) { + if (dynamic_cast(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 &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(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(getBit(0)); + if (FirstBit == 0) return true; + VarInit *Var = FirstBit->getVariable(); + + // Check to make sure the types are compatible. + BitsRecTy *Ty = dynamic_cast(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(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(getBit(i))) + return true; + OS << "?"; + return false; +} + +Init *IntInit::convertInitializerBitRange(const std::vector &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 &Bits) { + BitsRecTy *T = dynamic_cast(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(RV->getValue())); + BitsInit *BI = (BitsInit*)RV->getValue(); + + assert(getBitNum() < BI->getNumBits() && "Bit reference out of range!"); + Init *B = BI->getBit(getBitNum()); + + if (!dynamic_cast(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 &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 &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 &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 &Classes = RK.getClasses(); + for (std::map::const_iterator I = Classes.begin(), + E = Classes.end(); I != E; ++I) + OS << "class " << *I->second; + + OS << "------------- Defs -----------------\n"; + const std::map &Defs = RK.getDefs(); + for (std::map::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 00000000000..a3f8c0bd851 --- /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 +#include +#include +#include +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 &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 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 &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 &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 Records; +public: + ListInit(std::vector &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 &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 &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 TemplateArgs; + std::vector Values; + std::vector SuperClasses; +public: + + Record(const std::string &N) : Name(N) {} + ~Record() {} + + const std::string &getName() const { return Name; } + const std::vector &getTemplateArgs() const { + return TemplateArgs; + } + const std::vector &getValues() const { return Values; } + const std::vector &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 Classes, Defs; +public: + ~RecordKeeper() { + for (std::map::iterator I = Classes.begin(), + E = Classes.end(); I != E; ++I) + delete I->second; + for (std::map::iterator I = Defs.begin(), + E = Defs.end(); I != E; ++I) + delete I->second; + } + + const std::map &getClasses() const { return Classes; } + const std::map &getDefs() const { return Defs; } + + Record *getClass(const std::string &Name) const { + std::map::const_iterator I = Classes.find(Name); + return I == Classes.end() ? 0 : I->second; + } + Record *getDef(const std::string &Name) const { + std::map::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 00000000000..a66ffe6765c --- /dev/null +++ b/utils/TableGen/TableGen.cpp @@ -0,0 +1,351 @@ +#include "Record.h" +#include "Support/CommandLine.h" +#include + +static cl::opt Class("class", cl::desc("Print Enum list for this class")); +static cl::opt Parse("parse"); + +void ParseFile(); + +RecordKeeper Records; + +static Init *getBit(Record *R, unsigned BitNo) { + const std::vector &V = R->getValues(); + for (unsigned i = 0, e = V.size(); i != e; ++i) + if (V[i].getPrefix()) { + assert(dynamic_cast(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 &V = R->getValues(); + unsigned Num = 0; + for (unsigned i = 0, e = V.size(); i != e; ++i) + if (V[i].getPrefix()) { + assert(dynamic_cast(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(getBit(I1, BitNo)) && + dynamic_cast(getBit(I2, BitNo)); +} + +static bool BitsAreEqual(Record *I1, Record *I2, unsigned BitNo) { + BitInit *Bit1 = dynamic_cast(getBit(I1, BitNo)); + BitInit *Bit2 = dynamic_cast(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(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(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::iterator I, + std::vector::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::iterator IB, + std::vector::iterator IE, + unsigned StartBit) { + unsigned FirstFixedBit = 0; + for (std::vector::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::iterator InstsB, + std::vector::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(getBit(Inst, i))) + if (getMemoryBit(M, i) != BI->getValue()) + return 0; + return Inst; + } + + unsigned MaxBits = ~0; + for (std::vector::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::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::iterator RangeBegin = InstsB; + Record *Match = 0; + while (RangeBegin != InstsE) { + std::vector::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(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 &Vals = I->getValues(); + + // Start by filling in fixed values... + for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i) + if (BitInit *B = dynamic_cast(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(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 &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 Insts; + + const std::map &Defs = Records.getDefs(); + Record *Inst = Records.getClass("Instruction"); + assert(Inst && "Couldn't find Instruction class!"); + + for (std::map::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 &Defs = Records.getDefs(); + for (std::map::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; +} -- 2.34.1