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