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