utils/TableGen/TGParser.cpp

   1 //===- TGParser.cpp - Parser for TableGen Files ---------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Implement the Parser for TableGen.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include <algorithm>
  15
  16 #include "TGParser.h"
  17 #include "Record.h"
  18 #include "llvm/ADT/StringExtras.h"
  19 #include "llvm/Support/Streams.h"
  20 using namespace llvm;
  21
  22 //===----------------------------------------------------------------------===//
  23 // Support Code for the Semantic Actions.
  24 //===----------------------------------------------------------------------===//
  25
  26 namespace llvm {
  27 struct SubClassReference {
  28   TGLoc RefLoc;
  29   Record *Rec;
  30   std::vector<Init*> TemplateArgs;
  31   SubClassReference() : Rec(0) {}
  32
  33   bool isInvalid() const { return Rec == 0; }
  34 };
  35
  36 struct SubMultiClassReference {
  37   TGLoc RefLoc;
  38   MultiClass *MC;
  39   std::vector<Init*> TemplateArgs;
  40   SubMultiClassReference() : MC(0) {}
  41
  42   bool isInvalid() const { return MC == 0; }
  43   void dump() const;
  44 };
  45
  46 void SubMultiClassReference::dump() const {
  47   cerr << "Multiclass:\n";
  48
  49   MC->dump();
  50
  51   cerr << "Template args:\n";
  52   for (std::vector<Init *>::const_iterator i = TemplateArgs.begin(),
  53          iend = TemplateArgs.end();
  54        i != iend;
  55        ++i) {
  56     (*i)->dump();
  57   }
  58 }
  59
  60 } // end namespace llvm
  61
  62 bool TGParser::AddValue(Record *CurRec, TGLoc Loc, const RecordVal &RV) {
  63   if (CurRec == 0)
  64     CurRec = &CurMultiClass->Rec;
  65
  66   if (RecordVal *ERV = CurRec->getValue(RV.getName())) {
  67     // The value already exists in the class, treat this as a set.
  68     if (ERV->setValue(RV.getValue()))
  69       return Error(Loc, "New definition of '" + RV.getName() + "' of type '" +
  70                    RV.getType()->getAsString() + "' is incompatible with " +
  71                    "previous definition of type '" +
  72                    ERV->getType()->getAsString() + "'");
  73   } else {
  74     CurRec->addValue(RV);
  75   }
  76   return false;
  77 }
  78
  79 /// SetValue -
  80 /// Return true on error, false on success.
  81 bool TGParser::SetValue(Record *CurRec, TGLoc Loc, const std::string &ValName,
  82                         const std::vector<unsigned> &BitList, Init *V) {
  83   if (!V) return false;
  84
  85   if (CurRec == 0) CurRec = &CurMultiClass->Rec;
  86
  87   RecordVal *RV = CurRec->getValue(ValName);
  88   if (RV == 0)
  89     return Error(Loc, "Value '" + ValName + "' unknown!");
  90
  91   // Do not allow assignments like 'X = X'.  This will just cause infinite loops
  92   // in the resolution machinery.
  93   if (BitList.empty())
  94     if (VarInit *VI = dynamic_cast<VarInit*>(V))
  95       if (VI->getName() == ValName)
  96         return false;
  97
  98   // If we are assigning to a subset of the bits in the value... then we must be
  99   // assigning to a field of BitsRecTy, which must have a BitsInit
 100   // initializer.
 101   //
 102   if (!BitList.empty()) {
 103     BitsInit *CurVal = dynamic_cast<BitsInit*>(RV->getValue());
 104     if (CurVal == 0)
 105       return Error(Loc, "Value '" + ValName + "' is not a bits type");
 106
 107     // Convert the incoming value to a bits type of the appropriate size...
 108     Init *BI = V->convertInitializerTo(new BitsRecTy(BitList.size()));
 109     if (BI == 0) {
 110       V->convertInitializerTo(new BitsRecTy(BitList.size()));
 111       return Error(Loc, "Initializer is not compatible with bit range");
 112     }
 113
 114     // We should have a BitsInit type now.
 115     BitsInit *BInit = dynamic_cast<BitsInit*>(BI);
 116     assert(BInit != 0);
 117
 118     BitsInit *NewVal = new BitsInit(CurVal->getNumBits());
 119
 120     // Loop over bits, assigning values as appropriate.
 121     for (unsigned i = 0, e = BitList.size(); i != e; ++i) {
 122       unsigned Bit = BitList[i];
 123       if (NewVal->getBit(Bit))
 124         return Error(Loc, "Cannot set bit #" + utostr(Bit) + " of value '" +
 125                      ValName + "' more than once");
 126       NewVal->setBit(Bit, BInit->getBit(i));
 127     }
 128
 129     for (unsigned i = 0, e = CurVal->getNumBits(); i != e; ++i)
 130       if (NewVal->getBit(i) == 0)
 131         NewVal->setBit(i, CurVal->getBit(i));
 132
 133     V = NewVal;
 134   }
 135
 136   if (RV->setValue(V))
 137    return Error(Loc, "Value '" + ValName + "' of type '" +
 138                 RV->getType()->getAsString() +
 139                 "' is incompatible with initializer '" + V->getAsString() +"'");
 140   return false;
 141 }
 142
 143 /// AddSubClass - Add SubClass as a subclass to CurRec, resolving its template
 144 /// args as SubClass's template arguments.
 145 bool TGParser::AddSubClass(Record *CurRec, SubClassReference &SubClass) {
 146   Record *SC = SubClass.Rec;
 147   // Add all of the values in the subclass into the current class.
 148   const std::vector<RecordVal> &Vals = SC->getValues();
 149   for (unsigned i = 0, e = Vals.size(); i != e; ++i)
 150     if (AddValue(CurRec, SubClass.RefLoc, Vals[i]))
 151       return true;
 152
 153   const std::vector<std::string> &TArgs = SC->getTemplateArgs();
 154
 155   // Ensure that an appropriate number of template arguments are specified.
 156   if (TArgs.size() < SubClass.TemplateArgs.size())
 157     return Error(SubClass.RefLoc, "More template args specified than expected");
 158
 159   // Loop over all of the template arguments, setting them to the specified
 160   // value or leaving them as the default if necessary.
 161   for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
 162     if (i < SubClass.TemplateArgs.size()) {
 163       // If a value is specified for this template arg, set it now.
 164       if (SetValue(CurRec, SubClass.RefLoc, TArgs[i], std::vector<unsigned>(),
 165                    SubClass.TemplateArgs[i]))
 166         return true;
 167
 168       // Resolve it next.
 169       CurRec->resolveReferencesTo(CurRec->getValue(TArgs[i]));
 170
 171       // Now remove it.
 172       CurRec->removeValue(TArgs[i]);
 173
 174     } else if (!CurRec->getValue(TArgs[i])->getValue()->isComplete()) {
 175       return Error(SubClass.RefLoc,"Value not specified for template argument #"
 176                    + utostr(i) + " (" + TArgs[i] + ") of subclass '" +
 177                    SC->getName() + "'!");
 178     }
 179   }
 180
 181   // Since everything went well, we can now set the "superclass" list for the
 182   // current record.
 183   const std::vector<Record*> &SCs = SC->getSuperClasses();
 184   for (unsigned i = 0, e = SCs.size(); i != e; ++i) {
 185     if (CurRec->isSubClassOf(SCs[i]))
 186       return Error(SubClass.RefLoc,
 187                    "Already subclass of '" + SCs[i]->getName() + "'!\n");
 188     CurRec->addSuperClass(SCs[i]);
 189   }
 190
 191   if (CurRec->isSubClassOf(SC))
 192     return Error(SubClass.RefLoc,
 193                  "Already subclass of '" + SC->getName() + "'!\n");
 194   CurRec->addSuperClass(SC);
 195   return false;
 196 }
 197
 198 /// AddSubMultiClass - Add SubMultiClass as a subclass to
 199 /// CurMultiClass, resolving its template args as SubMultiClass's
 200 /// template arguments.
 201 bool TGParser::AddSubMultiClass(MultiClass *CurMultiClass,
 202                                 class SubMultiClassReference &SubMultiClass) {
 203   MultiClass *SMC = SubMultiClass.MC;
 204   Record *CurRec = &CurMultiClass->Rec;
 205
 206   const std::vector<RecordVal> &MCVals = CurMultiClass->Rec.getValues();
 207
 208   // Add all of the values in the subclass into the current class.
 209   const std::vector<RecordVal> &SMCVals = SMC->Rec.getValues();
 210   for (unsigned i = 0, e = SMCVals.size(); i != e; ++i)
 211     if (AddValue(CurRec, SubMultiClass.RefLoc, SMCVals[i]))
 212       return true;
 213
 214   int newDefStart = CurMultiClass->DefPrototypes.size();
 215
 216   // Add all of the defs in the subclass into the current multiclass.
 217   for (MultiClass::RecordVector::const_iterator i = SMC->DefPrototypes.begin(),
 218          iend = SMC->DefPrototypes.end();
 219        i != iend;
 220        ++i) {
 221     // Clone the def and add it to the current multiclass
 222     Record *NewDef = new Record(**i);
 223
 224     // Add all of the values in the superclass into the current def.
 225     for (unsigned i = 0, e = MCVals.size(); i != e; ++i)
 226       if (AddValue(NewDef, SubMultiClass.RefLoc, MCVals[i]))
 227         return true;
 228
 229     CurMultiClass->DefPrototypes.push_back(NewDef);
 230   }
 231
 232   const std::vector<std::string> &SMCTArgs = SMC->Rec.getTemplateArgs();
 233
 234   // Ensure that an appropriate number of template arguments are
 235   // specified.
 236   if (SMCTArgs.size() < SubMultiClass.TemplateArgs.size())
 237     return Error(SubMultiClass.RefLoc,
 238                  "More template args specified than expected");
 239
 240   // Loop over all of the template arguments, setting them to the specified
 241   // value or leaving them as the default if necessary.
 242   for (unsigned i = 0, e = SMCTArgs.size(); i != e; ++i) {
 243     if (i < SubMultiClass.TemplateArgs.size()) {
 244       // If a value is specified for this template arg, set it in the
 245       // superclass now.
 246       if (SetValue(CurRec, SubMultiClass.RefLoc, SMCTArgs[i],
 247                    std::vector<unsigned>(),
 248                    SubMultiClass.TemplateArgs[i]))
 249         return true;
 250
 251       // Resolve it next.
 252       CurRec->resolveReferencesTo(CurRec->getValue(SMCTArgs[i]));
 253
 254       // Now remove it.
 255       CurRec->removeValue(SMCTArgs[i]);
 256
 257       // If a value is specified for this template arg, set it in the
 258       // new defs now.
 259       for (MultiClass::RecordVector::iterator j =
 260              CurMultiClass->DefPrototypes.begin() + newDefStart,
 261              jend = CurMultiClass->DefPrototypes.end();
 262            j != jend;
 263            ++j) {
 264         Record *Def = *j;
 265
 266         if (SetValue(Def, SubMultiClass.RefLoc, SMCTArgs[i],
 267                      std::vector<unsigned>(),
 268                      SubMultiClass.TemplateArgs[i]))
 269           return true;
 270
 271         // Resolve it next.
 272         Def->resolveReferencesTo(Def->getValue(SMCTArgs[i]));
 273
 274         // Now remove it
 275         Def->removeValue(SMCTArgs[i]);
 276       }
 277     } else if (!CurRec->getValue(SMCTArgs[i])->getValue()->isComplete()) {
 278       return Error(SubMultiClass.RefLoc,
 279                    "Value not specified for template argument #"
 280                    + utostr(i) + " (" + SMCTArgs[i] + ") of subclass '" +
 281                    SMC->Rec.getName() + "'!");
 282     }
 283   }
 284
 285   return false;
 286 }
 287
 288 //===----------------------------------------------------------------------===//
 289 // Parser Code
 290 //===----------------------------------------------------------------------===//
 291
 292 /// isObjectStart - Return true if this is a valid first token for an Object.
 293 static bool isObjectStart(tgtok::TokKind K) {
 294   return K == tgtok::Class || K == tgtok::Def ||
 295          K == tgtok::Defm || K == tgtok::Let || K == tgtok::MultiClass;
 296 }
 297
 298 /// ParseObjectName - If an object name is specified, return it.  Otherwise,
 299 /// return an anonymous name.
 300 ///   ObjectName ::= ID
 301 ///   ObjectName ::= /*empty*/
 302 ///
 303 std::string TGParser::ParseObjectName() {
 304   if (Lex.getCode() == tgtok::Id) {
 305     std::string Ret = Lex.getCurStrVal();
 306     Lex.Lex();
 307     return Ret;
 308   }
 309
 310   static unsigned AnonCounter = 0;
 311   return "anonymous."+utostr(AnonCounter++);
 312 }
 313
 314
 315 /// ParseClassID - Parse and resolve a reference to a class name.  This returns
 316 /// null on error.
 317 ///
 318 ///    ClassID ::= ID
 319 ///
 320 Record *TGParser::ParseClassID() {
 321   if (Lex.getCode() != tgtok::Id) {
 322     TokError("expected name for ClassID");
 323     return 0;
 324   }
 325
 326   Record *Result = Records.getClass(Lex.getCurStrVal());
 327   if (Result == 0)
 328     TokError("Couldn't find class '" + Lex.getCurStrVal() + "'");
 329
 330   Lex.Lex();
 331   return Result;
 332 }
 333
 334 /// ParseMultiClassID - Parse and resolve a reference to a multiclass name.  This returns
 335 /// null on error.
 336 ///
 337 ///    MultiClassID ::= ID
 338 ///
 339 MultiClass *TGParser::ParseMultiClassID() {
 340   if (Lex.getCode() != tgtok::Id) {
 341     TokError("expected name for ClassID");
 342     return 0;
 343   }
 344
 345   MultiClass *Result = MultiClasses[Lex.getCurStrVal()];
 346   if (Result == 0)
 347     TokError("Couldn't find class '" + Lex.getCurStrVal() + "'");
 348
 349   Lex.Lex();
 350   return Result;
 351 }
 352
 353 Record *TGParser::ParseDefmID() {
 354   if (Lex.getCode() != tgtok::Id) {
 355     TokError("expected multiclass name");
 356     return 0;
 357   }
 358
 359   MultiClass *MC = MultiClasses[Lex.getCurStrVal()];
 360   if (MC == 0) {
 361     TokError("Couldn't find multiclass '" + Lex.getCurStrVal() + "'");
 362     return 0;
 363   }
 364
 365   Lex.Lex();
 366   return &MC->Rec;
 367 }
 368
 369
 370
 371 /// ParseSubClassReference - Parse a reference to a subclass or to a templated
 372 /// subclass.  This returns a SubClassRefTy with a null Record* on error.
 373 ///
 374 ///  SubClassRef ::= ClassID
 375 ///  SubClassRef ::= ClassID '<' ValueList '>'
 376 ///
 377 SubClassReference TGParser::
 378 ParseSubClassReference(Record *CurRec, bool isDefm) {
 379   SubClassReference Result;
 380   Result.RefLoc = Lex.getLoc();
 381
 382   if (isDefm)
 383     Result.Rec = ParseDefmID();
 384   else
 385     Result.Rec = ParseClassID();
 386   if (Result.Rec == 0) return Result;
 387
 388   // If there is no template arg list, we're done.
 389   if (Lex.getCode() != tgtok::less)
 390     return Result;
 391   Lex.Lex();  // Eat the '<'
 392
 393   if (Lex.getCode() == tgtok::greater) {
 394     TokError("subclass reference requires a non-empty list of template values");
 395     Result.Rec = 0;
 396     return Result;
 397   }
 398
 399   Result.TemplateArgs = ParseValueList(CurRec);
 400   if (Result.TemplateArgs.empty()) {
 401     Result.Rec = 0;   // Error parsing value list.
 402     return Result;
 403   }
 404
 405   if (Lex.getCode() != tgtok::greater) {
 406     TokError("expected '>' in template value list");
 407     Result.Rec = 0;
 408     return Result;
 409   }
 410   Lex.Lex();
 411
 412   return Result;
 413 }
 414
 415 /// ParseSubMultiClassReference - Parse a reference to a subclass or to a templated
 416 /// submulticlass.  This returns a SubMultiClassRefTy with a null Record* on error.
 417 ///
 418 ///  SubMultiClassRef ::= MultiClassID
 419 ///  SubMultiClassRef ::= MultiClassID '<' ValueList '>'
 420 ///
 421 SubMultiClassReference TGParser::
 422 ParseSubMultiClassReference(MultiClass *CurMC) {
 423   SubMultiClassReference Result;
 424   Result.RefLoc = Lex.getLoc();
 425
 426   Result.MC = ParseMultiClassID();
 427   if (Result.MC == 0) return Result;
 428
 429   // If there is no template arg list, we're done.
 430   if (Lex.getCode() != tgtok::less)
 431     return Result;
 432   Lex.Lex();  // Eat the '<'
 433
 434   if (Lex.getCode() == tgtok::greater) {
 435     TokError("subclass reference requires a non-empty list of template values");
 436     Result.MC = 0;
 437     return Result;
 438   }
 439
 440   Result.TemplateArgs = ParseValueList(&CurMC->Rec);
 441   if (Result.TemplateArgs.empty()) {
 442     Result.MC = 0;   // Error parsing value list.
 443     return Result;
 444   }
 445
 446   if (Lex.getCode() != tgtok::greater) {
 447     TokError("expected '>' in template value list");
 448     Result.MC = 0;
 449     return Result;
 450   }
 451   Lex.Lex();
 452
 453   return Result;
 454 }
 455
 456 /// ParseRangePiece - Parse a bit/value range.
 457 ///   RangePiece ::= INTVAL
 458 ///   RangePiece ::= INTVAL '-' INTVAL
 459 ///   RangePiece ::= INTVAL INTVAL
 460 bool TGParser::ParseRangePiece(std::vector<unsigned> &Ranges) {
 461   if (Lex.getCode() != tgtok::IntVal) {
 462     TokError("expected integer or bitrange");
 463     return true;
 464   }
 465   int64_t Start = Lex.getCurIntVal();
 466   int64_t End;
 467
 468   if (Start < 0)
 469     return TokError("invalid range, cannot be negative");
 470
 471   switch (Lex.Lex()) {  // eat first character.
 472   default:
 473     Ranges.push_back(Start);
 474     return false;
 475   case tgtok::minus:
 476     if (Lex.Lex() != tgtok::IntVal) {
 477       TokError("expected integer value as end of range");
 478       return true;
 479     }
 480     End = Lex.getCurIntVal();
 481     break;
 482   case tgtok::IntVal:
 483     End = -Lex.getCurIntVal();
 484     break;
 485   }
 486   if (End < 0)
 487     return TokError("invalid range, cannot be negative");
 488   Lex.Lex();
 489
 490   // Add to the range.
 491   if (Start < End) {
 492     for (; Start <= End; ++Start)
 493       Ranges.push_back(Start);
 494   } else {
 495     for (; Start >= End; --Start)
 496       Ranges.push_back(Start);
 497   }
 498   return false;
 499 }
 500
 501 /// ParseRangeList - Parse a list of scalars and ranges into scalar values.
 502 ///
 503 ///   RangeList ::= RangePiece (',' RangePiece)*
 504 ///
 505 std::vector<unsigned> TGParser::ParseRangeList() {
 506   std::vector<unsigned> Result;
 507
 508   // Parse the first piece.
 509   if (ParseRangePiece(Result))
 510     return std::vector<unsigned>();
 511   while (Lex.getCode() == tgtok::comma) {
 512     Lex.Lex();  // Eat the comma.
 513
 514     // Parse the next range piece.
 515     if (ParseRangePiece(Result))
 516       return std::vector<unsigned>();
 517   }
 518   return Result;
 519 }
 520
 521 /// ParseOptionalRangeList - Parse either a range list in <>'s or nothing.
 522 ///   OptionalRangeList ::= '<' RangeList '>'
 523 ///   OptionalRangeList ::= /*empty*/
 524 bool TGParser::ParseOptionalRangeList(std::vector<unsigned> &Ranges) {
 525   if (Lex.getCode() != tgtok::less)
 526     return false;
 527
 528   TGLoc StartLoc = Lex.getLoc();
 529   Lex.Lex(); // eat the '<'
 530
 531   // Parse the range list.
 532   Ranges = ParseRangeList();
 533   if (Ranges.empty()) return true;
 534
 535   if (Lex.getCode() != tgtok::greater) {
 536     TokError("expected '>' at end of range list");
 537     return Error(StartLoc, "to match this '<'");
 538   }
 539   Lex.Lex();   // eat the '>'.
 540   return false;
 541 }
 542
 543 /// ParseOptionalBitList - Parse either a bit list in {}'s or nothing.
 544 ///   OptionalBitList ::= '{' RangeList '}'
 545 ///   OptionalBitList ::= /*empty*/
 546 bool TGParser::ParseOptionalBitList(std::vector<unsigned> &Ranges) {
 547   if (Lex.getCode() != tgtok::l_brace)
 548     return false;
 549
 550   TGLoc StartLoc = Lex.getLoc();
 551   Lex.Lex(); // eat the '{'
 552
 553   // Parse the range list.
 554   Ranges = ParseRangeList();
 555   if (Ranges.empty()) return true;
 556
 557   if (Lex.getCode() != tgtok::r_brace) {
 558     TokError("expected '}' at end of bit list");
 559     return Error(StartLoc, "to match this '{'");
 560   }
 561   Lex.Lex();   // eat the '}'.
 562   return false;
 563 }
 564
 565
 566 /// ParseType - Parse and return a tblgen type.  This returns null on error.
 567 ///
 568 ///   Type ::= STRING                       // string type
 569 ///   Type ::= BIT                          // bit type
 570 ///   Type ::= BITS '<' INTVAL '>'          // bits<x> type
 571 ///   Type ::= INT                          // int type
 572 ///   Type ::= LIST '<' Type '>'            // list<x> type
 573 ///   Type ::= CODE                         // code type
 574 ///   Type ::= DAG                          // dag type
 575 ///   Type ::= ClassID                      // Record Type
 576 ///
 577 RecTy *TGParser::ParseType() {
 578   switch (Lex.getCode()) {
 579   default: TokError("Unknown token when expecting a type"); return 0;
 580   case tgtok::String: Lex.Lex(); return new StringRecTy();
 581   case tgtok::Bit:    Lex.Lex(); return new BitRecTy();
 582   case tgtok::Int:    Lex.Lex(); return new IntRecTy();
 583   case tgtok::Code:   Lex.Lex(); return new CodeRecTy();
 584   case tgtok::Dag:    Lex.Lex(); return new DagRecTy();
 585   case tgtok::Id:
 586     if (Record *R = ParseClassID()) return new RecordRecTy(R);
 587     return 0;
 588   case tgtok::Bits: {
 589     if (Lex.Lex() != tgtok::less) { // Eat 'bits'
 590       TokError("expected '<' after bits type");
 591       return 0;
 592     }
 593     if (Lex.Lex() != tgtok::IntVal) {  // Eat '<'
 594       TokError("expected integer in bits<n> type");
 595       return 0;
 596     }
 597     uint64_t Val = Lex.getCurIntVal();
 598     if (Lex.Lex() != tgtok::greater) {  // Eat count.
 599       TokError("expected '>' at end of bits<n> type");
 600       return 0;
 601     }
 602     Lex.Lex();  // Eat '>'
 603     return new BitsRecTy(Val);
 604   }
 605   case tgtok::List: {
 606     if (Lex.Lex() != tgtok::less) { // Eat 'bits'
 607       TokError("expected '<' after list type");
 608       return 0;
 609     }
 610     Lex.Lex();  // Eat '<'
 611     RecTy *SubType = ParseType();
 612     if (SubType == 0) return 0;
 613
 614     if (Lex.getCode() != tgtok::greater) {
 615       TokError("expected '>' at end of list<ty> type");
 616       return 0;
 617     }
 618     Lex.Lex();  // Eat '>'
 619     return new ListRecTy(SubType);
 620   }
 621   }
 622 }
 623
 624 /// ParseIDValue - Parse an ID as a value and decode what it means.
 625 ///
 626 ///  IDValue ::= ID [def local value]
 627 ///  IDValue ::= ID [def template arg]
 628 ///  IDValue ::= ID [multiclass local value]
 629 ///  IDValue ::= ID [multiclass template argument]
 630 ///  IDValue ::= ID [def name]
 631 ///
 632 Init *TGParser::ParseIDValue(Record *CurRec) {
 633   assert(Lex.getCode() == tgtok::Id && "Expected ID in ParseIDValue");
 634   std::string Name = Lex.getCurStrVal();
 635   TGLoc Loc = Lex.getLoc();
 636   Lex.Lex();
 637   return ParseIDValue(CurRec, Name, Loc);
 638 }
 639
 640 /// ParseIDValue - This is just like ParseIDValue above, but it assumes the ID
 641 /// has already been read.
 642 Init *TGParser::ParseIDValue(Record *CurRec,
 643                              const std::string &Name, TGLoc NameLoc) {
 644   if (CurRec) {
 645     if (const RecordVal *RV = CurRec->getValue(Name))
 646       return new VarInit(Name, RV->getType());
 647
 648     std::string TemplateArgName = CurRec->getName()+":"+Name;
 649     if (CurRec->isTemplateArg(TemplateArgName)) {
 650       const RecordVal *RV = CurRec->getValue(TemplateArgName);
 651       assert(RV && "Template arg doesn't exist??");
 652       return new VarInit(TemplateArgName, RV->getType());
 653     }
 654   }
 655
 656   if (CurMultiClass) {
 657     std::string MCName = CurMultiClass->Rec.getName()+"::"+Name;
 658     if (CurMultiClass->Rec.isTemplateArg(MCName)) {
 659       const RecordVal *RV = CurMultiClass->Rec.getValue(MCName);
 660       assert(RV && "Template arg doesn't exist??");
 661       return new VarInit(MCName, RV->getType());
 662     }
 663   }
 664
 665   if (Record *D = Records.getDef(Name))
 666     return new DefInit(D);
 667
 668   Error(NameLoc, "Variable not defined: '" + Name + "'");
 669   return 0;
 670 }
 671
 672 /// ParseSimpleValue - Parse a tblgen value.  This returns null on error.
 673 ///
 674 ///   SimpleValue ::= IDValue
 675 ///   SimpleValue ::= INTVAL
 676 ///   SimpleValue ::= STRVAL+
 677 ///   SimpleValue ::= CODEFRAGMENT
 678 ///   SimpleValue ::= '?'
 679 ///   SimpleValue ::= '{' ValueList '}'
 680 ///   SimpleValue ::= ID '<' ValueListNE '>'
 681 ///   SimpleValue ::= '[' ValueList ']'
 682 ///   SimpleValue ::= '(' IDValue DagArgList ')'
 683 ///   SimpleValue ::= CONCATTOK '(' Value ',' Value ')'
 684 ///   SimpleValue ::= SHLTOK '(' Value ',' Value ')'
 685 ///   SimpleValue ::= SRATOK '(' Value ',' Value ')'
 686 ///   SimpleValue ::= SRLTOK '(' Value ',' Value ')'
 687 ///   SimpleValue ::= STRCONCATTOK '(' Value ',' Value ')'
 688 ///
 689 Init *TGParser::ParseSimpleValue(Record *CurRec) {
 690   Init *R = 0;
 691   switch (Lex.getCode()) {
 692   default: TokError("Unknown token when parsing a value"); break;
 693   case tgtok::IntVal: R = new IntInit(Lex.getCurIntVal()); Lex.Lex(); break;
 694   case tgtok::StrVal: {
 695     std::string Val = Lex.getCurStrVal();
 696     Lex.Lex();
 697
 698     // Handle multiple consecutive concatenated strings.
 699     while (Lex.getCode() == tgtok::StrVal) {
 700       Val += Lex.getCurStrVal();
 701       Lex.Lex();
 702     }
 703
 704     R = new StringInit(Val);
 705     break;
 706   }
 707   case tgtok::CodeFragment:
 708       R = new CodeInit(Lex.getCurStrVal()); Lex.Lex(); break;
 709   case tgtok::question: R = new UnsetInit(); Lex.Lex(); break;
 710   case tgtok::Id: {
 711     TGLoc NameLoc = Lex.getLoc();
 712     std::string Name = Lex.getCurStrVal();
 713     if (Lex.Lex() != tgtok::less)  // consume the Id.
 714       return ParseIDValue(CurRec, Name, NameLoc);    // Value ::= IDValue
 715
 716     // Value ::= ID '<' ValueListNE '>'
 717     if (Lex.Lex() == tgtok::greater) {
 718       TokError("expected non-empty value list");
 719       return 0;
 720     }
 721     std::vector<Init*> ValueList = ParseValueList(CurRec);
 722     if (ValueList.empty()) return 0;
 723
 724     if (Lex.getCode() != tgtok::greater) {
 725       TokError("expected '>' at end of value list");
 726       return 0;
 727     }
 728     Lex.Lex();  // eat the '>'
 729
 730     // This is a CLASS<initvalslist> expression.  This is supposed to synthesize
 731     // a new anonymous definition, deriving from CLASS<initvalslist> with no
 732     // body.
 733     Record *Class = Records.getClass(Name);
 734     if (!Class) {
 735       Error(NameLoc, "Expected a class name, got '" + Name + "'");
 736       return 0;
 737     }
 738
 739     // Create the new record, set it as CurRec temporarily.
 740     static unsigned AnonCounter = 0;
 741     Record *NewRec = new Record("anonymous.val."+utostr(AnonCounter++),NameLoc);
 742     SubClassReference SCRef;
 743     SCRef.RefLoc = NameLoc;
 744     SCRef.Rec = Class;
 745     SCRef.TemplateArgs = ValueList;
 746     // Add info about the subclass to NewRec.
 747     if (AddSubClass(NewRec, SCRef))
 748       return 0;
 749     NewRec->resolveReferences();
 750     Records.addDef(NewRec);
 751
 752     // The result of the expression is a reference to the new record.
 753     return new DefInit(NewRec);
 754   }
 755   case tgtok::l_brace: {           // Value ::= '{' ValueList '}'
 756     TGLoc BraceLoc = Lex.getLoc();
 757     Lex.Lex(); // eat the '{'
 758     std::vector<Init*> Vals;
 759
 760     if (Lex.getCode() != tgtok::r_brace) {
 761       Vals = ParseValueList(CurRec);
 762       if (Vals.empty()) return 0;
 763     }
 764     if (Lex.getCode() != tgtok::r_brace) {
 765       TokError("expected '}' at end of bit list value");
 766       return 0;
 767     }
 768     Lex.Lex();  // eat the '}'
 769
 770     BitsInit *Result = new BitsInit(Vals.size());
 771     for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
 772       Init *Bit = Vals[i]->convertInitializerTo(new BitRecTy());
 773       if (Bit == 0) {
 774         Error(BraceLoc, "Element #" + utostr(i) + " (" + Vals[i]->getAsString()+
 775               ") is not convertable to a bit");
 776         return 0;
 777       }
 778       Result->setBit(Vals.size()-i-1, Bit);
 779     }
 780     return Result;
 781   }
 782   case tgtok::l_square: {          // Value ::= '[' ValueList ']'
 783     Lex.Lex(); // eat the '['
 784     std::vector<Init*> Vals;
 785
 786     if (Lex.getCode() != tgtok::r_square) {
 787       Vals = ParseValueList(CurRec);
 788       if (Vals.empty()) return 0;
 789     }
 790     if (Lex.getCode() != tgtok::r_square) {
 791       TokError("expected ']' at end of list value");
 792       return 0;
 793     }
 794     Lex.Lex();  // eat the ']'
 795     return new ListInit(Vals);
 796   }
 797   case tgtok::l_paren: {         // Value ::= '(' IDValue DagArgList ')'
 798     Lex.Lex();   // eat the '('
 799     if (Lex.getCode() != tgtok::Id
 800         && Lex.getCode() != tgtok::XNameConcat) {
 801       TokError("expected identifier in dag init");
 802       return 0;
 803     }
 804
 805     Init *Operator = 0;
 806     if (Lex.getCode() == tgtok::Id) {
 807       Operator = ParseIDValue(CurRec);
 808       if (Operator == 0) return 0;
 809     }
 810     else {
 811       BinOpInit::BinaryOp Code = BinOpInit::NAMECONCAT;
 812
 813       Lex.Lex();  // eat the operation
 814
 815       if (Lex.getCode() != tgtok::less) {
 816         TokError("expected type name for nameconcat");
 817         return 0;
 818       }
 819       Lex.Lex();  // eat the <
 820
 821       RecTy *Type = ParseType();
 822
 823       if (Type == 0) {
 824         TokError("expected type name for nameconcat");
 825         return 0;
 826       }
 827
 828       if (Lex.getCode() != tgtok::greater) {
 829         TokError("expected type name for nameconcat");
 830         return 0;
 831       }
 832       Lex.Lex();  // eat the >
 833
 834       if (Lex.getCode() != tgtok::l_paren) {
 835         TokError("expected '(' after binary operator");
 836         return 0;
 837       }
 838       Lex.Lex();  // eat the '('
 839
 840       Init *LHS = ParseValue(CurRec);
 841       if (LHS == 0) return 0;
 842
 843       if (Lex.getCode() != tgtok::comma) {
 844         TokError("expected ',' in binary operator");
 845         return 0;
 846       }
 847       Lex.Lex();  // eat the ','
 848
 849       Init *RHS = ParseValue(CurRec);
 850        if (RHS == 0) return 0;
 851
 852        if (Lex.getCode() != tgtok::r_paren) {
 853          TokError("expected ')' in binary operator");
 854          return 0;
 855        }
 856        Lex.Lex();  // eat the ')'
 857        Operator = (new BinOpInit(Code, LHS, RHS, Type))->Fold(CurRec, CurMultiClass);
 858     }
 859
 860     // If the operator name is present, parse it.
 861     std::string OperatorName;
 862     if (Lex.getCode() == tgtok::colon) {
 863       if (Lex.Lex() != tgtok::VarName) { // eat the ':'
 864         TokError("expected variable name in dag operator");
 865         return 0;
 866       }
 867       OperatorName = Lex.getCurStrVal();
 868       Lex.Lex();  // eat the VarName.
 869     }
 870
 871     std::vector<std::pair<llvm::Init*, std::string> > DagArgs;
 872     if (Lex.getCode() != tgtok::r_paren) {
 873       DagArgs = ParseDagArgList(CurRec);
 874       if (DagArgs.empty()) return 0;
 875     }
 876
 877     if (Lex.getCode() != tgtok::r_paren) {
 878       TokError("expected ')' in dag init");
 879       return 0;
 880     }
 881     Lex.Lex();  // eat the ')'
 882
 883     return new DagInit(Operator, OperatorName, DagArgs);
 884   }
 885   case tgtok::XConcat:
 886   case tgtok::XSRA:
 887   case tgtok::XSRL:
 888   case tgtok::XSHL:
 889   case tgtok::XStrConcat:
 890   case tgtok::XNameConcat: {  // Value ::= !binop '(' Value ',' Value ')'
 891     BinOpInit::BinaryOp Code;
 892     RecTy *Type = 0;
 893
 894
 895     switch (Lex.getCode()) {
 896     default: assert(0 && "Unhandled code!");
 897     case tgtok::XConcat:
 898       Lex.Lex();  // eat the operation
 899       Code = BinOpInit::CONCAT;
 900       Type = new DagRecTy();
 901       break;
 902     case tgtok::XSRA:
 903       Lex.Lex();  // eat the operation
 904       Code = BinOpInit::SRA;
 905       Type = new IntRecTy();
 906       break;
 907     case tgtok::XSRL:
 908       Lex.Lex();  // eat the operation
 909       Code = BinOpInit::SRL;
 910       Type = new IntRecTy();
 911       break;
 912     case tgtok::XSHL:
 913       Lex.Lex();  // eat the operation
 914       Code = BinOpInit::SHL;
 915       Type = new IntRecTy();
 916       break;
 917     case tgtok::XStrConcat:
 918       Lex.Lex();  // eat the operation
 919       Code = BinOpInit::STRCONCAT;
 920       Type = new StringRecTy();
 921       break;
 922     case tgtok::XNameConcat:
 923       Lex.Lex();  // eat the operation
 924       Code = BinOpInit::NAMECONCAT;
 925       if (Lex.getCode() != tgtok::less) {
 926         TokError("expected type name for nameconcat");
 927         return 0;
 928       }
 929       Lex.Lex();  // eat the <
 930
 931       Type = ParseType();
 932
 933       if (Type == 0) {
 934         TokError("expected type name for nameconcat");
 935         return 0;
 936       }
 937
 938       if (Lex.getCode() != tgtok::greater) {
 939         TokError("expected type name for nameconcat");
 940         return 0;
 941       }
 942       Lex.Lex();  // eat the >
 943       break;
 944     }
 945     if (Lex.getCode() != tgtok::l_paren) {
 946       TokError("expected '(' after binary operator");
 947       return 0;
 948     }
 949     Lex.Lex();  // eat the '('
 950
 951     Init *LHS = ParseValue(CurRec);
 952     if (LHS == 0) return 0;
 953
 954     if (Lex.getCode() != tgtok::comma) {
 955       TokError("expected ',' in binary operator");
 956       return 0;
 957     }
 958     Lex.Lex();  // eat the ','
 959
 960     Init *RHS = ParseValue(CurRec);
 961     if (RHS == 0) return 0;
 962
 963     if (Lex.getCode() != tgtok::r_paren) {
 964       TokError("expected ')' in binary operator");
 965       return 0;
 966     }
 967     Lex.Lex();  // eat the ')'
 968     return (new BinOpInit(Code, LHS, RHS, Type))->Fold(CurRec, CurMultiClass);
 969   }
 970   }
 971
 972   return R;
 973 }
 974
 975 /// ParseValue - Parse a tblgen value.  This returns null on error.
 976 ///
 977 ///   Value       ::= SimpleValue ValueSuffix*
 978 ///   ValueSuffix ::= '{' BitList '}'
 979 ///   ValueSuffix ::= '[' BitList ']'
 980 ///   ValueSuffix ::= '.' ID
 981 ///
 982 Init *TGParser::ParseValue(Record *CurRec) {
 983   Init *Result = ParseSimpleValue(CurRec);
 984   if (Result == 0) return 0;
 985
 986   // Parse the suffixes now if present.
 987   while (1) {
 988     switch (Lex.getCode()) {
 989     default: return Result;
 990     case tgtok::l_brace: {
 991       TGLoc CurlyLoc = Lex.getLoc();
 992       Lex.Lex(); // eat the '{'
 993       std::vector<unsigned> Ranges = ParseRangeList();
 994       if (Ranges.empty()) return 0;
 995
 996       // Reverse the bitlist.
 997       std::reverse(Ranges.begin(), Ranges.end());
 998       Result = Result->convertInitializerBitRange(Ranges);
 999       if (Result == 0) {
1000         Error(CurlyLoc, "Invalid bit range for value");
1001         return 0;
1002       }
1003
1004       // Eat the '}'.
1005       if (Lex.getCode() != tgtok::r_brace) {
1006         TokError("expected '}' at end of bit range list");
1007         return 0;
1008       }
1009       Lex.Lex();
1010       break;
1011     }
1012     case tgtok::l_square: {
1013       TGLoc SquareLoc = Lex.getLoc();
1014       Lex.Lex(); // eat the '['
1015       std::vector<unsigned> Ranges = ParseRangeList();
1016       if (Ranges.empty()) return 0;
1017
1018       Result = Result->convertInitListSlice(Ranges);
1019       if (Result == 0) {
1020         Error(SquareLoc, "Invalid range for list slice");
1021         return 0;
1022       }
1023
1024       // Eat the ']'.
1025       if (Lex.getCode() != tgtok::r_square) {
1026         TokError("expected ']' at end of list slice");
1027         return 0;
1028       }
1029       Lex.Lex();
1030       break;
1031     }
1032     case tgtok::period:
1033       if (Lex.Lex() != tgtok::Id) {  // eat the .
1034         TokError("expected field identifier after '.'");
1035         return 0;
1036       }
1037       if (!Result->getFieldType(Lex.getCurStrVal())) {
1038         TokError("Cannot access field '" + Lex.getCurStrVal() + "' of value '" +
1039                  Result->getAsString() + "'");
1040         return 0;
1041       }
1042       Result = new FieldInit(Result, Lex.getCurStrVal());
1043       Lex.Lex();  // eat field name
1044       break;
1045     }
1046   }
1047 }
1048
1049 /// ParseDagArgList - Parse the argument list for a dag literal expression.
1050 ///
1051 ///    ParseDagArgList ::= Value (':' VARNAME)?
1052 ///    ParseDagArgList ::= ParseDagArgList ',' Value (':' VARNAME)?
1053 std::vector<std::pair<llvm::Init*, std::string> >
1054 TGParser::ParseDagArgList(Record *CurRec) {
1055   std::vector<std::pair<llvm::Init*, std::string> > Result;
1056
1057   while (1) {
1058     Init *Val = ParseValue(CurRec);
1059     if (Val == 0) return std::vector<std::pair<llvm::Init*, std::string> >();
1060
1061     // If the variable name is present, add it.
1062     std::string VarName;
1063     if (Lex.getCode() == tgtok::colon) {
1064       if (Lex.Lex() != tgtok::VarName) { // eat the ':'
1065         TokError("expected variable name in dag literal");
1066         return std::vector<std::pair<llvm::Init*, std::string> >();
1067       }
1068       VarName = Lex.getCurStrVal();
1069       Lex.Lex();  // eat the VarName.
1070     }
1071
1072     Result.push_back(std::make_pair(Val, VarName));
1073
1074     if (Lex.getCode() != tgtok::comma) break;
1075     Lex.Lex(); // eat the ','
1076   }
1077
1078   return Result;
1079 }
1080
1081
1082 /// ParseValueList - Parse a comma separated list of values, returning them as a
1083 /// vector.  Note that this always expects to be able to parse at least one
1084 /// value.  It returns an empty list if this is not possible.
1085 ///
1086 ///   ValueList ::= Value (',' Value)
1087 ///
1088 std::vector<Init*> TGParser::ParseValueList(Record *CurRec) {
1089   std::vector<Init*> Result;
1090   Result.push_back(ParseValue(CurRec));
1091   if (Result.back() == 0) return std::vector<Init*>();
1092
1093   while (Lex.getCode() == tgtok::comma) {
1094     Lex.Lex();  // Eat the comma
1095
1096     Result.push_back(ParseValue(CurRec));
1097     if (Result.back() == 0) return std::vector<Init*>();
1098   }
1099
1100   return Result;
1101 }
1102
1103
1104
1105 /// ParseDeclaration - Read a declaration, returning the name of field ID, or an
1106 /// empty string on error.  This can happen in a number of different context's,
1107 /// including within a def or in the template args for a def (which which case
1108 /// CurRec will be non-null) and within the template args for a multiclass (in
1109 /// which case CurRec will be null, but CurMultiClass will be set).  This can
1110 /// also happen within a def that is within a multiclass, which will set both
1111 /// CurRec and CurMultiClass.
1112 ///
1113 ///  Declaration ::= FIELD? Type ID ('=' Value)?
1114 ///
1115 std::string TGParser::ParseDeclaration(Record *CurRec,
1116                                        bool ParsingTemplateArgs) {
1117   // Read the field prefix if present.
1118   bool HasField = Lex.getCode() == tgtok::Field;
1119   if (HasField) Lex.Lex();
1120
1121   RecTy *Type = ParseType();
1122   if (Type == 0) return "";
1123
1124   if (Lex.getCode() != tgtok::Id) {
1125     TokError("Expected identifier in declaration");
1126     return "";
1127   }
1128
1129   TGLoc IdLoc = Lex.getLoc();
1130   std::string DeclName = Lex.getCurStrVal();
1131   Lex.Lex();
1132
1133   if (ParsingTemplateArgs) {
1134     if (CurRec) {
1135       DeclName = CurRec->getName() + ":" + DeclName;
1136     } else {
1137       assert(CurMultiClass);
1138     }
1139     if (CurMultiClass)
1140       DeclName = CurMultiClass->Rec.getName() + "::" + DeclName;
1141   }
1142
1143   // Add the value.
1144   if (AddValue(CurRec, IdLoc, RecordVal(DeclName, Type, HasField)))
1145     return "";
1146
1147   // If a value is present, parse it.
1148   if (Lex.getCode() == tgtok::equal) {
1149     Lex.Lex();
1150     TGLoc ValLoc = Lex.getLoc();
1151     Init *Val = ParseValue(CurRec);
1152     if (Val == 0 ||
1153         SetValue(CurRec, ValLoc, DeclName, std::vector<unsigned>(), Val))
1154       return "";
1155   }
1156
1157   return DeclName;
1158 }
1159
1160 /// ParseTemplateArgList - Read a template argument list, which is a non-empty
1161 /// sequence of template-declarations in <>'s.  If CurRec is non-null, these are
1162 /// template args for a def, which may or may not be in a multiclass.  If null,
1163 /// these are the template args for a multiclass.
1164 ///
1165 ///    TemplateArgList ::= '<' Declaration (',' Declaration)* '>'
1166 ///
1167 bool TGParser::ParseTemplateArgList(Record *CurRec) {
1168   assert(Lex.getCode() == tgtok::less && "Not a template arg list!");
1169   Lex.Lex(); // eat the '<'
1170
1171   Record *TheRecToAddTo = CurRec ? CurRec : &CurMultiClass->Rec;
1172
1173   // Read the first declaration.
1174   std::string TemplArg = ParseDeclaration(CurRec, true/*templateargs*/);
1175   if (TemplArg.empty())
1176     return true;
1177
1178   TheRecToAddTo->addTemplateArg(TemplArg);
1179
1180   while (Lex.getCode() == tgtok::comma) {
1181     Lex.Lex(); // eat the ','
1182
1183     // Read the following declarations.
1184     TemplArg = ParseDeclaration(CurRec, true/*templateargs*/);
1185     if (TemplArg.empty())
1186       return true;
1187     TheRecToAddTo->addTemplateArg(TemplArg);
1188   }
1189
1190   if (Lex.getCode() != tgtok::greater)
1191     return TokError("expected '>' at end of template argument list");
1192   Lex.Lex(); // eat the '>'.
1193   return false;
1194 }
1195
1196
1197 /// ParseBodyItem - Parse a single item at within the body of a def or class.
1198 ///
1199 ///   BodyItem ::= Declaration ';'
1200 ///   BodyItem ::= LET ID OptionalBitList '=' Value ';'
1201 bool TGParser::ParseBodyItem(Record *CurRec) {
1202   if (Lex.getCode() != tgtok::Let) {
1203     if (ParseDeclaration(CurRec, false).empty())
1204       return true;
1205
1206     if (Lex.getCode() != tgtok::semi)
1207       return TokError("expected ';' after declaration");
1208     Lex.Lex();
1209     return false;
1210   }
1211
1212   // LET ID OptionalRangeList '=' Value ';'
1213   if (Lex.Lex() != tgtok::Id)
1214     return TokError("expected field identifier after let");
1215
1216   TGLoc IdLoc = Lex.getLoc();
1217   std::string FieldName = Lex.getCurStrVal();
1218   Lex.Lex();  // eat the field name.
1219
1220   std::vector<unsigned> BitList;
1221   if (ParseOptionalBitList(BitList))
1222     return true;
1223   std::reverse(BitList.begin(), BitList.end());
1224
1225   if (Lex.getCode() != tgtok::equal)
1226     return TokError("expected '=' in let expression");
1227   Lex.Lex();  // eat the '='.
1228
1229   Init *Val = ParseValue(CurRec);
1230   if (Val == 0) return true;
1231
1232   if (Lex.getCode() != tgtok::semi)
1233     return TokError("expected ';' after let expression");
1234   Lex.Lex();
1235
1236   return SetValue(CurRec, IdLoc, FieldName, BitList, Val);
1237 }
1238
1239 /// ParseBody - Read the body of a class or def.  Return true on error, false on
1240 /// success.
1241 ///
1242 ///   Body     ::= ';'
1243 ///   Body     ::= '{' BodyList '}'
1244 ///   BodyList BodyItem*
1245 ///
1246 bool TGParser::ParseBody(Record *CurRec) {
1247   // If this is a null definition, just eat the semi and return.
1248   if (Lex.getCode() == tgtok::semi) {
1249     Lex.Lex();
1250     return false;
1251   }
1252
1253   if (Lex.getCode() != tgtok::l_brace)
1254     return TokError("Expected ';' or '{' to start body");
1255   // Eat the '{'.
1256   Lex.Lex();
1257
1258   while (Lex.getCode() != tgtok::r_brace)
1259     if (ParseBodyItem(CurRec))
1260       return true;
1261
1262   // Eat the '}'.
1263   Lex.Lex();
1264   return false;
1265 }
1266
1267 /// ParseObjectBody - Parse the body of a def or class.  This consists of an
1268 /// optional ClassList followed by a Body.  CurRec is the current def or class
1269 /// that is being parsed.
1270 ///
1271 ///   ObjectBody      ::= BaseClassList Body
1272 ///   BaseClassList   ::= /*empty*/
1273 ///   BaseClassList   ::= ':' BaseClassListNE
1274 ///   BaseClassListNE ::= SubClassRef (',' SubClassRef)*
1275 ///
1276 bool TGParser::ParseObjectBody(Record *CurRec) {
1277   // If there is a baseclass list, read it.
1278   if (Lex.getCode() == tgtok::colon) {
1279     Lex.Lex();
1280
1281     // Read all of the subclasses.
1282     SubClassReference SubClass = ParseSubClassReference(CurRec, false);
1283     while (1) {
1284       // Check for error.
1285       if (SubClass.Rec == 0) return true;
1286
1287       // Add it.
1288       if (AddSubClass(CurRec, SubClass))
1289         return true;
1290
1291       if (Lex.getCode() != tgtok::comma) break;
1292       Lex.Lex(); // eat ','.
1293       SubClass = ParseSubClassReference(CurRec, false);
1294     }
1295   }
1296
1297   // Process any variables on the let stack.
1298   for (unsigned i = 0, e = LetStack.size(); i != e; ++i)
1299     for (unsigned j = 0, e = LetStack[i].size(); j != e; ++j)
1300       if (SetValue(CurRec, LetStack[i][j].Loc, LetStack[i][j].Name,
1301                    LetStack[i][j].Bits, LetStack[i][j].Value))
1302         return true;
1303
1304   return ParseBody(CurRec);
1305 }
1306
1307
1308 /// ParseDef - Parse and return a top level or multiclass def, return the record
1309 /// corresponding to it.  This returns null on error.
1310 ///
1311 ///   DefInst ::= DEF ObjectName ObjectBody
1312 ///
1313 llvm::Record *TGParser::ParseDef(MultiClass *CurMultiClass) {
1314   TGLoc DefLoc = Lex.getLoc();
1315   assert(Lex.getCode() == tgtok::Def && "Unknown tok");
1316   Lex.Lex();  // Eat the 'def' token.
1317
1318   // Parse ObjectName and make a record for it.
1319   Record *CurRec = new Record(ParseObjectName(), DefLoc);
1320
1321   if (!CurMultiClass) {
1322     // Top-level def definition.
1323
1324     // Ensure redefinition doesn't happen.
1325     if (Records.getDef(CurRec->getName())) {
1326       Error(DefLoc, "def '" + CurRec->getName() + "' already defined");
1327       return 0;
1328     }
1329     Records.addDef(CurRec);
1330   } else {
1331     // Otherwise, a def inside a multiclass, add it to the multiclass.
1332     for (unsigned i = 0, e = CurMultiClass->DefPrototypes.size(); i != e; ++i)
1333       if (CurMultiClass->DefPrototypes[i]->getName() == CurRec->getName()) {
1334         Error(DefLoc, "def '" + CurRec->getName() +
1335               "' already defined in this multiclass!");
1336         return 0;
1337       }
1338     CurMultiClass->DefPrototypes.push_back(CurRec);
1339   }
1340
1341   if (ParseObjectBody(CurRec))
1342     return 0;
1343
1344   if (CurMultiClass == 0)  // Def's in multiclasses aren't really defs.
1345     CurRec->resolveReferences();
1346
1347   // If ObjectBody has template arguments, it's an error.
1348   assert(CurRec->getTemplateArgs().empty() && "How'd this get template args?");
1349   return CurRec;
1350 }
1351
1352
1353 /// ParseClass - Parse a tblgen class definition.
1354 ///
1355 ///   ClassInst ::= CLASS ID TemplateArgList? ObjectBody
1356 ///
1357 bool TGParser::ParseClass() {
1358   assert(Lex.getCode() == tgtok::Class && "Unexpected token!");
1359   Lex.Lex();
1360
1361   if (Lex.getCode() != tgtok::Id)
1362     return TokError("expected class name after 'class' keyword");
1363
1364   Record *CurRec = Records.getClass(Lex.getCurStrVal());
1365   if (CurRec) {
1366     // If the body was previously defined, this is an error.
1367     if (!CurRec->getValues().empty() ||
1368         !CurRec->getSuperClasses().empty() ||
1369         !CurRec->getTemplateArgs().empty())
1370       return TokError("Class '" + CurRec->getName() + "' already defined");
1371   } else {
1372     // If this is the first reference to this class, create and add it.
1373     CurRec = new Record(Lex.getCurStrVal(), Lex.getLoc());
1374     Records.addClass(CurRec);
1375   }
1376   Lex.Lex(); // eat the name.
1377
1378   // If there are template args, parse them.
1379   if (Lex.getCode() == tgtok::less)
1380     if (ParseTemplateArgList(CurRec))
1381       return true;
1382
1383   // Finally, parse the object body.
1384   return ParseObjectBody(CurRec);
1385 }
1386
1387 /// ParseLetList - Parse a non-empty list of assignment expressions into a list
1388 /// of LetRecords.
1389 ///
1390 ///   LetList ::= LetItem (',' LetItem)*
1391 ///   LetItem ::= ID OptionalRangeList '=' Value
1392 ///
1393 std::vector<LetRecord> TGParser::ParseLetList() {
1394   std::vector<LetRecord> Result;
1395
1396   while (1) {
1397     if (Lex.getCode() != tgtok::Id) {
1398       TokError("expected identifier in let definition");
1399       return std::vector<LetRecord>();
1400     }
1401     std::string Name = Lex.getCurStrVal();
1402     TGLoc NameLoc = Lex.getLoc();
1403     Lex.Lex();  // Eat the identifier.
1404
1405     // Check for an optional RangeList.
1406     std::vector<unsigned> Bits;
1407     if (ParseOptionalRangeList(Bits))
1408       return std::vector<LetRecord>();
1409     std::reverse(Bits.begin(), Bits.end());
1410
1411     if (Lex.getCode() != tgtok::equal) {
1412       TokError("expected '=' in let expression");
1413       return std::vector<LetRecord>();
1414     }
1415     Lex.Lex();  // eat the '='.
1416
1417     Init *Val = ParseValue(0);
1418     if (Val == 0) return std::vector<LetRecord>();
1419
1420     // Now that we have everything, add the record.
1421     Result.push_back(LetRecord(Name, Bits, Val, NameLoc));
1422
1423     if (Lex.getCode() != tgtok::comma)
1424       return Result;
1425     Lex.Lex();  // eat the comma.
1426   }
1427 }
1428
1429 /// ParseTopLevelLet - Parse a 'let' at top level.  This can be a couple of
1430 /// different related productions.
1431 ///
1432 ///   Object ::= LET LetList IN '{' ObjectList '}'
1433 ///   Object ::= LET LetList IN Object
1434 ///
1435 bool TGParser::ParseTopLevelLet() {
1436   assert(Lex.getCode() == tgtok::Let && "Unexpected token");
1437   Lex.Lex();
1438
1439   // Add this entry to the let stack.
1440   std::vector<LetRecord> LetInfo = ParseLetList();
1441   if (LetInfo.empty()) return true;
1442   LetStack.push_back(LetInfo);
1443
1444   if (Lex.getCode() != tgtok::In)
1445     return TokError("expected 'in' at end of top-level 'let'");
1446   Lex.Lex();
1447
1448   // If this is a scalar let, just handle it now
1449   if (Lex.getCode() != tgtok::l_brace) {
1450     // LET LetList IN Object
1451     if (ParseObject())
1452       return true;
1453   } else {   // Object ::= LETCommand '{' ObjectList '}'
1454     TGLoc BraceLoc = Lex.getLoc();
1455     // Otherwise, this is a group let.
1456     Lex.Lex();  // eat the '{'.
1457
1458     // Parse the object list.
1459     if (ParseObjectList())
1460       return true;
1461
1462     if (Lex.getCode() != tgtok::r_brace) {
1463       TokError("expected '}' at end of top level let command");
1464       return Error(BraceLoc, "to match this '{'");
1465     }
1466     Lex.Lex();
1467   }
1468
1469   // Outside this let scope, this let block is not active.
1470   LetStack.pop_back();
1471   return false;
1472 }
1473
1474 /// ParseMultiClassDef - Parse a def in a multiclass context.
1475 ///
1476 ///  MultiClassDef ::= DefInst
1477 ///
1478 bool TGParser::ParseMultiClassDef(MultiClass *CurMC) {
1479   if (Lex.getCode() != tgtok::Def)
1480     return TokError("expected 'def' in multiclass body");
1481
1482   Record *D = ParseDef(CurMC);
1483   if (D == 0) return true;
1484
1485   // Copy the template arguments for the multiclass into the def.
1486   const std::vector<std::string> &TArgs = CurMC->Rec.getTemplateArgs();
1487
1488   for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
1489     const RecordVal *RV = CurMC->Rec.getValue(TArgs[i]);
1490     assert(RV && "Template arg doesn't exist?");
1491     D->addValue(*RV);
1492   }
1493
1494   return false;
1495 }
1496
1497 /// ParseMultiClass - Parse a multiclass definition.
1498 ///
1499 ///  MultiClassInst ::= MULTICLASS ID TemplateArgList? ':' BaseMultiClassList '{' MultiClassDef+ '}'
1500 ///
1501 bool TGParser::ParseMultiClass() {
1502   assert(Lex.getCode() == tgtok::MultiClass && "Unexpected token");
1503   Lex.Lex();  // Eat the multiclass token.
1504
1505   if (Lex.getCode() != tgtok::Id)
1506     return TokError("expected identifier after multiclass for name");
1507   std::string Name = Lex.getCurStrVal();
1508
1509   if (MultiClasses.count(Name))
1510     return TokError("multiclass '" + Name + "' already defined");
1511
1512   CurMultiClass = MultiClasses[Name] = new MultiClass(Name, Lex.getLoc());
1513   Lex.Lex();  // Eat the identifier.
1514
1515   // If there are template args, parse them.
1516   if (Lex.getCode() == tgtok::less)
1517     if (ParseTemplateArgList(0))
1518       return true;
1519
1520   bool inherits = false;
1521
1522   // If there are submulticlasses, parse them.
1523   if (Lex.getCode() == tgtok::colon) {
1524     inherits = true;
1525
1526     Lex.Lex();
1527
1528     // Read all of the submulticlasses.
1529     SubMultiClassReference SubMultiClass = ParseSubMultiClassReference(CurMultiClass);
1530     while (1) {
1531       // Check for error.
1532       if (SubMultiClass.MC == 0) return true;
1533
1534       // Add it.
1535       if (AddSubMultiClass(CurMultiClass, SubMultiClass))
1536         return true;
1537
1538       if (Lex.getCode() != tgtok::comma) break;
1539       Lex.Lex(); // eat ','.
1540       SubMultiClass = ParseSubMultiClassReference(CurMultiClass);
1541     }
1542   }
1543
1544   if (Lex.getCode() != tgtok::l_brace) {
1545     if (!inherits)
1546       return TokError("expected '{' in multiclass definition");
1547     else
1548       if (Lex.getCode() != tgtok::semi)
1549         return TokError("expected ';' in multiclass definition");
1550       else
1551         Lex.Lex();  // eat the ';'.
1552   }
1553   else {
1554     if (Lex.Lex() == tgtok::r_brace)  // eat the '{'.
1555       return TokError("multiclass must contain at least one def");
1556
1557     while (Lex.getCode() != tgtok::r_brace)
1558       if (ParseMultiClassDef(CurMultiClass))
1559         return true;
1560
1561     Lex.Lex();  // eat the '}'.
1562   }
1563
1564   CurMultiClass = 0;
1565   return false;
1566 }
1567
1568 /// ParseDefm - Parse the instantiation of a multiclass.
1569 ///
1570 ///   DefMInst ::= DEFM ID ':' DefmSubClassRef ';'
1571 ///
1572 bool TGParser::ParseDefm() {
1573   assert(Lex.getCode() == tgtok::Defm && "Unexpected token!");
1574   if (Lex.Lex() != tgtok::Id)  // eat the defm.
1575     return TokError("expected identifier after defm");
1576
1577   TGLoc DefmPrefixLoc = Lex.getLoc();
1578   std::string DefmPrefix = Lex.getCurStrVal();
1579   if (Lex.Lex() != tgtok::colon)
1580     return TokError("expected ':' after defm identifier");
1581
1582   // eat the colon.
1583   Lex.Lex();
1584
1585   TGLoc SubClassLoc = Lex.getLoc();
1586   SubClassReference Ref = ParseSubClassReference(0, true);
1587
1588   while (1) {
1589     if (Ref.Rec == 0) return true;
1590
1591     // To instantiate a multiclass, we need to first get the multiclass, then
1592     // instantiate each def contained in the multiclass with the SubClassRef
1593     // template parameters.
1594     MultiClass *MC = MultiClasses[Ref.Rec->getName()];
1595     assert(MC && "Didn't lookup multiclass correctly?");
1596     std::vector<Init*> &TemplateVals = Ref.TemplateArgs;
1597
1598     // Verify that the correct number of template arguments were specified.
1599     const std::vector<std::string> &TArgs = MC->Rec.getTemplateArgs();
1600     if (TArgs.size() < TemplateVals.size())
1601       return Error(SubClassLoc,
1602                    "more template args specified than multiclass expects");
1603
1604     // Loop over all the def's in the multiclass, instantiating each one.
1605     for (unsigned i = 0, e = MC->DefPrototypes.size(); i != e; ++i) {
1606       Record *DefProto = MC->DefPrototypes[i];
1607
1608       // Add the suffix to the defm name to get the new name.
1609       Record *CurRec = new Record(DefmPrefix + DefProto->getName(), DefmPrefixLoc);
1610
1611       SubClassReference Ref;
1612       Ref.RefLoc = DefmPrefixLoc;
1613       Ref.Rec = DefProto;
1614       AddSubClass(CurRec, Ref);
1615
1616       // Loop over all of the template arguments, setting them to the specified
1617       // value or leaving them as the default if necessary.
1618       for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
1619         if (i < TemplateVals.size()) { // A value is specified for this temp-arg?
1620           // Set it now.
1621           if (SetValue(CurRec, DefmPrefixLoc, TArgs[i], std::vector<unsigned>(),
1622                        TemplateVals[i]))
1623             return true;
1624
1625           // Resolve it next.
1626           CurRec->resolveReferencesTo(CurRec->getValue(TArgs[i]));
1627
1628           // Now remove it.
1629           CurRec->removeValue(TArgs[i]);
1630
1631         } else if (!CurRec->getValue(TArgs[i])->getValue()->isComplete()) {
1632           return Error(SubClassLoc, "value not specified for template argument #"+
1633                        utostr(i) + " (" + TArgs[i] + ") of multiclassclass '" +
1634                        MC->Rec.getName() + "'");
1635         }
1636       }
1637
1638       // If the mdef is inside a 'let' expression, add to each def.
1639       for (unsigned i = 0, e = LetStack.size(); i != e; ++i)
1640         for (unsigned j = 0, e = LetStack[i].size(); j != e; ++j)
1641           if (SetValue(CurRec, LetStack[i][j].Loc, LetStack[i][j].Name,
1642                        LetStack[i][j].Bits, LetStack[i][j].Value)) {
1643             Error(DefmPrefixLoc, "when instantiating this defm");
1644             return true;
1645           }
1646
1647       // Ensure redefinition doesn't happen.
1648       if (Records.getDef(CurRec->getName()))
1649         return Error(DefmPrefixLoc, "def '" + CurRec->getName() +
1650                      "' already defined, instantiating defm with subdef '" +
1651                      DefProto->getName() + "'");
1652       Records.addDef(CurRec);
1653       CurRec->resolveReferences();
1654     }
1655
1656     if (Lex.getCode() != tgtok::comma) break;
1657     Lex.Lex(); // eat ','.
1658
1659     SubClassLoc = Lex.getLoc();
1660     Ref = ParseSubClassReference(0, true);
1661   }
1662
1663   if (Lex.getCode() != tgtok::semi)
1664     return TokError("expected ';' at end of defm");
1665   Lex.Lex();
1666
1667   return false;
1668 }
1669
1670 /// ParseObject
1671 ///   Object ::= ClassInst
1672 ///   Object ::= DefInst
1673 ///   Object ::= MultiClassInst
1674 ///   Object ::= DefMInst
1675 ///   Object ::= LETCommand '{' ObjectList '}'
1676 ///   Object ::= LETCommand Object
1677 bool TGParser::ParseObject() {
1678   switch (Lex.getCode()) {
1679   default: assert(0 && "This is not an object");
1680   case tgtok::Let:   return ParseTopLevelLet();
1681   case tgtok::Def:   return ParseDef(0) == 0;
1682   case tgtok::Defm:  return ParseDefm();
1683   case tgtok::Class: return ParseClass();
1684   case tgtok::MultiClass: return ParseMultiClass();
1685   }
1686 }
1687
1688 /// ParseObjectList
1689 ///   ObjectList :== Object*
1690 bool TGParser::ParseObjectList() {
1691   while (isObjectStart(Lex.getCode())) {
1692     if (ParseObject())
1693       return true;
1694   }
1695   return false;
1696 }
1697
1698
1699 bool TGParser::ParseFile() {
1700   Lex.Lex(); // Prime the lexer.
1701   if (ParseObjectList()) return true;
1702
1703   // If we have unread input at the end of the file, report it.
1704   if (Lex.getCode() == tgtok::Eof)
1705     return false;
1706
1707   return TokError("Unexpected input at top level");
1708 }
1709