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