utils/TableGen/FileParser.y

   1 //===-- FileParser.y - Parser for TableGen files ----------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file implements the bison parser for Table Generator files...
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 %{
  15 #include "Record.h"
  16 #include "llvm/ADT/StringExtras.h"
  17 #include <algorithm>
  18 #include <cstdio>
  19 #define YYERROR_VERBOSE 1
  20
  21 int yyerror(const char *ErrorMsg);
  22 int yylex();
  23
  24 namespace llvm {
  25
  26 extern int Filelineno;
  27 static Record *CurRec = 0;
  28 static bool ParsingTemplateArgs = false;
  29
  30 typedef std::pair<Record*, std::vector<Init*>*> SubClassRefTy;
  31
  32 struct LetRecord {
  33   std::string Name;
  34   std::vector<unsigned> Bits;
  35   Init *Value;
  36   bool HasBits;
  37   LetRecord(const std::string &N, std::vector<unsigned> *B, Init *V)
  38     : Name(N), Value(V), HasBits(B != 0) {
  39     if (HasBits) Bits = *B;
  40   }
  41 };
  42
  43 static std::vector<std::vector<LetRecord> > LetStack;
  44
  45
  46 extern std::ostream &err();
  47
  48 static void addValue(const RecordVal &RV) {
  49   if (RecordVal *ERV = CurRec->getValue(RV.getName())) {
  50     // The value already exists in the class, treat this as a set...
  51     if (ERV->setValue(RV.getValue())) {
  52       err() << "New definition of '" << RV.getName() << "' of type '"
  53             << *RV.getType() << "' is incompatible with previous "
  54             << "definition of type '" << *ERV->getType() << "'!\n";
  55       exit(1);
  56     }
  57   } else {
  58     CurRec->addValue(RV);
  59   }
  60 }
  61
  62 static void addSuperClass(Record *SC) {
  63   if (CurRec->isSubClassOf(SC)) {
  64     err() << "Already subclass of '" << SC->getName() << "'!\n";
  65     exit(1);
  66   }
  67   CurRec->addSuperClass(SC);
  68 }
  69
  70 static void setValue(const std::string &ValName,
  71                      std::vector<unsigned> *BitList, Init *V) {
  72   if (!V) return;
  73
  74   RecordVal *RV = CurRec->getValue(ValName);
  75   if (RV == 0) {
  76     err() << "Value '" << ValName << "' unknown!\n";
  77     exit(1);
  78   }
  79
  80   // Do not allow assignments like 'X = X'.  This will just cause infinite loops
  81   // in the resolution machinery.
  82   if (!BitList)
  83     if (VarInit *VI = dynamic_cast<VarInit*>(V))
  84       if (VI->getName() == ValName)
  85         return;
  86
  87   // If we are assigning to a subset of the bits in the value... then we must be
  88   // assigning to a field of BitsRecTy, which must have a BitsInit
  89   // initializer...
  90   //
  91   if (BitList) {
  92     BitsInit *CurVal = dynamic_cast<BitsInit*>(RV->getValue());
  93     if (CurVal == 0) {
  94       err() << "Value '" << ValName << "' is not a bits type!\n";
  95       exit(1);
  96     }
  97
  98     // Convert the incoming value to a bits type of the appropriate size...
  99     Init *BI = V->convertInitializerTo(new BitsRecTy(BitList->size()));
 100     if (BI == 0) {
 101       V->convertInitializerTo(new BitsRecTy(BitList->size()));
 102       err() << "Initializer '" << *V << "' not compatible with bit range!\n";
 103       exit(1);
 104     }
 105
 106     // We should have a BitsInit type now...
 107     assert(dynamic_cast<BitsInit*>(BI) != 0 || &(std::cerr << *BI) == 0);
 108     BitsInit *BInit = (BitsInit*)BI;
 109
 110     BitsInit *NewVal = new BitsInit(CurVal->getNumBits());
 111
 112     // Loop over bits, assigning values as appropriate...
 113     for (unsigned i = 0, e = BitList->size(); i != e; ++i) {
 114       unsigned Bit = (*BitList)[i];
 115       if (NewVal->getBit(Bit)) {
 116         err() << "Cannot set bit #" << Bit << " of value '" << ValName
 117               << "' more than once!\n";
 118         exit(1);
 119       }
 120       NewVal->setBit(Bit, BInit->getBit(i));
 121     }
 122
 123     for (unsigned i = 0, e = CurVal->getNumBits(); i != e; ++i)
 124       if (NewVal->getBit(i) == 0)
 125         NewVal->setBit(i, CurVal->getBit(i));
 126
 127     V = NewVal;
 128   }
 129
 130   if (RV->setValue(V)) {
 131     err() << "Value '" << ValName << "' of type '" << *RV->getType()
 132           << "' is incompatible with initializer '" << *V << "'!\n";
 133     exit(1);
 134   }
 135 }
 136
 137 // addSubClass - Add SC as a subclass to CurRec, resolving TemplateArgs as SC's
 138 // template arguments.
 139 static void addSubClass(Record *SC, const std::vector<Init*> &TemplateArgs) {
 140   // Add all of the values in the subclass into the current class...
 141   const std::vector<RecordVal> &Vals = SC->getValues();
 142   for (unsigned i = 0, e = Vals.size(); i != e; ++i)
 143     addValue(Vals[i]);
 144
 145   const std::vector<std::string> &TArgs = SC->getTemplateArgs();
 146
 147   // Ensure that an appropriate number of template arguments are specified...
 148   if (TArgs.size() < TemplateArgs.size()) {
 149     err() << "ERROR: More template args specified than expected!\n";
 150     exit(1);
 151   } else {    // This class expects template arguments...
 152     // Loop over all of the template arguments, setting them to the specified
 153     // value or leaving them as the default if necessary.
 154     for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
 155       if (i < TemplateArgs.size()) {  // A value is specified for this temp-arg?
 156         // Set it now.
 157         setValue(TArgs[i], 0, TemplateArgs[i]);
 158
 159         // Resolve it next.
 160         CurRec->resolveReferencesTo(CurRec->getValue(TArgs[i]));
 161
 162
 163         // Now remove it.
 164         CurRec->removeValue(TArgs[i]);
 165
 166       } else if (!CurRec->getValue(TArgs[i])->getValue()->isComplete()) {
 167         err() << "ERROR: Value not specified for template argument #"
 168               << i << " (" << TArgs[i] << ") of subclass '" << SC->getName()
 169               << "'!\n";
 170         exit(1);
 171       }
 172     }
 173   }
 174
 175   // Since everything went well, we can now set the "superclass" list for the
 176   // current record.
 177   const std::vector<Record*> &SCs  = SC->getSuperClasses();
 178   for (unsigned i = 0, e = SCs.size(); i != e; ++i)
 179     addSuperClass(SCs[i]);
 180   addSuperClass(SC);
 181 }
 182
 183 } // End llvm namespace
 184
 185 using namespace llvm;
 186
 187 %}
 188
 189 %union {
 190   std::string*                StrVal;
 191   int                         IntVal;
 192   llvm::RecTy*                Ty;
 193   llvm::Init*                 Initializer;
 194   std::vector<llvm::Init*>*   FieldList;
 195   std::vector<unsigned>*      BitList;
 196   llvm::Record*               Rec;
 197   SubClassRefTy*              SubClassRef;
 198   std::vector<SubClassRefTy>* SubClassList;
 199   std::vector<std::pair<llvm::Init*, std::string> >* DagValueList;
 200 };
 201
 202 %token INT BIT STRING BITS LIST CODE DAG CLASS DEF FIELD LET IN
 203 %token SHLTOK SRATOK SRLTOK
 204 %token <IntVal>      INTVAL
 205 %token <StrVal>      ID VARNAME STRVAL CODEFRAGMENT
 206
 207 %type <Ty>           Type
 208 %type <Rec>          ClassInst DefInst Object ObjectBody ClassID
 209
 210 %type <SubClassRef>  SubClassRef
 211 %type <SubClassList> ClassList ClassListNE
 212 %type <IntVal>       OptPrefix
 213 %type <Initializer>  Value OptValue
 214 %type <DagValueList> DagArgList DagArgListNE
 215 %type <FieldList>    ValueList ValueListNE
 216 %type <BitList>      BitList OptBitList RBitList
 217 %type <StrVal>       Declaration OptID OptVarName ObjectName
 218
 219 %start File
 220
 221 %%
 222
 223 ClassID : ID {
 224     $$ = Records.getClass(*$1);
 225     if ($$ == 0) {
 226       err() << "Couldn't find class '" << *$1 << "'!\n";
 227       exit(1);
 228     }
 229     delete $1;
 230   };
 231
 232
 233 // TableGen types...
 234 Type : STRING {                       // string type
 235     $$ = new StringRecTy();
 236   } | BIT {                           // bit type
 237     $$ = new BitRecTy();
 238   } | BITS '<' INTVAL '>' {           // bits<x> type
 239     $$ = new BitsRecTy($3);
 240   } | INT {                           // int type
 241     $$ = new IntRecTy();
 242   } | LIST '<' Type '>'    {          // list<x> type
 243     $$ = new ListRecTy($3);
 244   } | CODE {                          // code type
 245     $$ = new CodeRecTy();
 246   } | DAG {                           // dag type
 247     $$ = new DagRecTy();
 248   } | ClassID {                       // Record Type
 249     $$ = new RecordRecTy($1);
 250   };
 251
 252 OptPrefix : /*empty*/ { $$ = 0; } | FIELD { $$ = 1; };
 253
 254 OptValue : /*empty*/ { $$ = 0; } | '=' Value { $$ = $2; };
 255
 256 Value : INTVAL {
 257     $$ = new IntInit($1);
 258   } | STRVAL {
 259     $$ = new StringInit(*$1);
 260     delete $1;
 261   } | CODEFRAGMENT {
 262     $$ = new CodeInit(*$1);
 263     delete $1;
 264   } | '?' {
 265     $$ = new UnsetInit();
 266   } | '{' ValueList '}' {
 267     BitsInit *Init = new BitsInit($2->size());
 268     for (unsigned i = 0, e = $2->size(); i != e; ++i) {
 269       struct Init *Bit = (*$2)[i]->convertInitializerTo(new BitRecTy());
 270       if (Bit == 0) {
 271         err() << "Element #" << i << " (" << *(*$2)[i]
 272               << ") is not convertable to a bit!\n";
 273         exit(1);
 274       }
 275       Init->setBit($2->size()-i-1, Bit);
 276     }
 277     $$ = Init;
 278     delete $2;
 279   } | ID '<' ValueListNE '>' {
 280     // This is a CLASS<initvalslist> expression.  This is supposed to synthesize
 281     // a new anonymous definition, deriving from CLASS<initvalslist> with no
 282     // body.
 283     Record *Class = Records.getClass(*$1);
 284     if (!Class) {
 285       err() << "Expected a class, got '" << *$1 << "'!\n";
 286       exit(1);
 287     }
 288     delete $1;
 289
 290     static unsigned AnonCounter = 0;
 291     Record *OldRec = CurRec;  // Save CurRec.
 292
 293     // Create the new record, set it as CurRec temporarily.
 294     CurRec = new Record("anonymous.val."+utostr(AnonCounter++));
 295     addSubClass(Class, *$3);    // Add info about the subclass to CurRec.
 296     delete $3;  // Free up the template args.
 297
 298     CurRec->resolveReferences();
 299
 300     Records.addDef(CurRec);
 301
 302     // The result of the expression is a reference to the new record.
 303     $$ = new DefInit(CurRec);
 304
 305     // Restore the old CurRec
 306     CurRec = OldRec;
 307   } | ID {
 308     if (const RecordVal *RV = (CurRec ? CurRec->getValue(*$1) : 0)) {
 309       $$ = new VarInit(*$1, RV->getType());
 310     } else if (CurRec && CurRec->isTemplateArg(CurRec->getName()+":"+*$1)) {
 311       const RecordVal *RV = CurRec->getValue(CurRec->getName()+":"+*$1);
 312       assert(RV && "Template arg doesn't exist??");
 313       $$ = new VarInit(CurRec->getName()+":"+*$1, RV->getType());
 314     } else if (Record *D = Records.getDef(*$1)) {
 315       $$ = new DefInit(D);
 316     } else {
 317       err() << "Variable not defined: '" << *$1 << "'!\n";
 318       exit(1);
 319     }
 320
 321     delete $1;
 322   } | Value '{' BitList '}' {
 323     $$ = $1->convertInitializerBitRange(*$3);
 324     if ($$ == 0) {
 325       err() << "Invalid bit range for value '" << *$1 << "'!\n";
 326       exit(1);
 327     }
 328     delete $3;
 329   } | '[' ValueList ']' {
 330     $$ = new ListInit(*$2);
 331     delete $2;
 332   } | Value '.' ID {
 333     if (!$1->getFieldType(*$3)) {
 334       err() << "Cannot access field '" << *$3 << "' of value '" << *$1 << "!\n";
 335       exit(1);
 336     }
 337     $$ = new FieldInit($1, *$3);
 338     delete $3;
 339   } | '(' ID DagArgList ')' {
 340     Record *D = Records.getDef(*$2);
 341     if (D == 0) {
 342       err() << "Invalid def '" << *$2 << "'!\n";
 343       exit(1);
 344     }
 345     $$ = new DagInit(D, *$3);
 346     delete $2; delete $3;
 347   } | Value '[' BitList ']' {
 348     std::reverse($3->begin(), $3->end());
 349     $$ = $1->convertInitListSlice(*$3);
 350     if ($$ == 0) {
 351       err() << "Invalid list slice for value '" << *$1 << "'!\n";
 352       exit(1);
 353     }
 354     delete $3;
 355   } | SHLTOK '(' Value ',' Value ')' {
 356     $$ = $3->getBinaryOp(Init::SHL, $5);
 357     if ($$ == 0) {
 358       err() << "Cannot shift values '" << *$3 << "' and '" << *$5 << "'!\n";
 359       exit(1);
 360     }
 361   } | SRATOK '(' Value ',' Value ')' {
 362     $$ = $3->getBinaryOp(Init::SRA, $5);
 363     if ($$ == 0) {
 364       err() << "Cannot shift values '" << *$3 << "' and '" << *$5 << "'!\n";
 365       exit(1);
 366     }
 367   } | SRLTOK '(' Value ',' Value ')' {
 368     $$ = $3->getBinaryOp(Init::SRL, $5);
 369     if ($$ == 0) {
 370       err() << "Cannot shift values '" << *$3 << "' and '" << *$5 << "'!\n";
 371       exit(1);
 372     }
 373   };
 374
 375 OptVarName : /* empty */ {
 376     $$ = new std::string();
 377   }
 378   | ':' VARNAME {
 379     $$ = $2;
 380   };
 381
 382 DagArgListNE : Value OptVarName {
 383     $$ = new std::vector<std::pair<Init*, std::string> >();
 384     $$->push_back(std::make_pair($1, *$2));
 385     delete $2;
 386   }
 387   | DagArgListNE ',' Value OptVarName {
 388     $1->push_back(std::make_pair($3, *$4));
 389     delete $4;
 390     $$ = $1;
 391   };
 392
 393 DagArgList : /*empty*/ {
 394     $$ = new std::vector<std::pair<Init*, std::string> >();
 395   }
 396   | DagArgListNE { $$ = $1; };
 397
 398
 399 RBitList : INTVAL {
 400     $$ = new std::vector<unsigned>();
 401     $$->push_back($1);
 402   } | INTVAL '-' INTVAL {
 403     if ($1 < 0 || $3 < 0) {
 404       err() << "Invalid range: " << $1 << "-" << $3 << "!\n";
 405       exit(1);
 406     }
 407     $$ = new std::vector<unsigned>();
 408     if ($1 < $3) {
 409       for (int i = $1; i <= $3; ++i)
 410         $$->push_back(i);
 411     } else {
 412       for (int i = $1; i >= $3; --i)
 413         $$->push_back(i);
 414     }
 415   } | INTVAL INTVAL {
 416     $2 = -$2;
 417     if ($1 < 0 || $2 < 0) {
 418       err() << "Invalid range: " << $1 << "-" << $2 << "!\n";
 419       exit(1);
 420     }
 421     $$ = new std::vector<unsigned>();
 422     if ($1 < $2) {
 423       for (int i = $1; i <= $2; ++i)
 424         $$->push_back(i);
 425     } else {
 426       for (int i = $1; i >= $2; --i)
 427         $$->push_back(i);
 428     }
 429   } | RBitList ',' INTVAL {
 430     ($$=$1)->push_back($3);
 431   } | RBitList ',' INTVAL '-' INTVAL {
 432     if ($3 < 0 || $5 < 0) {
 433       err() << "Invalid range: " << $3 << "-" << $5 << "!\n";
 434       exit(1);
 435     }
 436     $$ = $1;
 437     if ($3 < $5) {
 438       for (int i = $3; i <= $5; ++i)
 439         $$->push_back(i);
 440     } else {
 441       for (int i = $3; i >= $5; --i)
 442         $$->push_back(i);
 443     }
 444   } | RBitList ',' INTVAL INTVAL {
 445     $4 = -$4;
 446     if ($3 < 0 || $4 < 0) {
 447       err() << "Invalid range: " << $3 << "-" << $4 << "!\n";
 448       exit(1);
 449     }
 450     $$ = $1;
 451     if ($3 < $4) {
 452       for (int i = $3; i <= $4; ++i)
 453         $$->push_back(i);
 454     } else {
 455       for (int i = $3; i >= $4; --i)
 456         $$->push_back(i);
 457     }
 458   };
 459
 460 BitList : RBitList { $$ = $1; std::reverse($1->begin(), $1->end()); };
 461
 462 OptBitList : /*empty*/ { $$ = 0; } | '{' BitList '}' { $$ = $2; };
 463
 464
 465
 466 ValueList : /*empty*/ {
 467     $$ = new std::vector<Init*>();
 468   } | ValueListNE {
 469     $$ = $1;
 470   };
 471
 472 ValueListNE : Value {
 473     $$ = new std::vector<Init*>();
 474     $$->push_back($1);
 475   } | ValueListNE ',' Value {
 476     ($$ = $1)->push_back($3);
 477   };
 478
 479 Declaration : OptPrefix Type ID OptValue {
 480   std::string DecName = *$3;
 481   if (ParsingTemplateArgs)
 482     DecName = CurRec->getName() + ":" + DecName;
 483
 484   addValue(RecordVal(DecName, $2, $1));
 485   setValue(DecName, 0, $4);
 486   $$ = new std::string(DecName);
 487 };
 488
 489 BodyItem : Declaration ';' {
 490   delete $1;
 491 } | LET ID OptBitList '=' Value ';' {
 492   setValue(*$2, $3, $5);
 493   delete $2;
 494   delete $3;
 495 };
 496
 497 BodyList : /*empty*/ | BodyList BodyItem;
 498 Body : ';' | '{' BodyList '}';
 499
 500 SubClassRef : ClassID {
 501     $$ = new SubClassRefTy($1, new std::vector<Init*>());
 502   } | ClassID '<' ValueListNE '>' {
 503     $$ = new SubClassRefTy($1, $3);
 504   };
 505
 506 ClassListNE : SubClassRef {
 507     $$ = new std::vector<SubClassRefTy>();
 508     $$->push_back(*$1);
 509     delete $1;
 510   }
 511   | ClassListNE ',' SubClassRef {
 512     ($$=$1)->push_back(*$3);
 513     delete $3;
 514   };
 515
 516 ClassList : /*empty */ {
 517     $$ = new std::vector<SubClassRefTy>();
 518   }
 519   | ':' ClassListNE {
 520     $$ = $2;
 521   };
 522
 523 DeclListNE : Declaration {
 524   CurRec->addTemplateArg(*$1);
 525   delete $1;
 526 } | DeclListNE ',' Declaration {
 527   CurRec->addTemplateArg(*$3);
 528   delete $3;
 529 };
 530
 531 TemplateArgList : '<' DeclListNE '>' {};
 532 OptTemplateArgList : /*empty*/ | TemplateArgList;
 533
 534 OptID : ID { $$ = $1; } | /*empty*/ { $$ = new std::string(); };
 535
 536 ObjectName : OptID {
 537   static unsigned AnonCounter = 0;
 538   if ($1->empty())
 539     *$1 = "anonymous."+utostr(AnonCounter++);
 540   $$ = $1;
 541 };
 542
 543 ClassName : ObjectName {
 544   // If a class of this name already exists, it must be a forward ref.
 545   if ((CurRec = Records.getClass(*$1))) {
 546     // If the body was previously defined, this is an error.
 547     if (!CurRec->getValues().empty() ||
 548         !CurRec->getSuperClasses().empty() ||
 549         !CurRec->getTemplateArgs().empty()) {
 550       err() << "Class '" << CurRec->getName() << "' already defined!\n";
 551       exit(1);
 552     }
 553   } else {
 554     // If this is the first reference to this class, create and add it.
 555     CurRec = new Record(*$1);
 556     Records.addClass(CurRec);
 557   }
 558   delete $1;
 559 };
 560
 561 DefName : ObjectName {
 562   CurRec = new Record(*$1);
 563   delete $1;
 564
 565   // Ensure redefinition doesn't happen.
 566   if (Records.getDef(CurRec->getName())) {
 567     err() << "Def '" << CurRec->getName() << "' already defined!\n";
 568     exit(1);
 569   }
 570   Records.addDef(CurRec);
 571 };
 572
 573 ObjectBody : ClassList {
 574            for (unsigned i = 0, e = $1->size(); i != e; ++i) {
 575              addSubClass((*$1)[i].first, *(*$1)[i].second);
 576              // Delete the template arg values for the class
 577              delete (*$1)[i].second;
 578            }
 579            delete $1;   // Delete the class list...
 580
 581            // Process any variables on the set stack...
 582            for (unsigned i = 0, e = LetStack.size(); i != e; ++i)
 583              for (unsigned j = 0, e = LetStack[i].size(); j != e; ++j)
 584                setValue(LetStack[i][j].Name,
 585                         LetStack[i][j].HasBits ? &LetStack[i][j].Bits : 0,
 586                         LetStack[i][j].Value);
 587          } Body {
 588            $$ = CurRec;
 589            CurRec = 0;
 590          };
 591
 592 ClassInst : CLASS ClassName {
 593                 ParsingTemplateArgs = true;
 594             } OptTemplateArgList {
 595                 ParsingTemplateArgs = false;
 596             } ObjectBody {
 597         $$ = $6;
 598      };
 599
 600 DefInst : DEF DefName ObjectBody {
 601   $3->resolveReferences();
 602
 603   // If ObjectBody has template arguments, it's an error.
 604   assert($3->getTemplateArgs().empty() && "How'd this get template args?");
 605   $$ = $3;
 606 };
 607
 608
 609 Object : ClassInst | DefInst;
 610
 611 LETItem : ID OptBitList '=' Value {
 612   LetStack.back().push_back(LetRecord(*$1, $2, $4));
 613   delete $1; delete $2;
 614 };
 615
 616 LETList : LETItem | LETList ',' LETItem;
 617
 618 // LETCommand - A 'LET' statement start...
 619 LETCommand : LET { LetStack.push_back(std::vector<LetRecord>()); } LETList IN;
 620
 621 // Support Set commands wrapping objects... both with and without braces.
 622 Object : LETCommand '{' ObjectList '}' {
 623     LetStack.pop_back();
 624   }
 625   | LETCommand Object {
 626     LetStack.pop_back();
 627   };
 628
 629 ObjectList : Object {} | ObjectList Object {};
 630
 631 File : ObjectList {};
 632
 633 %%
 634
 635 int yyerror(const char *ErrorMsg) {
 636   err() << "Error parsing: " << ErrorMsg << "\n";
 637   exit(1);
 638 }