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 "TGParser.h"
  15 #include "Record.h"
  16 #include "llvm/ADT/StringExtras.h"
  17 #include <algorithm>
  18 #include <sstream>
  19 #include "llvm/ADT/SmallVector.h"
  20 #include "llvm/Support/CommandLine.h"
  21 using namespace llvm;
  22
  23 /// LLVMCHack - This is a temporary hack that changes how "(foo [1, 2, 3])"
  24 /// parses.
  25 /// FIXME: REMOVE THIS.
  26 static cl::opt<bool> LLVMCHack("llvmc-temp-hack", cl::ReallyHidden);
  27
  28 //===----------------------------------------------------------------------===//
  29 // Support Code for the Semantic Actions.
  30 //===----------------------------------------------------------------------===//
  31
  32 namespace llvm {
  33 struct SubClassReference {
  34   SMLoc RefLoc;
  35   Record *Rec;
  36   std::vector<Init*> TemplateArgs;
  37   SubClassReference() : Rec(0) {}
  38
  39   bool isInvalid() const { return Rec == 0; }
  40 };
  41
  42 struct SubMultiClassReference {
  43   SMLoc RefLoc;
  44   MultiClass *MC;
  45   std::vector<Init*> TemplateArgs;
  46   SubMultiClassReference() : MC(0) {}
  47
  48   bool isInvalid() const { return MC == 0; }
  49   void dump() const;
  50 };
  51
  52 void SubMultiClassReference::dump() const {
  53   errs() << "Multiclass:\n";
  54
  55   MC->dump();
  56
  57   errs() << "Template args:\n";
  58   for (std::vector<Init *>::const_iterator i = TemplateArgs.begin(),
  59          iend = TemplateArgs.end();
  60        i != iend;
  61        ++i) {
  62     (*i)->dump();
  63   }
  64 }
  65
  66 } // end namespace llvm
  67
  68 bool TGParser::AddValue(Record *CurRec, SMLoc Loc, const RecordVal &RV) {
  69   if (CurRec == 0)
  70     CurRec = &CurMultiClass->Rec;
  71
  72   if (RecordVal *ERV = CurRec->getValue(RV.getName())) {
  73     // The value already exists in the class, treat this as a set.
  74     if (ERV->setValue(RV.getValue()))
  75       return Error(Loc, "New definition of '" + RV.getName() + "' of type '" +
  76                    RV.getType()->getAsString() + "' is incompatible with " +
  77                    "previous definition of type '" +
  78                    ERV->getType()->getAsString() + "'");
  79   } else {
  80     CurRec->addValue(RV);
  81   }
  82   return false;
  83 }
  84
  85 /// SetValue -
  86 /// Return true on error, false on success.
  87 bool TGParser::SetValue(Record *CurRec, SMLoc Loc, const std::string &ValName,
  88                         const std::vector<unsigned> &BitList, Init *V) {
  89   if (!V) return false;
  90
  91   if (CurRec == 0) CurRec = &CurMultiClass->Rec;
  92
  93   RecordVal *RV = CurRec->getValue(ValName);
  94   if (RV == 0)
  95     return Error(Loc, "Value '" + ValName + "' unknown!");
  96
  97   // Do not allow assignments like 'X = X'.  This will just cause infinite loops
  98   // in the resolution machinery.
  99   if (BitList.empty())
 100     if (VarInit *VI = dynamic_cast<VarInit*>(V))
 101       if (VI->getName() == ValName)
 102         return false;
 103
 104   // If we are assigning to a subset of the bits in the value... then we must be
 105   // assigning to a field of BitsRecTy, which must have a BitsInit
 106   // initializer.
 107   //
 108   if (!BitList.empty()) {
 109     BitsInit *CurVal = dynamic_cast<BitsInit*>(RV->getValue());
 110     if (CurVal == 0)
 111       return Error(Loc, "Value '" + ValName + "' is not a bits type");
 112
 113     // Convert the incoming value to a bits type of the appropriate size...
 114     Init *BI = V->convertInitializerTo(new BitsRecTy(BitList.size()));
 115     if (BI == 0) {
 116       V->convertInitializerTo(new BitsRecTy(BitList.size()));
 117       return Error(Loc, "Initializer is not compatible with bit range");
 118     }
 119
 120     // We should have a BitsInit type now.
 121     BitsInit *BInit = dynamic_cast<BitsInit*>(BI);
 122     assert(BInit != 0);
 123
 124     BitsInit *NewVal = new BitsInit(CurVal->getNumBits());
 125
 126     // Loop over bits, assigning values as appropriate.
 127     for (unsigned i = 0, e = BitList.size(); i != e; ++i) {
 128       unsigned Bit = BitList[i];
 129       if (NewVal->getBit(Bit))
 130         return Error(Loc, "Cannot set bit #" + utostr(Bit) + " of value '" +
 131                      ValName + "' more than once");
 132       NewVal->setBit(Bit, BInit->getBit(i));
 133     }
 134
 135     for (unsigned i = 0, e = CurVal->getNumBits(); i != e; ++i)
 136       if (NewVal->getBit(i) == 0)
 137         NewVal->setBit(i, CurVal->getBit(i));
 138
 139     V = NewVal;
 140   }
 141
 142   if (RV->setValue(V))
 143    return Error(Loc, "Value '" + ValName + "' of type '" +
 144                 RV->getType()->getAsString() +
 145                 "' is incompatible with initializer '" + V->getAsString() +"'");
 146   return false;
 147 }
 148
 149 /// AddSubClass - Add SubClass as a subclass to CurRec, resolving its template
 150 /// args as SubClass's template arguments.
 151 bool TGParser::AddSubClass(Record *CurRec, SubClassReference &SubClass) {
 152   Record *SC = SubClass.Rec;
 153   // Add all of the values in the subclass into the current class.
 154   const std::vector<RecordVal> &Vals = SC->getValues();
 155   for (unsigned i = 0, e = Vals.size(); i != e; ++i)
 156     if (AddValue(CurRec, SubClass.RefLoc, Vals[i]))
 157       return true;
 158
 159   const std::vector<std::string> &TArgs = SC->getTemplateArgs();
 160
 161   // Ensure that an appropriate number of template arguments are specified.
 162   if (TArgs.size() < SubClass.TemplateArgs.size())
 163     return Error(SubClass.RefLoc, "More template args specified than expected");
 164
 165   // Loop over all of the template arguments, setting them to the specified
 166   // value or leaving them as the default if necessary.
 167   for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
 168     if (i < SubClass.TemplateArgs.size()) {
 169       // If a value is specified for this template arg, set it now.
 170       if (SetValue(CurRec, SubClass.RefLoc, TArgs[i], std::vector<unsigned>(),
 171                    SubClass.TemplateArgs[i]))
 172         return true;
 173
 174       // Resolve it next.
 175       CurRec->resolveReferencesTo(CurRec->getValue(TArgs[i]));
 176
 177       // Now remove it.
 178       CurRec->removeValue(TArgs[i]);
 179
 180     } else if (!CurRec->getValue(TArgs[i])->getValue()->isComplete()) {
 181       return Error(SubClass.RefLoc,"Value not specified for template argument #"
 182                    + utostr(i) + " (" + TArgs[i] + ") of subclass '" +
 183                    SC->getName() + "'!");
 184     }
 185   }
 186
 187   // Since everything went well, we can now set the "superclass" list for the
 188   // current record.
 189   const std::vector<Record*> &SCs = SC->getSuperClasses();
 190   for (unsigned i = 0, e = SCs.size(); i != e; ++i) {
 191     if (CurRec->isSubClassOf(SCs[i]))
 192       return Error(SubClass.RefLoc,
 193                    "Already subclass of '" + SCs[i]->getName() + "'!\n");
 194     CurRec->addSuperClass(SCs[i]);
 195   }
 196
 197   if (CurRec->isSubClassOf(SC))
 198     return Error(SubClass.RefLoc,
 199                  "Already subclass of '" + SC->getName() + "'!\n");
 200   CurRec->addSuperClass(SC);
 201   return false;
 202 }
 203
 204 /// AddSubMultiClass - Add SubMultiClass as a subclass to
 205 /// CurMC, resolving its template args as SubMultiClass's
 206 /// template arguments.
 207 bool TGParser::AddSubMultiClass(MultiClass *CurMC,
 208                                 SubMultiClassReference &SubMultiClass) {
 209   MultiClass *SMC = SubMultiClass.MC;
 210   Record *CurRec = &CurMC->Rec;
 211
 212   const std::vector<RecordVal> &MCVals = CurRec->getValues();
 213
 214   // Add all of the values in the subclass into the current class.
 215   const std::vector<RecordVal> &SMCVals = SMC->Rec.getValues();
 216   for (unsigned i = 0, e = SMCVals.size(); i != e; ++i)
 217     if (AddValue(CurRec, SubMultiClass.RefLoc, SMCVals[i]))
 218       return true;
 219
 220   int newDefStart = CurMC->DefPrototypes.size();
 221
 222   // Add all of the defs in the subclass into the current multiclass.
 223   for (MultiClass::RecordVector::const_iterator i = SMC->DefPrototypes.begin(),
 224          iend = SMC->DefPrototypes.end();
 225        i != iend;
 226        ++i) {
 227     // Clone the def and add it to the current multiclass
 228     Record *NewDef = new Record(**i);
 229
 230     // Add all of the values in the superclass into the current def.
 231     for (unsigned i = 0, e = MCVals.size(); i != e; ++i)
 232       if (AddValue(NewDef, SubMultiClass.RefLoc, MCVals[i]))
 233         return true;
 234
 235     CurMC->DefPrototypes.push_back(NewDef);
 236   }
 237
 238   const std::vector<std::string> &SMCTArgs = SMC->Rec.getTemplateArgs();
 239
 240   // Ensure that an appropriate number of template arguments are
 241   // specified.
 242   if (SMCTArgs.size() < SubMultiClass.TemplateArgs.size())
 243     return Error(SubMultiClass.RefLoc,
 244                  "More template args specified than expected");
 245
 246   // Loop over all of the template arguments, setting them to the specified
 247   // value or leaving them as the default if necessary.
 248   for (unsigned i = 0, e = SMCTArgs.size(); i != e; ++i) {
 249     if (i < SubMultiClass.TemplateArgs.size()) {
 250       // If a value is specified for this template arg, set it in the
 251       // superclass now.
 252       if (SetValue(CurRec, SubMultiClass.RefLoc, SMCTArgs[i],
 253                    std::vector<unsigned>(),
 254                    SubMultiClass.TemplateArgs[i]))
 255         return true;
 256
 257       // Resolve it next.
 258       CurRec->resolveReferencesTo(CurRec->getValue(SMCTArgs[i]));
 259
 260       // Now remove it.
 261       CurRec->removeValue(SMCTArgs[i]);
 262
 263       // If a value is specified for this template arg, set it in the
 264       // new defs now.
 265       for (MultiClass::RecordVector::iterator j =
 266              CurMC->DefPrototypes.begin() + newDefStart,
 267              jend = CurMC->DefPrototypes.end();
 268            j != jend;
 269            ++j) {
 270         Record *Def = *j;
 271
 272         if (SetValue(Def, SubMultiClass.RefLoc, SMCTArgs[i],
 273                      std::vector<unsigned>(),
 274                      SubMultiClass.TemplateArgs[i]))
 275           return true;
 276
 277         // Resolve it next.
 278         Def->resolveReferencesTo(Def->getValue(SMCTArgs[i]));
 279
 280         // Now remove it
 281         Def->removeValue(SMCTArgs[i]);
 282       }
 283     } else if (!CurRec->getValue(SMCTArgs[i])->getValue()->isComplete()) {
 284       return Error(SubMultiClass.RefLoc,
 285                    "Value not specified for template argument #"
 286                    + utostr(i) + " (" + SMCTArgs[i] + ") of subclass '" +
 287                    SMC->Rec.getName() + "'!");
 288     }
 289   }
 290
 291   return false;
 292 }
 293
 294 //===----------------------------------------------------------------------===//
 295 // Parser Code
 296 //===----------------------------------------------------------------------===//
 297
 298 /// isObjectStart - Return true if this is a valid first token for an Object.
 299 static bool isObjectStart(tgtok::TokKind K) {
 300   return K == tgtok::Class || K == tgtok::Def ||
 301          K == tgtok::Defm || K == tgtok::Let || K == tgtok::MultiClass;
 302 }
 303
 304 static std::string GetNewAnonymousName() {
 305   static unsigned AnonCounter = 0;
 306   return "anonymous."+utostr(AnonCounter++);
 307 }
 308
 309 /// ParseObjectName - If an object name is specified, return it.  Otherwise,
 310 /// return an anonymous name.
 311 ///   ObjectName ::= ID
 312 ///   ObjectName ::= /*empty*/
 313 ///
 314 std::string TGParser::ParseObjectName() {
 315   if (Lex.getCode() != tgtok::Id)
 316     return GetNewAnonymousName();
 317
 318   std::string Ret = Lex.getCurStrVal();
 319   Lex.Lex();
 320   return Ret;
 321 }
 322
 323
 324 /// ParseClassID - Parse and resolve a reference to a class name.  This returns
 325 /// null on error.
 326 ///
 327 ///    ClassID ::= ID
 328 ///
 329 Record *TGParser::ParseClassID() {
 330   if (Lex.getCode() != tgtok::Id) {
 331     TokError("expected name for ClassID");
 332     return 0;
 333   }
 334
 335   Record *Result = Records.getClass(Lex.getCurStrVal());
 336   if (Result == 0)
 337     TokError("Couldn't find class '" + Lex.getCurStrVal() + "'");
 338
 339   Lex.Lex();
 340   return Result;
 341 }
 342
 343 /// ParseMultiClassID - Parse and resolve a reference to a multiclass name.
 344 /// This returns null on error.
 345 ///
 346 ///    MultiClassID ::= ID
 347 ///
 348 MultiClass *TGParser::ParseMultiClassID() {
 349   if (Lex.getCode() != tgtok::Id) {
 350     TokError("expected name for ClassID");
 351     return 0;
 352   }
 353
 354   MultiClass *Result = MultiClasses[Lex.getCurStrVal()];
 355   if (Result == 0)
 356     TokError("Couldn't find class '" + Lex.getCurStrVal() + "'");
 357
 358   Lex.Lex();
 359   return Result;
 360 }
 361
 362 Record *TGParser::ParseDefmID() {
 363   if (Lex.getCode() != tgtok::Id) {
 364     TokError("expected multiclass name");
 365     return 0;
 366   }
 367
 368   MultiClass *MC = MultiClasses[Lex.getCurStrVal()];
 369   if (MC == 0) {
 370     TokError("Couldn't find multiclass '" + Lex.getCurStrVal() + "'");
 371     return 0;
 372   }
 373
 374   Lex.Lex();
 375   return &MC->Rec;
 376 }
 377
 378
 379 /// ParseSubClassReference - Parse a reference to a subclass or to a templated
 380 /// subclass.  This returns a SubClassRefTy with a null Record* on error.
 381 ///
 382 ///  SubClassRef ::= ClassID
 383 ///  SubClassRef ::= ClassID '<' ValueList '>'
 384 ///
 385 SubClassReference TGParser::
 386 ParseSubClassReference(Record *CurRec, bool isDefm) {
 387   SubClassReference Result;
 388   Result.RefLoc = Lex.getLoc();
 389
 390   if (isDefm)
 391     Result.Rec = ParseDefmID();
 392   else
 393     Result.Rec = ParseClassID();
 394   if (Result.Rec == 0) return Result;
 395
 396   // If there is no template arg list, we're done.
 397   if (Lex.getCode() != tgtok::less)
 398     return Result;
 399   Lex.Lex();  // Eat the '<'
 400
 401   if (Lex.getCode() == tgtok::greater) {
 402     TokError("subclass reference requires a non-empty list of template values");
 403     Result.Rec = 0;
 404     return Result;
 405   }
 406
 407   Result.TemplateArgs = ParseValueList(CurRec, Result.Rec);
 408   if (Result.TemplateArgs.empty()) {
 409     Result.Rec = 0;   // Error parsing value list.
 410     return Result;
 411   }
 412
 413   if (Lex.getCode() != tgtok::greater) {
 414     TokError("expected '>' in template value list");
 415     Result.Rec = 0;
 416     return Result;
 417   }
 418   Lex.Lex();
 419
 420   return Result;
 421 }
 422
 423 /// ParseSubMultiClassReference - Parse a reference to a subclass or to a
 424 /// templated submulticlass.  This returns a SubMultiClassRefTy with a null
 425 /// Record* on error.
 426 ///
 427 ///  SubMultiClassRef ::= MultiClassID
 428 ///  SubMultiClassRef ::= MultiClassID '<' ValueList '>'
 429 ///
 430 SubMultiClassReference TGParser::
 431 ParseSubMultiClassReference(MultiClass *CurMC) {
 432   SubMultiClassReference Result;
 433   Result.RefLoc = Lex.getLoc();
 434
 435   Result.MC = ParseMultiClassID();
 436   if (Result.MC == 0) return Result;
 437
 438   // If there is no template arg list, we're done.
 439   if (Lex.getCode() != tgtok::less)
 440     return Result;
 441   Lex.Lex();  // Eat the '<'
 442
 443   if (Lex.getCode() == tgtok::greater) {
 444     TokError("subclass reference requires a non-empty list of template values");
 445     Result.MC = 0;
 446     return Result;
 447   }
 448
 449   Result.TemplateArgs = ParseValueList(&CurMC->Rec, &Result.MC->Rec);
 450   if (Result.TemplateArgs.empty()) {
 451     Result.MC = 0;   // Error parsing value list.
 452     return Result;
 453   }
 454
 455   if (Lex.getCode() != tgtok::greater) {
 456     TokError("expected '>' in template value list");
 457     Result.MC = 0;
 458     return Result;
 459   }
 460   Lex.Lex();
 461
 462   return Result;
 463 }
 464
 465 /// ParseRangePiece - Parse a bit/value range.
 466 ///   RangePiece ::= INTVAL
 467 ///   RangePiece ::= INTVAL '-' INTVAL
 468 ///   RangePiece ::= INTVAL INTVAL
 469 bool TGParser::ParseRangePiece(std::vector<unsigned> &Ranges) {
 470   if (Lex.getCode() != tgtok::IntVal) {
 471     TokError("expected integer or bitrange");
 472     return true;
 473   }
 474   int64_t Start = Lex.getCurIntVal();
 475   int64_t End;
 476
 477   if (Start < 0)
 478     return TokError("invalid range, cannot be negative");
 479
 480   switch (Lex.Lex()) {  // eat first character.
 481   default:
 482     Ranges.push_back(Start);
 483     return false;
 484   case tgtok::minus:
 485     if (Lex.Lex() != tgtok::IntVal) {
 486       TokError("expected integer value as end of range");
 487       return true;
 488     }
 489     End = Lex.getCurIntVal();
 490     break;
 491   case tgtok::IntVal:
 492     End = -Lex.getCurIntVal();
 493     break;
 494   }
 495   if (End < 0)
 496     return TokError("invalid range, cannot be negative");
 497   Lex.Lex();
 498
 499   // Add to the range.
 500   if (Start < End) {
 501     for (; Start <= End; ++Start)
 502       Ranges.push_back(Start);
 503   } else {
 504     for (; Start >= End; --Start)
 505       Ranges.push_back(Start);
 506   }
 507   return false;
 508 }
 509
 510 /// ParseRangeList - Parse a list of scalars and ranges into scalar values.
 511 ///
 512 ///   RangeList ::= RangePiece (',' RangePiece)*
 513 ///
 514 std::vector<unsigned> TGParser::ParseRangeList() {
 515   std::vector<unsigned> Result;
 516
 517   // Parse the first piece.
 518   if (ParseRangePiece(Result))
 519     return std::vector<unsigned>();
 520   while (Lex.getCode() == tgtok::comma) {
 521     Lex.Lex();  // Eat the comma.
 522
 523     // Parse the next range piece.
 524     if (ParseRangePiece(Result))
 525       return std::vector<unsigned>();
 526   }
 527   return Result;
 528 }
 529
 530 /// ParseOptionalRangeList - Parse either a range list in <>'s or nothing.
 531 ///   OptionalRangeList ::= '<' RangeList '>'
 532 ///   OptionalRangeList ::= /*empty*/
 533 bool TGParser::ParseOptionalRangeList(std::vector<unsigned> &Ranges) {
 534   if (Lex.getCode() != tgtok::less)
 535     return false;
 536
 537   SMLoc StartLoc = Lex.getLoc();
 538   Lex.Lex(); // eat the '<'
 539
 540   // Parse the range list.
 541   Ranges = ParseRangeList();
 542   if (Ranges.empty()) return true;
 543
 544   if (Lex.getCode() != tgtok::greater) {
 545     TokError("expected '>' at end of range list");
 546     return Error(StartLoc, "to match this '<'");
 547   }
 548   Lex.Lex();   // eat the '>'.
 549   return false;
 550 }
 551
 552 /// ParseOptionalBitList - Parse either a bit list in {}'s or nothing.
 553 ///   OptionalBitList ::= '{' RangeList '}'
 554 ///   OptionalBitList ::= /*empty*/
 555 bool TGParser::ParseOptionalBitList(std::vector<unsigned> &Ranges) {
 556   if (Lex.getCode() != tgtok::l_brace)
 557     return false;
 558
 559   SMLoc StartLoc = Lex.getLoc();
 560   Lex.Lex(); // eat the '{'
 561
 562   // Parse the range list.
 563   Ranges = ParseRangeList();
 564   if (Ranges.empty()) return true;
 565
 566   if (Lex.getCode() != tgtok::r_brace) {
 567     TokError("expected '}' at end of bit list");
 568     return Error(StartLoc, "to match this '{'");
 569   }
 570   Lex.Lex();   // eat the '}'.
 571   return false;
 572 }
 573
 574
 575 /// ParseType - Parse and return a tblgen type.  This returns null on error.
 576 ///
 577 ///   Type ::= STRING                       // string type
 578 ///   Type ::= BIT                          // bit type
 579 ///   Type ::= BITS '<' INTVAL '>'          // bits<x> type
 580 ///   Type ::= INT                          // int type
 581 ///   Type ::= LIST '<' Type '>'            // list<x> type
 582 ///   Type ::= CODE                         // code type
 583 ///   Type ::= DAG                          // dag type
 584 ///   Type ::= ClassID                      // Record Type
 585 ///
 586 RecTy *TGParser::ParseType() {
 587   switch (Lex.getCode()) {
 588   default: TokError("Unknown token when expecting a type"); return 0;
 589   case tgtok::String: Lex.Lex(); return new StringRecTy();
 590   case tgtok::Bit:    Lex.Lex(); return new BitRecTy();
 591   case tgtok::Int:    Lex.Lex(); return new IntRecTy();
 592   case tgtok::Code:   Lex.Lex(); return new CodeRecTy();
 593   case tgtok::Dag:    Lex.Lex(); return new DagRecTy();
 594   case tgtok::Id:
 595     if (Record *R = ParseClassID()) return new RecordRecTy(R);
 596     return 0;
 597   case tgtok::Bits: {
 598     if (Lex.Lex() != tgtok::less) { // Eat 'bits'
 599       TokError("expected '<' after bits type");
 600       return 0;
 601     }
 602     if (Lex.Lex() != tgtok::IntVal) {  // Eat '<'
 603       TokError("expected integer in bits<n> type");
 604       return 0;
 605     }
 606     uint64_t Val = Lex.getCurIntVal();
 607     if (Lex.Lex() != tgtok::greater) {  // Eat count.
 608       TokError("expected '>' at end of bits<n> type");
 609       return 0;
 610     }
 611     Lex.Lex();  // Eat '>'
 612     return new BitsRecTy(Val);
 613   }
 614   case tgtok::List: {
 615     if (Lex.Lex() != tgtok::less) { // Eat 'bits'
 616       TokError("expected '<' after list type");
 617       return 0;
 618     }
 619     Lex.Lex();  // Eat '<'
 620     RecTy *SubType = ParseType();
 621     if (SubType == 0) return 0;
 622
 623     if (Lex.getCode() != tgtok::greater) {
 624       TokError("expected '>' at end of list<ty> type");
 625       return 0;
 626     }
 627     Lex.Lex();  // Eat '>'
 628     return new ListRecTy(SubType);
 629   }
 630   }
 631 }
 632
 633 /// ParseIDValue - Parse an ID as a value and decode what it means.
 634 ///
 635 ///  IDValue ::= ID [def local value]
 636 ///  IDValue ::= ID [def template arg]
 637 ///  IDValue ::= ID [multiclass local value]
 638 ///  IDValue ::= ID [multiclass template argument]
 639 ///  IDValue ::= ID [def name]
 640 ///
 641 Init *TGParser::ParseIDValue(Record *CurRec) {
 642   assert(Lex.getCode() == tgtok::Id && "Expected ID in ParseIDValue");
 643   std::string Name = Lex.getCurStrVal();
 644   SMLoc Loc = Lex.getLoc();
 645   Lex.Lex();
 646   return ParseIDValue(CurRec, Name, Loc);
 647 }
 648
 649 /// ParseIDValue - This is just like ParseIDValue above, but it assumes the ID
 650 /// has already been read.
 651 Init *TGParser::ParseIDValue(Record *CurRec,
 652                              const std::string &Name, SMLoc NameLoc) {
 653   if (CurRec) {
 654     if (const RecordVal *RV = CurRec->getValue(Name))
 655       return new VarInit(Name, RV->getType());
 656
 657     std::string TemplateArgName = CurRec->getName()+":"+Name;
 658     if (CurRec->isTemplateArg(TemplateArgName)) {
 659       const RecordVal *RV = CurRec->getValue(TemplateArgName);
 660       assert(RV && "Template arg doesn't exist??");
 661       return new VarInit(TemplateArgName, RV->getType());
 662     }
 663   }
 664
 665   if (CurMultiClass) {
 666     std::string MCName = CurMultiClass->Rec.getName()+"::"+Name;
 667     if (CurMultiClass->Rec.isTemplateArg(MCName)) {
 668       const RecordVal *RV = CurMultiClass->Rec.getValue(MCName);
 669       assert(RV && "Template arg doesn't exist??");
 670       return new VarInit(MCName, RV->getType());
 671     }
 672   }
 673
 674   if (Record *D = Records.getDef(Name))
 675     return new DefInit(D);
 676
 677   Error(NameLoc, "Variable not defined: '" + Name + "'");
 678   return 0;
 679 }
 680
 681 /// ParseOperation - Parse an operator.  This returns null on error.
 682 ///
 683 /// Operation ::= XOperator ['<' Type '>'] '(' Args ')'
 684 ///
 685 Init *TGParser::ParseOperation(Record *CurRec) {
 686   switch (Lex.getCode()) {
 687   default:
 688     TokError("unknown operation");
 689     return 0;
 690     break;
 691   case tgtok::XCar:
 692   case tgtok::XCdr:
 693   case tgtok::XNull:
 694   case tgtok::XCast: {  // Value ::= !unop '(' Value ')'
 695     UnOpInit::UnaryOp Code;
 696     RecTy *Type = 0;
 697
 698     switch (Lex.getCode()) {
 699     default: assert(0 && "Unhandled code!");
 700     case tgtok::XCast:
 701       Lex.Lex();  // eat the operation
 702       Code = UnOpInit::CAST;
 703
 704       Type = ParseOperatorType();
 705
 706       if (Type == 0) {
 707         TokError("did not get type for unary operator");
 708         return 0;
 709       }
 710
 711       break;
 712     case tgtok::XCar:
 713       Lex.Lex();  // eat the operation
 714       Code = UnOpInit::CAR;
 715       break;
 716     case tgtok::XCdr:
 717       Lex.Lex();  // eat the operation
 718       Code = UnOpInit::CDR;
 719       break;
 720     case tgtok::XNull:
 721       Lex.Lex();  // eat the operation
 722       Code = UnOpInit::LNULL;
 723       Type = new IntRecTy;
 724       break;
 725     }
 726     if (Lex.getCode() != tgtok::l_paren) {
 727       TokError("expected '(' after unary operator");
 728       return 0;
 729     }
 730     Lex.Lex();  // eat the '('
 731
 732     Init *LHS = ParseValue(CurRec);
 733     if (LHS == 0) return 0;
 734
 735     if (Code == UnOpInit::CAR
 736         || Code == UnOpInit::CDR
 737         || Code == UnOpInit::LNULL) {
 738       ListInit *LHSl = dynamic_cast<ListInit*>(LHS);
 739       StringInit *LHSs = dynamic_cast<StringInit*>(LHS);
 740       TypedInit *LHSt = dynamic_cast<TypedInit*>(LHS);
 741       if (LHSl == 0 && LHSs == 0 && LHSt == 0) {
 742         TokError("expected list or string type argument in unary operator");
 743         return 0;
 744       }
 745       if (LHSt) {
 746         ListRecTy *LType = dynamic_cast<ListRecTy*>(LHSt->getType());
 747         StringRecTy *SType = dynamic_cast<StringRecTy*>(LHSt->getType());
 748         if (LType == 0 && SType == 0) {
 749           TokError("expected list or string type argumnet in unary operator");
 750           return 0;
 751         }
 752       }
 753
 754       if (Code == UnOpInit::CAR
 755           || Code == UnOpInit::CDR) {
 756         if (LHSl == 0 && LHSt == 0) {
 757           TokError("expected list type argumnet in unary operator");
 758           return 0;
 759         }
 760
 761         if (LHSl && LHSl->getSize() == 0) {
 762           TokError("empty list argument in unary operator");
 763           return 0;
 764         }
 765         if (LHSl) {
 766           Init *Item = LHSl->getElement(0);
 767           TypedInit *Itemt = dynamic_cast<TypedInit*>(Item);
 768           if (Itemt == 0) {
 769             TokError("untyped list element in unary operator");
 770             return 0;
 771           }
 772           if (Code == UnOpInit::CAR) {
 773             Type = Itemt->getType();
 774           } else {
 775             Type = new ListRecTy(Itemt->getType());
 776           }
 777         } else {
 778           assert(LHSt && "expected list type argument in unary operator");
 779           ListRecTy *LType = dynamic_cast<ListRecTy*>(LHSt->getType());
 780           if (LType == 0) {
 781             TokError("expected list type argumnet in unary operator");
 782             return 0;
 783           }
 784           if (Code == UnOpInit::CAR) {
 785             Type = LType->getElementType();
 786           } else {
 787             Type = LType;
 788           }
 789         }
 790       }
 791     }
 792
 793     if (Lex.getCode() != tgtok::r_paren) {
 794       TokError("expected ')' in unary operator");
 795       return 0;
 796     }
 797     Lex.Lex();  // eat the ')'
 798     return (new UnOpInit(Code, LHS, Type))->Fold(CurRec, CurMultiClass);
 799   }
 800
 801   case tgtok::XConcat:
 802   case tgtok::XSRA:
 803   case tgtok::XSRL:
 804   case tgtok::XSHL:
 805   case tgtok::XEq:
 806   case tgtok::XStrConcat: {  // Value ::= !binop '(' Value ',' Value ')'
 807     tgtok::TokKind OpTok = Lex.getCode();
 808     SMLoc OpLoc = Lex.getLoc();
 809     Lex.Lex();  // eat the operation
 810
 811     BinOpInit::BinaryOp Code;
 812     RecTy *Type = 0;
 813
 814     switch (OpTok) {
 815     default: assert(0 && "Unhandled code!");
 816     case tgtok::XConcat: Code = BinOpInit::CONCAT; Type = new DagRecTy(); break;
 817     case tgtok::XSRA:    Code = BinOpInit::SRA;    Type = new IntRecTy(); break;
 818     case tgtok::XSRL:    Code = BinOpInit::SRL;    Type = new IntRecTy(); break;
 819     case tgtok::XSHL:    Code = BinOpInit::SHL;    Type = new IntRecTy(); break;
 820     case tgtok::XEq:     Code = BinOpInit::EQ;     Type = new IntRecTy(); break;
 821     case tgtok::XStrConcat:
 822       Code = BinOpInit::STRCONCAT;
 823       Type = new StringRecTy();
 824       break;
 825     }
 826
 827     if (Lex.getCode() != tgtok::l_paren) {
 828       TokError("expected '(' after binary operator");
 829       return 0;
 830     }
 831     Lex.Lex();  // eat the '('
 832
 833     SmallVector<Init*, 2> InitList;
 834
 835     InitList.push_back(ParseValue(CurRec));
 836     if (InitList.back() == 0) return 0;
 837
 838     while (Lex.getCode() == tgtok::comma) {
 839       Lex.Lex();  // eat the ','
 840
 841       InitList.push_back(ParseValue(CurRec));
 842       if (InitList.back() == 0) return 0;
 843     }
 844
 845     if (Lex.getCode() != tgtok::r_paren) {
 846       TokError("expected ')' in operator");
 847       return 0;
 848     }
 849     Lex.Lex();  // eat the ')'
 850
 851     // We allow multiple operands to associative operators like !strconcat as
 852     // shorthand for nesting them.
 853     if (Code == BinOpInit::STRCONCAT) {
 854       while (InitList.size() > 2) {
 855         Init *RHS = InitList.pop_back_val();
 856         RHS = (new BinOpInit(Code, InitList.back(), RHS, Type))
 857                       ->Fold(CurRec, CurMultiClass);
 858         InitList.back() = RHS;
 859       }
 860     }
 861
 862     if (InitList.size() == 2)
 863       return (new BinOpInit(Code, InitList[0], InitList[1], Type))
 864         ->Fold(CurRec, CurMultiClass);
 865
 866     Error(OpLoc, "expected two operands to operator");
 867     return 0;
 868   }
 869
 870   case tgtok::XIf:
 871   case tgtok::XForEach:
 872   case tgtok::XSubst: {  // Value ::= !ternop '(' Value ',' Value ',' Value ')'
 873     TernOpInit::TernaryOp Code;
 874     RecTy *Type = 0;
 875
 876
 877     tgtok::TokKind LexCode = Lex.getCode();
 878     Lex.Lex();  // eat the operation
 879     switch (LexCode) {
 880     default: assert(0 && "Unhandled code!");
 881     case tgtok::XIf:
 882       Code = TernOpInit::IF;
 883       break;
 884     case tgtok::XForEach:
 885       Code = TernOpInit::FOREACH;
 886       break;
 887     case tgtok::XSubst:
 888       Code = TernOpInit::SUBST;
 889       break;
 890     }
 891     if (Lex.getCode() != tgtok::l_paren) {
 892       TokError("expected '(' after ternary operator");
 893       return 0;
 894     }
 895     Lex.Lex();  // eat the '('
 896
 897     Init *LHS = ParseValue(CurRec);
 898     if (LHS == 0) return 0;
 899
 900     if (Lex.getCode() != tgtok::comma) {
 901       TokError("expected ',' in ternary operator");
 902       return 0;
 903     }
 904     Lex.Lex();  // eat the ','
 905
 906     Init *MHS = ParseValue(CurRec);
 907     if (MHS == 0) return 0;
 908
 909     if (Lex.getCode() != tgtok::comma) {
 910       TokError("expected ',' in ternary operator");
 911       return 0;
 912     }
 913     Lex.Lex();  // eat the ','
 914
 915     Init *RHS = ParseValue(CurRec);
 916     if (RHS == 0) return 0;
 917
 918     if (Lex.getCode() != tgtok::r_paren) {
 919       TokError("expected ')' in binary operator");
 920       return 0;
 921     }
 922     Lex.Lex();  // eat the ')'
 923
 924     switch (LexCode) {
 925     default: assert(0 && "Unhandled code!");
 926     case tgtok::XIf: {
 927       TypedInit *MHSt = dynamic_cast<TypedInit *>(MHS);
 928       TypedInit *RHSt = dynamic_cast<TypedInit *>(RHS);
 929       if (MHSt == 0 || RHSt == 0) {
 930         TokError("could not get type for !if");
 931         return 0;
 932       }
 933       if (MHSt->getType()->typeIsConvertibleTo(RHSt->getType())) {
 934         Type = RHSt->getType();
 935       } else if (RHSt->getType()->typeIsConvertibleTo(MHSt->getType())) {
 936         Type = MHSt->getType();
 937       } else {
 938         TokError("inconsistent types for !if");
 939         return 0;
 940       }
 941       break;
 942     }
 943     case tgtok::XForEach: {
 944       TypedInit *MHSt = dynamic_cast<TypedInit *>(MHS);
 945       if (MHSt == 0) {
 946         TokError("could not get type for !foreach");
 947         return 0;
 948       }
 949       Type = MHSt->getType();
 950       break;
 951     }
 952     case tgtok::XSubst: {
 953       TypedInit *RHSt = dynamic_cast<TypedInit *>(RHS);
 954       if (RHSt == 0) {
 955         TokError("could not get type for !subst");
 956         return 0;
 957       }
 958       Type = RHSt->getType();
 959       break;
 960     }
 961     }
 962     return (new TernOpInit(Code, LHS, MHS, RHS, Type))->Fold(CurRec,
 963                                                              CurMultiClass);
 964   }
 965   }
 966   TokError("could not parse operation");
 967   return 0;
 968 }
 969
 970 /// ParseOperatorType - Parse a type for an operator.  This returns
 971 /// null on error.
 972 ///
 973 /// OperatorType ::= '<' Type '>'
 974 ///
 975 RecTy *TGParser::ParseOperatorType() {
 976   RecTy *Type = 0;
 977
 978   if (Lex.getCode() != tgtok::less) {
 979     TokError("expected type name for operator");
 980     return 0;
 981   }
 982   Lex.Lex();  // eat the <
 983
 984   Type = ParseType();
 985
 986   if (Type == 0) {
 987     TokError("expected type name for operator");
 988     return 0;
 989   }
 990
 991   if (Lex.getCode() != tgtok::greater) {
 992     TokError("expected type name for operator");
 993     return 0;
 994   }
 995   Lex.Lex();  // eat the >
 996
 997   return Type;
 998 }
 999
1000
1001 /// ParseSimpleValue - Parse a tblgen value.  This returns null on error.
1002 ///
1003 ///   SimpleValue ::= IDValue
1004 ///   SimpleValue ::= INTVAL
1005 ///   SimpleValue ::= STRVAL+
1006 ///   SimpleValue ::= CODEFRAGMENT
1007 ///   SimpleValue ::= '?'
1008 ///   SimpleValue ::= '{' ValueList '}'
1009 ///   SimpleValue ::= ID '<' ValueListNE '>'
1010 ///   SimpleValue ::= '[' ValueList ']'
1011 ///   SimpleValue ::= '(' IDValue DagArgList ')'
1012 ///   SimpleValue ::= CONCATTOK '(' Value ',' Value ')'
1013 ///   SimpleValue ::= SHLTOK '(' Value ',' Value ')'
1014 ///   SimpleValue ::= SRATOK '(' Value ',' Value ')'
1015 ///   SimpleValue ::= SRLTOK '(' Value ',' Value ')'
1016 ///   SimpleValue ::= STRCONCATTOK '(' Value ',' Value ')'
1017 ///
1018 Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType) {
1019   Init *R = 0;
1020   switch (Lex.getCode()) {
1021   default: TokError("Unknown token when parsing a value"); break;
1022   case tgtok::IntVal: R = new IntInit(Lex.getCurIntVal()); Lex.Lex(); break;
1023   case tgtok::StrVal: {
1024     std::string Val = Lex.getCurStrVal();
1025     Lex.Lex();
1026
1027     // Handle multiple consecutive concatenated strings.
1028     while (Lex.getCode() == tgtok::StrVal) {
1029       Val += Lex.getCurStrVal();
1030       Lex.Lex();
1031     }
1032
1033     R = new StringInit(Val);
1034     break;
1035   }
1036   case tgtok::CodeFragment:
1037     R = new CodeInit(Lex.getCurStrVal());
1038     Lex.Lex();
1039     break;
1040   case tgtok::question:
1041     R = new UnsetInit();
1042     Lex.Lex();
1043     break;
1044   case tgtok::Id: {
1045     SMLoc NameLoc = Lex.getLoc();
1046     std::string Name = Lex.getCurStrVal();
1047     if (Lex.Lex() != tgtok::less)  // consume the Id.
1048       return ParseIDValue(CurRec, Name, NameLoc);    // Value ::= IDValue
1049
1050     // Value ::= ID '<' ValueListNE '>'
1051     if (Lex.Lex() == tgtok::greater) {
1052       TokError("expected non-empty value list");
1053       return 0;
1054     }
1055
1056     // This is a CLASS<initvalslist> expression.  This is supposed to synthesize
1057     // a new anonymous definition, deriving from CLASS<initvalslist> with no
1058     // body.
1059     Record *Class = Records.getClass(Name);
1060     if (!Class) {
1061       Error(NameLoc, "Expected a class name, got '" + Name + "'");
1062       return 0;
1063     }
1064
1065     std::vector<Init*> ValueList = ParseValueList(CurRec, Class);
1066     if (ValueList.empty()) return 0;
1067
1068     if (Lex.getCode() != tgtok::greater) {
1069       TokError("expected '>' at end of value list");
1070       return 0;
1071     }
1072     Lex.Lex();  // eat the '>'
1073
1074     // Create the new record, set it as CurRec temporarily.
1075     static unsigned AnonCounter = 0;
1076     Record *NewRec = new Record("anonymous.val."+utostr(AnonCounter++),NameLoc);
1077     SubClassReference SCRef;
1078     SCRef.RefLoc = NameLoc;
1079     SCRef.Rec = Class;
1080     SCRef.TemplateArgs = ValueList;
1081     // Add info about the subclass to NewRec.
1082     if (AddSubClass(NewRec, SCRef))
1083       return 0;
1084     NewRec->resolveReferences();
1085     Records.addDef(NewRec);
1086
1087     // The result of the expression is a reference to the new record.
1088     return new DefInit(NewRec);
1089   }
1090   case tgtok::l_brace: {           // Value ::= '{' ValueList '}'
1091     SMLoc BraceLoc = Lex.getLoc();
1092     Lex.Lex(); // eat the '{'
1093     std::vector<Init*> Vals;
1094
1095     if (Lex.getCode() != tgtok::r_brace) {
1096       Vals = ParseValueList(CurRec);
1097       if (Vals.empty()) return 0;
1098     }
1099     if (Lex.getCode() != tgtok::r_brace) {
1100       TokError("expected '}' at end of bit list value");
1101       return 0;
1102     }
1103     Lex.Lex();  // eat the '}'
1104
1105     BitsInit *Result = new BitsInit(Vals.size());
1106     for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
1107       Init *Bit = Vals[i]->convertInitializerTo(new BitRecTy());
1108       if (Bit == 0) {
1109         Error(BraceLoc, "Element #" + utostr(i) + " (" + Vals[i]->getAsString()+
1110               ") is not convertable to a bit");
1111         return 0;
1112       }
1113       Result->setBit(Vals.size()-i-1, Bit);
1114     }
1115     return Result;
1116   }
1117   case tgtok::l_square: {          // Value ::= '[' ValueList ']'
1118     Lex.Lex(); // eat the '['
1119     std::vector<Init*> Vals;
1120
1121     RecTy *DeducedEltTy = 0;
1122     ListRecTy *GivenListTy = 0;
1123
1124     if (ItemType != 0) {
1125       ListRecTy *ListType = dynamic_cast<ListRecTy*>(ItemType);
1126       if (ListType == 0) {
1127         std::stringstream s;
1128         s << "Type mismatch for list, expected list type, got "
1129           << ItemType->getAsString();
1130         TokError(s.str());
1131       }
1132       GivenListTy = ListType;
1133     }
1134
1135     if (Lex.getCode() != tgtok::r_square) {
1136       Vals = ParseValueList(CurRec, 0,
1137                             GivenListTy ? GivenListTy->getElementType() : 0);
1138       if (Vals.empty()) return 0;
1139     }
1140     if (Lex.getCode() != tgtok::r_square) {
1141       TokError("expected ']' at end of list value");
1142       return 0;
1143     }
1144     Lex.Lex();  // eat the ']'
1145
1146     RecTy *GivenEltTy = 0;
1147     if (Lex.getCode() == tgtok::less) {
1148       // Optional list element type
1149       Lex.Lex();  // eat the '<'
1150
1151       GivenEltTy = ParseType();
1152       if (GivenEltTy == 0) {
1153         // Couldn't parse element type
1154         return 0;
1155       }
1156
1157       if (Lex.getCode() != tgtok::greater) {
1158         TokError("expected '>' at end of list element type");
1159         return 0;
1160       }
1161       Lex.Lex();  // eat the '>'
1162     }
1163
1164     // Check elements
1165     RecTy *EltTy = 0;
1166     for (std::vector<Init *>::iterator i = Vals.begin(), ie = Vals.end();
1167          i != ie;
1168          ++i) {
1169       TypedInit *TArg = dynamic_cast<TypedInit*>(*i);
1170       if (TArg == 0) {
1171         TokError("Untyped list element");
1172         return 0;
1173       }
1174       if (EltTy != 0) {
1175         EltTy = resolveTypes(EltTy, TArg->getType());
1176         if (EltTy == 0) {
1177           TokError("Incompatible types in list elements");
1178           return 0;
1179         }
1180       } else {
1181         EltTy = TArg->getType();
1182       }
1183     }
1184
1185     if (GivenEltTy != 0) {
1186       if (EltTy != 0) {
1187         // Verify consistency
1188         if (!EltTy->typeIsConvertibleTo(GivenEltTy)) {
1189           TokError("Incompatible types in list elements");
1190           return 0;
1191         }
1192       }
1193       EltTy = GivenEltTy;
1194     }
1195
1196     if (EltTy == 0) {
1197       if (ItemType == 0) {
1198         TokError("No type for list");
1199         return 0;
1200       }
1201       DeducedEltTy = GivenListTy->getElementType();
1202     } else {
1203       // Make sure the deduced type is compatible with the given type
1204       if (GivenListTy) {
1205         if (!EltTy->typeIsConvertibleTo(GivenListTy->getElementType())) {
1206           TokError("Element type mismatch for list");
1207           return 0;
1208         }
1209       }
1210       DeducedEltTy = EltTy;
1211     }
1212
1213     return new ListInit(Vals, DeducedEltTy);
1214   }
1215   case tgtok::l_paren: {         // Value ::= '(' IDValue DagArgList ')'
1216     Lex.Lex();   // eat the '('
1217     if (Lex.getCode() != tgtok::Id && Lex.getCode() != tgtok::XCast) {
1218       TokError("expected identifier in dag init");
1219       return 0;
1220     }
1221
1222     Init *Operator;
1223     /// LLVMC Requires an old grammar and I don't know how to update it, placate
1224     /// it in the short term by changing the grammar specifically for llvmc.
1225     /// FIXME: REMOVE THIS.
1226     if (!LLVMCHack)
1227       Operator = ParseValue(CurRec);
1228     else {
1229       if (Lex.getCode() == tgtok::Id)
1230         Operator = ParseIDValue(CurRec);
1231       else
1232         Operator = ParseOperation(CurRec);
1233     }
1234     if (Operator == 0) return 0;
1235
1236     // If the operator name is present, parse it.
1237     std::string OperatorName;
1238     if (Lex.getCode() == tgtok::colon) {
1239       if (Lex.Lex() != tgtok::VarName) { // eat the ':'
1240         TokError("expected variable name in dag operator");
1241         return 0;
1242       }
1243       OperatorName = Lex.getCurStrVal();
1244       Lex.Lex();  // eat the VarName.
1245     }
1246
1247     std::vector<std::pair<llvm::Init*, std::string> > DagArgs;
1248     if (Lex.getCode() != tgtok::r_paren) {
1249       DagArgs = ParseDagArgList(CurRec);
1250       if (DagArgs.empty()) return 0;
1251     }
1252
1253     if (Lex.getCode() != tgtok::r_paren) {
1254       TokError("expected ')' in dag init");
1255       return 0;
1256     }
1257     Lex.Lex();  // eat the ')'
1258
1259     return new DagInit(Operator, OperatorName, DagArgs);
1260   }
1261
1262   case tgtok::XCar:
1263   case tgtok::XCdr:
1264   case tgtok::XNull:
1265   case tgtok::XCast:  // Value ::= !unop '(' Value ')'
1266   case tgtok::XConcat:
1267   case tgtok::XSRA:
1268   case tgtok::XSRL:
1269   case tgtok::XSHL:
1270   case tgtok::XEq:
1271   case tgtok::XStrConcat:   // Value ::= !binop '(' Value ',' Value ')'
1272   case tgtok::XIf:
1273   case tgtok::XForEach:
1274   case tgtok::XSubst: {  // Value ::= !ternop '(' Value ',' Value ',' Value ')'
1275     return ParseOperation(CurRec);
1276   }
1277   }
1278
1279   return R;
1280 }
1281
1282 /// ParseValue - Parse a tblgen value.  This returns null on error.
1283 ///
1284 ///   Value       ::= SimpleValue ValueSuffix*
1285 ///   ValueSuffix ::= '{' BitList '}'
1286 ///   ValueSuffix ::= '[' BitList ']'
1287 ///   ValueSuffix ::= '.' ID
1288 ///
1289 Init *TGParser::ParseValue(Record *CurRec, RecTy *ItemType) {
1290   Init *Result = ParseSimpleValue(CurRec, ItemType);
1291   if (Result == 0) return 0;
1292
1293   // Parse the suffixes now if present.
1294   while (1) {
1295     switch (Lex.getCode()) {
1296     default: return Result;
1297     case tgtok::l_brace: {
1298       SMLoc CurlyLoc = Lex.getLoc();
1299       Lex.Lex(); // eat the '{'
1300       std::vector<unsigned> Ranges = ParseRangeList();
1301       if (Ranges.empty()) return 0;
1302
1303       // Reverse the bitlist.
1304       std::reverse(Ranges.begin(), Ranges.end());
1305       Result = Result->convertInitializerBitRange(Ranges);
1306       if (Result == 0) {
1307         Error(CurlyLoc, "Invalid bit range for value");
1308         return 0;
1309       }
1310
1311       // Eat the '}'.
1312       if (Lex.getCode() != tgtok::r_brace) {
1313         TokError("expected '}' at end of bit range list");
1314         return 0;
1315       }
1316       Lex.Lex();
1317       break;
1318     }
1319     case tgtok::l_square: {
1320       SMLoc SquareLoc = Lex.getLoc();
1321       Lex.Lex(); // eat the '['
1322       std::vector<unsigned> Ranges = ParseRangeList();
1323       if (Ranges.empty()) return 0;
1324
1325       Result = Result->convertInitListSlice(Ranges);
1326       if (Result == 0) {
1327         Error(SquareLoc, "Invalid range for list slice");
1328         return 0;
1329       }
1330
1331       // Eat the ']'.
1332       if (Lex.getCode() != tgtok::r_square) {
1333         TokError("expected ']' at end of list slice");
1334         return 0;
1335       }
1336       Lex.Lex();
1337       break;
1338     }
1339     case tgtok::period:
1340       if (Lex.Lex() != tgtok::Id) {  // eat the .
1341         TokError("expected field identifier after '.'");
1342         return 0;
1343       }
1344       if (!Result->getFieldType(Lex.getCurStrVal())) {
1345         TokError("Cannot access field '" + Lex.getCurStrVal() + "' of value '" +
1346                  Result->getAsString() + "'");
1347         return 0;
1348       }
1349       Result = new FieldInit(Result, Lex.getCurStrVal());
1350       Lex.Lex();  // eat field name
1351       break;
1352     }
1353   }
1354 }
1355
1356 /// ParseDagArgList - Parse the argument list for a dag literal expression.
1357 ///
1358 ///    ParseDagArgList ::= Value (':' VARNAME)?
1359 ///    ParseDagArgList ::= ParseDagArgList ',' Value (':' VARNAME)?
1360 std::vector<std::pair<llvm::Init*, std::string> >
1361 TGParser::ParseDagArgList(Record *CurRec) {
1362   std::vector<std::pair<llvm::Init*, std::string> > Result;
1363
1364   while (1) {
1365     Init *Val = ParseValue(CurRec);
1366     if (Val == 0) return std::vector<std::pair<llvm::Init*, std::string> >();
1367
1368     // If the variable name is present, add it.
1369     std::string VarName;
1370     if (Lex.getCode() == tgtok::colon) {
1371       if (Lex.Lex() != tgtok::VarName) { // eat the ':'
1372         TokError("expected variable name in dag literal");
1373         return std::vector<std::pair<llvm::Init*, std::string> >();
1374       }
1375       VarName = Lex.getCurStrVal();
1376       Lex.Lex();  // eat the VarName.
1377     }
1378
1379     Result.push_back(std::make_pair(Val, VarName));
1380
1381     if (Lex.getCode() != tgtok::comma) break;
1382     Lex.Lex(); // eat the ','
1383   }
1384
1385   return Result;
1386 }
1387
1388
1389 /// ParseValueList - Parse a comma separated list of values, returning them as a
1390 /// vector.  Note that this always expects to be able to parse at least one
1391 /// value.  It returns an empty list if this is not possible.
1392 ///
1393 ///   ValueList ::= Value (',' Value)
1394 ///
1395 std::vector<Init*> TGParser::ParseValueList(Record *CurRec, Record *ArgsRec,
1396                                             RecTy *EltTy) {
1397   std::vector<Init*> Result;
1398   RecTy *ItemType = EltTy;
1399   unsigned int ArgN = 0;
1400   if (ArgsRec != 0 && EltTy == 0) {
1401     const std::vector<std::string> &TArgs = ArgsRec->getTemplateArgs();
1402     const RecordVal *RV = ArgsRec->getValue(TArgs[ArgN]);
1403     assert(RV && "Template argument record not found??");
1404     ItemType = RV->getType();
1405     ++ArgN;
1406   }
1407   Result.push_back(ParseValue(CurRec, ItemType));
1408   if (Result.back() == 0) return std::vector<Init*>();
1409
1410   while (Lex.getCode() == tgtok::comma) {
1411     Lex.Lex();  // Eat the comma
1412
1413     if (ArgsRec != 0 && EltTy == 0) {
1414       const std::vector<std::string> &TArgs = ArgsRec->getTemplateArgs();
1415       if (ArgN >= TArgs.size()) {
1416         TokError("too many template arguments");
1417         return std::vector<Init*>();
1418       }
1419       const RecordVal *RV = ArgsRec->getValue(TArgs[ArgN]);
1420       assert(RV && "Template argument record not found??");
1421       ItemType = RV->getType();
1422       ++ArgN;
1423     }
1424     Result.push_back(ParseValue(CurRec, ItemType));
1425     if (Result.back() == 0) return std::vector<Init*>();
1426   }
1427
1428   return Result;
1429 }
1430
1431
1432 /// ParseDeclaration - Read a declaration, returning the name of field ID, or an
1433 /// empty string on error.  This can happen in a number of different context's,
1434 /// including within a def or in the template args for a def (which which case
1435 /// CurRec will be non-null) and within the template args for a multiclass (in
1436 /// which case CurRec will be null, but CurMultiClass will be set).  This can
1437 /// also happen within a def that is within a multiclass, which will set both
1438 /// CurRec and CurMultiClass.
1439 ///
1440 ///  Declaration ::= FIELD? Type ID ('=' Value)?
1441 ///
1442 std::string TGParser::ParseDeclaration(Record *CurRec,
1443                                        bool ParsingTemplateArgs) {
1444   // Read the field prefix if present.
1445   bool HasField = Lex.getCode() == tgtok::Field;
1446   if (HasField) Lex.Lex();
1447
1448   RecTy *Type = ParseType();
1449   if (Type == 0) return "";
1450
1451   if (Lex.getCode() != tgtok::Id) {
1452     TokError("Expected identifier in declaration");
1453     return "";
1454   }
1455
1456   SMLoc IdLoc = Lex.getLoc();
1457   std::string DeclName = Lex.getCurStrVal();
1458   Lex.Lex();
1459
1460   if (ParsingTemplateArgs) {
1461     if (CurRec) {
1462       DeclName = CurRec->getName() + ":" + DeclName;
1463     } else {
1464       assert(CurMultiClass);
1465     }
1466     if (CurMultiClass)
1467       DeclName = CurMultiClass->Rec.getName() + "::" + DeclName;
1468   }
1469
1470   // Add the value.
1471   if (AddValue(CurRec, IdLoc, RecordVal(DeclName, Type, HasField)))
1472     return "";
1473
1474   // If a value is present, parse it.
1475   if (Lex.getCode() == tgtok::equal) {
1476     Lex.Lex();
1477     SMLoc ValLoc = Lex.getLoc();
1478     Init *Val = ParseValue(CurRec, Type);
1479     if (Val == 0 ||
1480         SetValue(CurRec, ValLoc, DeclName, std::vector<unsigned>(), Val))
1481       return "";
1482   }
1483
1484   return DeclName;
1485 }
1486
1487 /// ParseTemplateArgList - Read a template argument list, which is a non-empty
1488 /// sequence of template-declarations in <>'s.  If CurRec is non-null, these are
1489 /// template args for a def, which may or may not be in a multiclass.  If null,
1490 /// these are the template args for a multiclass.
1491 ///
1492 ///    TemplateArgList ::= '<' Declaration (',' Declaration)* '>'
1493 ///
1494 bool TGParser::ParseTemplateArgList(Record *CurRec) {
1495   assert(Lex.getCode() == tgtok::less && "Not a template arg list!");
1496   Lex.Lex(); // eat the '<'
1497
1498   Record *TheRecToAddTo = CurRec ? CurRec : &CurMultiClass->Rec;
1499
1500   // Read the first declaration.
1501   std::string TemplArg = ParseDeclaration(CurRec, true/*templateargs*/);
1502   if (TemplArg.empty())
1503     return true;
1504
1505   TheRecToAddTo->addTemplateArg(TemplArg);
1506
1507   while (Lex.getCode() == tgtok::comma) {
1508     Lex.Lex(); // eat the ','
1509
1510     // Read the following declarations.
1511     TemplArg = ParseDeclaration(CurRec, true/*templateargs*/);
1512     if (TemplArg.empty())
1513       return true;
1514     TheRecToAddTo->addTemplateArg(TemplArg);
1515   }
1516
1517   if (Lex.getCode() != tgtok::greater)
1518     return TokError("expected '>' at end of template argument list");
1519   Lex.Lex(); // eat the '>'.
1520   return false;
1521 }
1522
1523
1524 /// ParseBodyItem - Parse a single item at within the body of a def or class.
1525 ///
1526 ///   BodyItem ::= Declaration ';'
1527 ///   BodyItem ::= LET ID OptionalBitList '=' Value ';'
1528 bool TGParser::ParseBodyItem(Record *CurRec) {
1529   if (Lex.getCode() != tgtok::Let) {
1530     if (ParseDeclaration(CurRec, false).empty())
1531       return true;
1532
1533     if (Lex.getCode() != tgtok::semi)
1534       return TokError("expected ';' after declaration");
1535     Lex.Lex();
1536     return false;
1537   }
1538
1539   // LET ID OptionalRangeList '=' Value ';'
1540   if (Lex.Lex() != tgtok::Id)
1541     return TokError("expected field identifier after let");
1542
1543   SMLoc IdLoc = Lex.getLoc();
1544   std::string FieldName = Lex.getCurStrVal();
1545   Lex.Lex();  // eat the field name.
1546
1547   std::vector<unsigned> BitList;
1548   if (ParseOptionalBitList(BitList))
1549     return true;
1550   std::reverse(BitList.begin(), BitList.end());
1551
1552   if (Lex.getCode() != tgtok::equal)
1553     return TokError("expected '=' in let expression");
1554   Lex.Lex();  // eat the '='.
1555
1556   RecordVal *Field = CurRec->getValue(FieldName);
1557   if (Field == 0)
1558     return TokError("Value '" + FieldName + "' unknown!");
1559
1560   RecTy *Type = Field->getType();
1561
1562   Init *Val = ParseValue(CurRec, Type);
1563   if (Val == 0) return true;
1564
1565   if (Lex.getCode() != tgtok::semi)
1566     return TokError("expected ';' after let expression");
1567   Lex.Lex();
1568
1569   return SetValue(CurRec, IdLoc, FieldName, BitList, Val);
1570 }
1571
1572 /// ParseBody - Read the body of a class or def.  Return true on error, false on
1573 /// success.
1574 ///
1575 ///   Body     ::= ';'
1576 ///   Body     ::= '{' BodyList '}'
1577 ///   BodyList BodyItem*
1578 ///
1579 bool TGParser::ParseBody(Record *CurRec) {
1580   // If this is a null definition, just eat the semi and return.
1581   if (Lex.getCode() == tgtok::semi) {
1582     Lex.Lex();
1583     return false;
1584   }
1585
1586   if (Lex.getCode() != tgtok::l_brace)
1587     return TokError("Expected ';' or '{' to start body");
1588   // Eat the '{'.
1589   Lex.Lex();
1590
1591   while (Lex.getCode() != tgtok::r_brace)
1592     if (ParseBodyItem(CurRec))
1593       return true;
1594
1595   // Eat the '}'.
1596   Lex.Lex();
1597   return false;
1598 }
1599
1600 /// ParseObjectBody - Parse the body of a def or class.  This consists of an
1601 /// optional ClassList followed by a Body.  CurRec is the current def or class
1602 /// that is being parsed.
1603 ///
1604 ///   ObjectBody      ::= BaseClassList Body
1605 ///   BaseClassList   ::= /*empty*/
1606 ///   BaseClassList   ::= ':' BaseClassListNE
1607 ///   BaseClassListNE ::= SubClassRef (',' SubClassRef)*
1608 ///
1609 bool TGParser::ParseObjectBody(Record *CurRec) {
1610   // If there is a baseclass list, read it.
1611   if (Lex.getCode() == tgtok::colon) {
1612     Lex.Lex();
1613
1614     // Read all of the subclasses.
1615     SubClassReference SubClass = ParseSubClassReference(CurRec, false);
1616     while (1) {
1617       // Check for error.
1618       if (SubClass.Rec == 0) return true;
1619
1620       // Add it.
1621       if (AddSubClass(CurRec, SubClass))
1622         return true;
1623
1624       if (Lex.getCode() != tgtok::comma) break;
1625       Lex.Lex(); // eat ','.
1626       SubClass = ParseSubClassReference(CurRec, false);
1627     }
1628   }
1629
1630   // Process any variables on the let stack.
1631   for (unsigned i = 0, e = LetStack.size(); i != e; ++i)
1632     for (unsigned j = 0, e = LetStack[i].size(); j != e; ++j)
1633       if (SetValue(CurRec, LetStack[i][j].Loc, LetStack[i][j].Name,
1634                    LetStack[i][j].Bits, LetStack[i][j].Value))
1635         return true;
1636
1637   return ParseBody(CurRec);
1638 }
1639
1640 /// ParseDef - Parse and return a top level or multiclass def, return the record
1641 /// corresponding to it.  This returns null on error.
1642 ///
1643 ///   DefInst ::= DEF ObjectName ObjectBody
1644 ///
1645 bool TGParser::ParseDef(MultiClass *CurMultiClass) {
1646   SMLoc DefLoc = Lex.getLoc();
1647   assert(Lex.getCode() == tgtok::Def && "Unknown tok");
1648   Lex.Lex();  // Eat the 'def' token.
1649
1650   // Parse ObjectName and make a record for it.
1651   Record *CurRec = new Record(ParseObjectName(), DefLoc);
1652
1653   if (!CurMultiClass) {
1654     // Top-level def definition.
1655
1656     // Ensure redefinition doesn't happen.
1657     if (Records.getDef(CurRec->getName())) {
1658       Error(DefLoc, "def '" + CurRec->getName() + "' already defined");
1659       return true;
1660     }
1661     Records.addDef(CurRec);
1662   } else {
1663     // Otherwise, a def inside a multiclass, add it to the multiclass.
1664     for (unsigned i = 0, e = CurMultiClass->DefPrototypes.size(); i != e; ++i)
1665       if (CurMultiClass->DefPrototypes[i]->getName() == CurRec->getName()) {
1666         Error(DefLoc, "def '" + CurRec->getName() +
1667               "' already defined in this multiclass!");
1668         return true;
1669       }
1670     CurMultiClass->DefPrototypes.push_back(CurRec);
1671   }
1672
1673   if (ParseObjectBody(CurRec))
1674     return true;
1675
1676   if (CurMultiClass == 0)  // Def's in multiclasses aren't really defs.
1677     CurRec->resolveReferences();
1678
1679   // If ObjectBody has template arguments, it's an error.
1680   assert(CurRec->getTemplateArgs().empty() && "How'd this get template args?");
1681
1682   if (CurMultiClass) {
1683     // Copy the template arguments for the multiclass into the def.
1684     const std::vector<std::string> &TArgs =
1685                                 CurMultiClass->Rec.getTemplateArgs();
1686
1687     for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
1688       const RecordVal *RV = CurMultiClass->Rec.getValue(TArgs[i]);
1689       assert(RV && "Template arg doesn't exist?");
1690       CurRec->addValue(*RV);
1691     }
1692   }
1693
1694   return false;
1695 }
1696
1697
1698 /// ParseClass - Parse a tblgen class definition.
1699 ///
1700 ///   ClassInst ::= CLASS ID TemplateArgList? ObjectBody
1701 ///
1702 bool TGParser::ParseClass() {
1703   assert(Lex.getCode() == tgtok::Class && "Unexpected token!");
1704   Lex.Lex();
1705
1706   if (Lex.getCode() != tgtok::Id)
1707     return TokError("expected class name after 'class' keyword");
1708
1709   Record *CurRec = Records.getClass(Lex.getCurStrVal());
1710   if (CurRec) {
1711     // If the body was previously defined, this is an error.
1712     if (!CurRec->getValues().empty() ||
1713         !CurRec->getSuperClasses().empty() ||
1714         !CurRec->getTemplateArgs().empty())
1715       return TokError("Class '" + CurRec->getName() + "' already defined");
1716   } else {
1717     // If this is the first reference to this class, create and add it.
1718     CurRec = new Record(Lex.getCurStrVal(), Lex.getLoc());
1719     Records.addClass(CurRec);
1720   }
1721   Lex.Lex(); // eat the name.
1722
1723   // If there are template args, parse them.
1724   if (Lex.getCode() == tgtok::less)
1725     if (ParseTemplateArgList(CurRec))
1726       return true;
1727
1728   // Finally, parse the object body.
1729   return ParseObjectBody(CurRec);
1730 }
1731
1732 /// ParseLetList - Parse a non-empty list of assignment expressions into a list
1733 /// of LetRecords.
1734 ///
1735 ///   LetList ::= LetItem (',' LetItem)*
1736 ///   LetItem ::= ID OptionalRangeList '=' Value
1737 ///
1738 std::vector<LetRecord> TGParser::ParseLetList() {
1739   std::vector<LetRecord> Result;
1740
1741   while (1) {
1742     if (Lex.getCode() != tgtok::Id) {
1743       TokError("expected identifier in let definition");
1744       return std::vector<LetRecord>();
1745     }
1746     std::string Name = Lex.getCurStrVal();
1747     SMLoc NameLoc = Lex.getLoc();
1748     Lex.Lex();  // Eat the identifier.
1749
1750     // Check for an optional RangeList.
1751     std::vector<unsigned> Bits;
1752     if (ParseOptionalRangeList(Bits))
1753       return std::vector<LetRecord>();
1754     std::reverse(Bits.begin(), Bits.end());
1755
1756     if (Lex.getCode() != tgtok::equal) {
1757       TokError("expected '=' in let expression");
1758       return std::vector<LetRecord>();
1759     }
1760     Lex.Lex();  // eat the '='.
1761
1762     Init *Val = ParseValue(0);
1763     if (Val == 0) return std::vector<LetRecord>();
1764
1765     // Now that we have everything, add the record.
1766     Result.push_back(LetRecord(Name, Bits, Val, NameLoc));
1767
1768     if (Lex.getCode() != tgtok::comma)
1769       return Result;
1770     Lex.Lex();  // eat the comma.
1771   }
1772 }
1773
1774 /// ParseTopLevelLet - Parse a 'let' at top level.  This can be a couple of
1775 /// different related productions. This works inside multiclasses too.
1776 ///
1777 ///   Object ::= LET LetList IN '{' ObjectList '}'
1778 ///   Object ::= LET LetList IN Object
1779 ///
1780 bool TGParser::ParseTopLevelLet(MultiClass *CurMultiClass) {
1781   assert(Lex.getCode() == tgtok::Let && "Unexpected token");
1782   Lex.Lex();
1783
1784   // Add this entry to the let stack.
1785   std::vector<LetRecord> LetInfo = ParseLetList();
1786   if (LetInfo.empty()) return true;
1787   LetStack.push_back(LetInfo);
1788
1789   if (Lex.getCode() != tgtok::In)
1790     return TokError("expected 'in' at end of top-level 'let'");
1791   Lex.Lex();
1792
1793   // If this is a scalar let, just handle it now
1794   if (Lex.getCode() != tgtok::l_brace) {
1795     // LET LetList IN Object
1796     if (ParseObject(CurMultiClass))
1797       return true;
1798   } else {   // Object ::= LETCommand '{' ObjectList '}'
1799     SMLoc BraceLoc = Lex.getLoc();
1800     // Otherwise, this is a group let.
1801     Lex.Lex();  // eat the '{'.
1802
1803     // Parse the object list.
1804     if (ParseObjectList(CurMultiClass))
1805       return true;
1806
1807     if (Lex.getCode() != tgtok::r_brace) {
1808       TokError("expected '}' at end of top level let command");
1809       return Error(BraceLoc, "to match this '{'");
1810     }
1811     Lex.Lex();
1812   }
1813
1814   // Outside this let scope, this let block is not active.
1815   LetStack.pop_back();
1816   return false;
1817 }
1818
1819 /// ParseMultiClass - Parse a multiclass definition.
1820 ///
1821 ///  MultiClassInst ::= MULTICLASS ID TemplateArgList?
1822 ///                     ':' BaseMultiClassList '{' MultiClassDef+ '}'
1823 ///
1824 bool TGParser::ParseMultiClass() {
1825   assert(Lex.getCode() == tgtok::MultiClass && "Unexpected token");
1826   Lex.Lex();  // Eat the multiclass token.
1827
1828   if (Lex.getCode() != tgtok::Id)
1829     return TokError("expected identifier after multiclass for name");
1830   std::string Name = Lex.getCurStrVal();
1831
1832   if (MultiClasses.count(Name))
1833     return TokError("multiclass '" + Name + "' already defined");
1834
1835   CurMultiClass = MultiClasses[Name] = new MultiClass(Name, Lex.getLoc());
1836   Lex.Lex();  // Eat the identifier.
1837
1838   // If there are template args, parse them.
1839   if (Lex.getCode() == tgtok::less)
1840     if (ParseTemplateArgList(0))
1841       return true;
1842
1843   bool inherits = false;
1844
1845   // If there are submulticlasses, parse them.
1846   if (Lex.getCode() == tgtok::colon) {
1847     inherits = true;
1848
1849     Lex.Lex();
1850
1851     // Read all of the submulticlasses.
1852     SubMultiClassReference SubMultiClass =
1853       ParseSubMultiClassReference(CurMultiClass);
1854     while (1) {
1855       // Check for error.
1856       if (SubMultiClass.MC == 0) return true;
1857
1858       // Add it.
1859       if (AddSubMultiClass(CurMultiClass, SubMultiClass))
1860         return true;
1861
1862       if (Lex.getCode() != tgtok::comma) break;
1863       Lex.Lex(); // eat ','.
1864       SubMultiClass = ParseSubMultiClassReference(CurMultiClass);
1865     }
1866   }
1867
1868   if (Lex.getCode() != tgtok::l_brace) {
1869     if (!inherits)
1870       return TokError("expected '{' in multiclass definition");
1871     else if (Lex.getCode() != tgtok::semi)
1872       return TokError("expected ';' in multiclass definition");
1873     else
1874       Lex.Lex();  // eat the ';'.
1875   } else {
1876     if (Lex.Lex() == tgtok::r_brace)  // eat the '{'.
1877       return TokError("multiclass must contain at least one def");
1878
1879     while (Lex.getCode() != tgtok::r_brace) {
1880       switch (Lex.getCode()) {
1881         default:
1882           return TokError("expected 'let', 'def' or 'defm' in multiclass body");
1883         case tgtok::Let:
1884         case tgtok::Def:
1885         case tgtok::Defm:
1886           if (ParseObject(CurMultiClass))
1887             return true;
1888          break;
1889       }
1890     }
1891     Lex.Lex();  // eat the '}'.
1892   }
1893
1894   CurMultiClass = 0;
1895   return false;
1896 }
1897
1898 /// ParseDefm - Parse the instantiation of a multiclass.
1899 ///
1900 ///   DefMInst ::= DEFM ID ':' DefmSubClassRef ';'
1901 ///
1902 bool TGParser::ParseDefm(MultiClass *CurMultiClass) {
1903   assert(Lex.getCode() == tgtok::Defm && "Unexpected token!");
1904
1905   std::string DefmPrefix;
1906   if (Lex.Lex() == tgtok::Id) {  // eat the defm.
1907     DefmPrefix = Lex.getCurStrVal();
1908     Lex.Lex();  // Eat the defm prefix.
1909   }
1910
1911   SMLoc DefmPrefixLoc = Lex.getLoc();
1912   if (Lex.getCode() != tgtok::colon)
1913     return TokError("expected ':' after defm identifier");
1914
1915   // Keep track of the new generated record definitions.
1916   std::vector<Record*> NewRecDefs;
1917
1918   // This record also inherits from a regular class (non-multiclass)?
1919   bool InheritFromClass = false;
1920
1921   // eat the colon.
1922   Lex.Lex();
1923
1924   SMLoc SubClassLoc = Lex.getLoc();
1925   SubClassReference Ref = ParseSubClassReference(0, true);
1926
1927   while (1) {
1928     if (Ref.Rec == 0) return true;
1929
1930     // To instantiate a multiclass, we need to first get the multiclass, then
1931     // instantiate each def contained in the multiclass with the SubClassRef
1932     // template parameters.
1933     MultiClass *MC = MultiClasses[Ref.Rec->getName()];
1934     assert(MC && "Didn't lookup multiclass correctly?");
1935     std::vector<Init*> &TemplateVals = Ref.TemplateArgs;
1936
1937     // Verify that the correct number of template arguments were specified.
1938     const std::vector<std::string> &TArgs = MC->Rec.getTemplateArgs();
1939     if (TArgs.size() < TemplateVals.size())
1940       return Error(SubClassLoc,
1941                    "more template args specified than multiclass expects");
1942
1943     // Loop over all the def's in the multiclass, instantiating each one.
1944     for (unsigned i = 0, e = MC->DefPrototypes.size(); i != e; ++i) {
1945       Record *DefProto = MC->DefPrototypes[i];
1946
1947       // Add in the defm name.  If the defm prefix is empty, give each
1948       // instantiated def a unique name.  Otherwise, if "#NAME#" exists in the
1949       // name, substitute the prefix for #NAME#.  Otherwise, use the defm name
1950       // as a prefix.
1951       std::string DefName = DefProto->getName();
1952       if (DefmPrefix.empty()) {
1953         DefName = GetNewAnonymousName();
1954       } else {
1955         std::string::size_type idx = DefName.find("#NAME#");
1956         if (idx != std::string::npos) {
1957           DefName.replace(idx, 6, DefmPrefix);
1958         } else {
1959           // Add the suffix to the defm name to get the new name.
1960           DefName = DefmPrefix + DefName;
1961         }
1962       }
1963
1964       Record *CurRec = new Record(DefName, DefmPrefixLoc);
1965
1966       SubClassReference Ref;
1967       Ref.RefLoc = DefmPrefixLoc;
1968       Ref.Rec = DefProto;
1969       AddSubClass(CurRec, Ref);
1970
1971       // Loop over all of the template arguments, setting them to the specified
1972       // value or leaving them as the default if necessary.
1973       for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
1974         // Check if a value is specified for this temp-arg.
1975         if (i < TemplateVals.size()) {
1976           // Set it now.
1977           if (SetValue(CurRec, DefmPrefixLoc, TArgs[i], std::vector<unsigned>(),
1978                        TemplateVals[i]))
1979             return true;
1980
1981           // Resolve it next.
1982           CurRec->resolveReferencesTo(CurRec->getValue(TArgs[i]));
1983
1984           // Now remove it.
1985           CurRec->removeValue(TArgs[i]);
1986
1987         } else if (!CurRec->getValue(TArgs[i])->getValue()->isComplete()) {
1988           return Error(SubClassLoc,
1989                        "value not specified for template argument #"+
1990                        utostr(i) + " (" + TArgs[i] + ") of multiclassclass '" +
1991                        MC->Rec.getName() + "'");
1992         }
1993       }
1994
1995       // If the mdef is inside a 'let' expression, add to each def.
1996       for (unsigned i = 0, e = LetStack.size(); i != e; ++i)
1997         for (unsigned j = 0, e = LetStack[i].size(); j != e; ++j)
1998           if (SetValue(CurRec, LetStack[i][j].Loc, LetStack[i][j].Name,
1999                        LetStack[i][j].Bits, LetStack[i][j].Value)) {
2000             Error(DefmPrefixLoc, "when instantiating this defm");
2001             return true;
2002           }
2003
2004       // Ensure redefinition doesn't happen.
2005       if (Records.getDef(CurRec->getName()))
2006         return Error(DefmPrefixLoc, "def '" + CurRec->getName() +
2007                      "' already defined, instantiating defm with subdef '" +
2008                      DefProto->getName() + "'");
2009
2010       // Don't create a top level definition for defm inside multiclasses,
2011       // instead, only update the prototypes and bind the template args
2012       // with the new created definition.
2013       if (CurMultiClass) {
2014         for (unsigned i = 0, e = CurMultiClass->DefPrototypes.size();
2015              i != e; ++i) {
2016           if (CurMultiClass->DefPrototypes[i]->getName() == CurRec->getName()) {
2017             Error(DefmPrefixLoc, "defm '" + CurRec->getName() +
2018                   "' already defined in this multiclass!");
2019             return 0;
2020           }
2021         }
2022         CurMultiClass->DefPrototypes.push_back(CurRec);
2023
2024         // Copy the template arguments for the multiclass into the new def.
2025         const std::vector<std::string> &TA =
2026           CurMultiClass->Rec.getTemplateArgs();
2027
2028         for (unsigned i = 0, e = TA.size(); i != e; ++i) {
2029           const RecordVal *RV = CurMultiClass->Rec.getValue(TA[i]);
2030           assert(RV && "Template arg doesn't exist?");
2031           CurRec->addValue(*RV);
2032         }
2033       } else {
2034         Records.addDef(CurRec);
2035       }
2036
2037       NewRecDefs.push_back(CurRec);
2038     }
2039
2040     if (Lex.getCode() != tgtok::comma) break;
2041     Lex.Lex(); // eat ','.
2042
2043     SubClassLoc = Lex.getLoc();
2044
2045     // A defm can inherit from regular classes (non-multiclass) as
2046     // long as they come in the end of the inheritance list.
2047     InheritFromClass = (Records.getClass(Lex.getCurStrVal()) != 0);
2048
2049     if (InheritFromClass)
2050       break;
2051
2052     Ref = ParseSubClassReference(0, true);
2053   }
2054
2055   if (InheritFromClass) {
2056     // Process all the classes to inherit as if they were part of a
2057     // regular 'def' and inherit all record values.
2058     SubClassReference SubClass = ParseSubClassReference(0, false);
2059     while (1) {
2060       // Check for error.
2061       if (SubClass.Rec == 0) return true;
2062
2063       // Get the expanded definition prototypes and teach them about
2064       // the record values the current class to inherit has
2065       for (unsigned i = 0, e = NewRecDefs.size(); i != e; ++i) {
2066         Record *CurRec = NewRecDefs[i];
2067
2068         // Add it.
2069         if (AddSubClass(CurRec, SubClass))
2070           return true;
2071
2072         // Process any variables on the let stack.
2073         for (unsigned i = 0, e = LetStack.size(); i != e; ++i)
2074           for (unsigned j = 0, e = LetStack[i].size(); j != e; ++j)
2075             if (SetValue(CurRec, LetStack[i][j].Loc, LetStack[i][j].Name,
2076                          LetStack[i][j].Bits, LetStack[i][j].Value))
2077               return true;
2078       }
2079
2080       if (Lex.getCode() != tgtok::comma) break;
2081       Lex.Lex(); // eat ','.
2082       SubClass = ParseSubClassReference(0, false);
2083     }
2084   }
2085
2086   if (!CurMultiClass)
2087     for (unsigned i = 0, e = NewRecDefs.size(); i != e; ++i)
2088       NewRecDefs[i]->resolveReferences();
2089
2090   if (Lex.getCode() != tgtok::semi)
2091     return TokError("expected ';' at end of defm");
2092   Lex.Lex();
2093
2094   return false;
2095 }
2096
2097 /// ParseObject
2098 ///   Object ::= ClassInst
2099 ///   Object ::= DefInst
2100 ///   Object ::= MultiClassInst
2101 ///   Object ::= DefMInst
2102 ///   Object ::= LETCommand '{' ObjectList '}'
2103 ///   Object ::= LETCommand Object
2104 bool TGParser::ParseObject(MultiClass *MC) {
2105   switch (Lex.getCode()) {
2106   default: assert(0 && "This is not an object");
2107   case tgtok::Let:   return ParseTopLevelLet(MC);
2108   case tgtok::Def:   return ParseDef(MC);
2109   case tgtok::Defm:  return ParseDefm(MC);
2110   case tgtok::Class: return ParseClass();
2111   case tgtok::MultiClass: return ParseMultiClass();
2112   }
2113 }
2114
2115 /// ParseObjectList
2116 ///   ObjectList :== Object*
2117 bool TGParser::ParseObjectList(MultiClass *MC) {
2118   while (isObjectStart(Lex.getCode())) {
2119     if (ParseObject(MC))
2120       return true;
2121   }
2122   return false;
2123 }
2124
2125 bool TGParser::ParseFile() {
2126   Lex.Lex(); // Prime the lexer.
2127   if (ParseObjectList()) return true;
2128
2129   // If we have unread input at the end of the file, report it.
2130   if (Lex.getCode() == tgtok::Eof)
2131     return false;
2132
2133   return TokError("Unexpected input at top level");
2134 }
2135