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