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