contrib/llvm-project/llvm/lib/TableGen/TGParser.cpp

   1 //===- TGParser.cpp - Parser for TableGen Files ---------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Implement the Parser for TableGen.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "TGParser.h"
  14 #include "llvm/ADT/None.h"
  15 #include "llvm/ADT/STLExtras.h"
  16 #include "llvm/ADT/SmallVector.h"
  17 #include "llvm/ADT/StringExtras.h"
  18 #include "llvm/Config/llvm-config.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 static bool checkBitsConcrete(Record &R, const RecordVal &RV) {
  72   BitsInit *BV = cast<BitsInit>(RV.getValue());
  73   for (unsigned i = 0, e = BV->getNumBits(); i != e; ++i) {
  74     Init *Bit = BV->getBit(i);
  75     bool IsReference = false;
  76     if (auto VBI = dyn_cast<VarBitInit>(Bit)) {
  77       if (auto VI = dyn_cast<VarInit>(VBI->getBitVar())) {
  78         if (R.getValue(VI->getName()))
  79           IsReference = true;
  80       }
  81     } else if (isa<VarInit>(Bit)) {
  82       IsReference = true;
  83     }
  84     if (!(IsReference || Bit->isConcrete()))
  85       return false;
  86   }
  87   return true;
  88 }
  89
  90 static void checkConcrete(Record &R) {
  91   for (const RecordVal &RV : R.getValues()) {
  92     // HACK: Disable this check for variables declared with 'field'. This is
  93     // done merely because existing targets have legitimate cases of
  94     // non-concrete variables in helper defs. Ideally, we'd introduce a
  95     // 'maybe' or 'optional' modifier instead of this.
  96     if (RV.getPrefix())
  97       continue;
  98
  99     if (Init *V = RV.getValue()) {
 100       bool Ok = isa<BitsInit>(V) ? checkBitsConcrete(R, RV) : V->isConcrete();
 101       if (!Ok) {
 102         PrintError(R.getLoc(),
 103                    Twine("Initializer of '") + RV.getNameInitAsString() +
 104                    "' in '" + R.getNameInitAsString() +
 105                    "' could not be fully resolved: " +
 106                    RV.getValue()->getAsString());
 107       }
 108     }
 109   }
 110 }
 111
 112 /// Return an Init with a qualifier prefix referring
 113 /// to CurRec's name.
 114 static Init *QualifyName(Record &CurRec, MultiClass *CurMultiClass,
 115                         Init *Name, StringRef Scoper) {
 116   Init *NewName =
 117       BinOpInit::getStrConcat(CurRec.getNameInit(), StringInit::get(Scoper));
 118   NewName = BinOpInit::getStrConcat(NewName, Name);
 119   if (CurMultiClass && Scoper != "::") {
 120     Init *Prefix = BinOpInit::getStrConcat(CurMultiClass->Rec.getNameInit(),
 121                                            StringInit::get("::"));
 122     NewName = BinOpInit::getStrConcat(Prefix, NewName);
 123   }
 124
 125   if (BinOpInit *BinOp = dyn_cast<BinOpInit>(NewName))
 126     NewName = BinOp->Fold(&CurRec);
 127   return NewName;
 128 }
 129
 130 /// Return the qualified version of the implicit 'NAME' template argument.
 131 static Init *QualifiedNameOfImplicitName(Record &Rec,
 132                                          MultiClass *MC = nullptr) {
 133   return QualifyName(Rec, MC, StringInit::get("NAME"), MC ? "::" : ":");
 134 }
 135
 136 static Init *QualifiedNameOfImplicitName(MultiClass *MC) {
 137   return QualifiedNameOfImplicitName(MC->Rec, MC);
 138 }
 139
 140 bool TGParser::AddValue(Record *CurRec, SMLoc Loc, const RecordVal &RV) {
 141   if (!CurRec)
 142     CurRec = &CurMultiClass->Rec;
 143
 144   if (RecordVal *ERV = CurRec->getValue(RV.getNameInit())) {
 145     // The value already exists in the class, treat this as a set.
 146     if (ERV->setValue(RV.getValue()))
 147       return Error(Loc, "New definition of '" + RV.getName() + "' of type '" +
 148                    RV.getType()->getAsString() + "' is incompatible with " +
 149                    "previous definition of type '" +
 150                    ERV->getType()->getAsString() + "'");
 151   } else {
 152     CurRec->addValue(RV);
 153   }
 154   return false;
 155 }
 156
 157 /// SetValue -
 158 /// Return true on error, false on success.
 159 bool TGParser::SetValue(Record *CurRec, SMLoc Loc, Init *ValName,
 160                         ArrayRef<unsigned> BitList, Init *V,
 161                         bool AllowSelfAssignment) {
 162   if (!V) return false;
 163
 164   if (!CurRec) CurRec = &CurMultiClass->Rec;
 165
 166   RecordVal *RV = CurRec->getValue(ValName);
 167   if (!RV)
 168     return Error(Loc, "Value '" + ValName->getAsUnquotedString() +
 169                  "' unknown!");
 170
 171   // Do not allow assignments like 'X = X'.  This will just cause infinite loops
 172   // in the resolution machinery.
 173   if (BitList.empty())
 174     if (VarInit *VI = dyn_cast<VarInit>(V))
 175       if (VI->getNameInit() == ValName && !AllowSelfAssignment)
 176         return Error(Loc, "Recursion / self-assignment forbidden");
 177
 178   // If we are assigning to a subset of the bits in the value... then we must be
 179   // assigning to a field of BitsRecTy, which must have a BitsInit
 180   // initializer.
 181   //
 182   if (!BitList.empty()) {
 183     BitsInit *CurVal = dyn_cast<BitsInit>(RV->getValue());
 184     if (!CurVal)
 185       return Error(Loc, "Value '" + ValName->getAsUnquotedString() +
 186                    "' is not a bits type");
 187
 188     // Convert the incoming value to a bits type of the appropriate size...
 189     Init *BI = V->getCastTo(BitsRecTy::get(BitList.size()));
 190     if (!BI)
 191       return Error(Loc, "Initializer is not compatible with bit range");
 192
 193     SmallVector<Init *, 16> NewBits(CurVal->getNumBits());
 194
 195     // Loop over bits, assigning values as appropriate.
 196     for (unsigned i = 0, e = BitList.size(); i != e; ++i) {
 197       unsigned Bit = BitList[i];
 198       if (NewBits[Bit])
 199         return Error(Loc, "Cannot set bit #" + Twine(Bit) + " of value '" +
 200                      ValName->getAsUnquotedString() + "' more than once");
 201       NewBits[Bit] = BI->getBit(i);
 202     }
 203
 204     for (unsigned i = 0, e = CurVal->getNumBits(); i != e; ++i)
 205       if (!NewBits[i])
 206         NewBits[i] = CurVal->getBit(i);
 207
 208     V = BitsInit::get(NewBits);
 209   }
 210
 211   if (RV->setValue(V)) {
 212     std::string InitType;
 213     if (BitsInit *BI = dyn_cast<BitsInit>(V))
 214       InitType = (Twine("' of type bit initializer with length ") +
 215                   Twine(BI->getNumBits())).str();
 216     else if (TypedInit *TI = dyn_cast<TypedInit>(V))
 217       InitType = (Twine("' of type '") + TI->getType()->getAsString()).str();
 218     return Error(Loc, "Value '" + ValName->getAsUnquotedString() +
 219                           "' of type '" + RV->getType()->getAsString() +
 220                           "' is incompatible with initializer '" +
 221                           V->getAsString() + InitType + "'");
 222   }
 223   return false;
 224 }
 225
 226 /// AddSubClass - Add SubClass as a subclass to CurRec, resolving its template
 227 /// args as SubClass's template arguments.
 228 bool TGParser::AddSubClass(Record *CurRec, SubClassReference &SubClass) {
 229   Record *SC = SubClass.Rec;
 230   // Add all of the values in the subclass into the current class.
 231   for (const RecordVal &Val : SC->getValues())
 232     if (AddValue(CurRec, SubClass.RefRange.Start, Val))
 233       return true;
 234
 235   ArrayRef<Init *> TArgs = SC->getTemplateArgs();
 236
 237   // Ensure that an appropriate number of template arguments are specified.
 238   if (TArgs.size() < SubClass.TemplateArgs.size())
 239     return Error(SubClass.RefRange.Start,
 240                  "More template args specified than expected");
 241
 242   // Loop over all of the template arguments, setting them to the specified
 243   // value or leaving them as the default if necessary.
 244   MapResolver R(CurRec);
 245
 246   for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
 247     if (i < SubClass.TemplateArgs.size()) {
 248       // If a value is specified for this template arg, set it now.
 249       if (SetValue(CurRec, SubClass.RefRange.Start, TArgs[i],
 250                    None, SubClass.TemplateArgs[i]))
 251         return true;
 252     } else if (!CurRec->getValue(TArgs[i])->getValue()->isComplete()) {
 253       return Error(SubClass.RefRange.Start,
 254                    "Value not specified for template argument #" +
 255                    Twine(i) + " (" + TArgs[i]->getAsUnquotedString() +
 256                    ") of subclass '" + SC->getNameInitAsString() + "'!");
 257     }
 258
 259     R.set(TArgs[i], CurRec->getValue(TArgs[i])->getValue());
 260
 261     CurRec->removeValue(TArgs[i]);
 262   }
 263
 264   Init *Name;
 265   if (CurRec->isClass())
 266     Name =
 267         VarInit::get(QualifiedNameOfImplicitName(*CurRec), StringRecTy::get());
 268   else
 269     Name = CurRec->getNameInit();
 270   R.set(QualifiedNameOfImplicitName(*SC), Name);
 271
 272   CurRec->resolveReferences(R);
 273
 274   // Since everything went well, we can now set the "superclass" list for the
 275   // current record.
 276   ArrayRef<std::pair<Record *, SMRange>> SCs = SC->getSuperClasses();
 277   for (const auto &SCPair : SCs) {
 278     if (CurRec->isSubClassOf(SCPair.first))
 279       return Error(SubClass.RefRange.Start,
 280                    "Already subclass of '" + SCPair.first->getName() + "'!\n");
 281     CurRec->addSuperClass(SCPair.first, SCPair.second);
 282   }
 283
 284   if (CurRec->isSubClassOf(SC))
 285     return Error(SubClass.RefRange.Start,
 286                  "Already subclass of '" + SC->getName() + "'!\n");
 287   CurRec->addSuperClass(SC, SubClass.RefRange);
 288   return false;
 289 }
 290
 291 bool TGParser::AddSubClass(RecordsEntry &Entry, SubClassReference &SubClass) {
 292   if (Entry.Rec)
 293     return AddSubClass(Entry.Rec.get(), SubClass);
 294
 295   for (auto &E : Entry.Loop->Entries) {
 296     if (AddSubClass(E, SubClass))
 297       return true;
 298   }
 299
 300   return false;
 301 }
 302
 303 /// AddSubMultiClass - Add SubMultiClass as a subclass to
 304 /// CurMC, resolving its template args as SubMultiClass's
 305 /// template arguments.
 306 bool TGParser::AddSubMultiClass(MultiClass *CurMC,
 307                                 SubMultiClassReference &SubMultiClass) {
 308   MultiClass *SMC = SubMultiClass.MC;
 309
 310   ArrayRef<Init *> SMCTArgs = SMC->Rec.getTemplateArgs();
 311   if (SMCTArgs.size() < SubMultiClass.TemplateArgs.size())
 312     return Error(SubMultiClass.RefRange.Start,
 313                  "More template args specified than expected");
 314
 315   // Prepare the mapping of template argument name to value, filling in default
 316   // values if necessary.
 317   SubstStack TemplateArgs;
 318   for (unsigned i = 0, e = SMCTArgs.size(); i != e; ++i) {
 319     if (i < SubMultiClass.TemplateArgs.size()) {
 320       TemplateArgs.emplace_back(SMCTArgs[i], SubMultiClass.TemplateArgs[i]);
 321     } else {
 322       Init *Default = SMC->Rec.getValue(SMCTArgs[i])->getValue();
 323       if (!Default->isComplete()) {
 324         return Error(SubMultiClass.RefRange.Start,
 325                      "value not specified for template argument #" + Twine(i) +
 326                          " (" + SMCTArgs[i]->getAsUnquotedString() +
 327                          ") of multiclass '" + SMC->Rec.getNameInitAsString() +
 328                          "'");
 329       }
 330       TemplateArgs.emplace_back(SMCTArgs[i], Default);
 331     }
 332   }
 333
 334   TemplateArgs.emplace_back(
 335       QualifiedNameOfImplicitName(SMC),
 336       VarInit::get(QualifiedNameOfImplicitName(CurMC), StringRecTy::get()));
 337
 338   // Add all of the defs in the subclass into the current multiclass.
 339   return resolve(SMC->Entries, TemplateArgs, false, &CurMC->Entries);
 340 }
 341
 342 /// Add a record or foreach loop to the current context (global record keeper,
 343 /// current inner-most foreach loop, or multiclass).
 344 bool TGParser::addEntry(RecordsEntry E) {
 345   assert(!E.Rec || !E.Loop);
 346
 347   if (!Loops.empty()) {
 348     Loops.back()->Entries.push_back(std::move(E));
 349     return false;
 350   }
 351
 352   if (E.Loop) {
 353     SubstStack Stack;
 354     return resolve(*E.Loop, Stack, CurMultiClass == nullptr,
 355                    CurMultiClass ? &CurMultiClass->Entries : nullptr);
 356   }
 357
 358   if (CurMultiClass) {
 359     CurMultiClass->Entries.push_back(std::move(E));
 360     return false;
 361   }
 362
 363   return addDefOne(std::move(E.Rec));
 364 }
 365
 366 /// Resolve the entries in \p Loop, going over inner loops recursively
 367 /// and making the given subsitutions of (name, value) pairs.
 368 ///
 369 /// The resulting records are stored in \p Dest if non-null. Otherwise, they
 370 /// are added to the global record keeper.
 371 bool TGParser::resolve(const ForeachLoop &Loop, SubstStack &Substs,
 372                        bool Final, std::vector<RecordsEntry> *Dest,
 373                        SMLoc *Loc) {
 374   MapResolver R;
 375   for (const auto &S : Substs)
 376     R.set(S.first, S.second);
 377   Init *List = Loop.ListValue->resolveReferences(R);
 378   auto LI = dyn_cast<ListInit>(List);
 379   if (!LI) {
 380     if (!Final) {
 381       Dest->emplace_back(std::make_unique<ForeachLoop>(Loop.Loc, Loop.IterVar,
 382                                                   List));
 383       return resolve(Loop.Entries, Substs, Final, &Dest->back().Loop->Entries,
 384                      Loc);
 385     }
 386
 387     PrintError(Loop.Loc, Twine("attempting to loop over '") +
 388                               List->getAsString() + "', expected a list");
 389     return true;
 390   }
 391
 392   bool Error = false;
 393   for (auto Elt : *LI) {
 394     if (Loop.IterVar)
 395       Substs.emplace_back(Loop.IterVar->getNameInit(), Elt);
 396     Error = resolve(Loop.Entries, Substs, Final, Dest);
 397     if (Loop.IterVar)
 398       Substs.pop_back();
 399     if (Error)
 400       break;
 401   }
 402   return Error;
 403 }
 404
 405 /// Resolve the entries in \p Source, going over loops recursively and
 406 /// making the given substitutions of (name, value) pairs.
 407 ///
 408 /// The resulting records are stored in \p Dest if non-null. Otherwise, they
 409 /// are added to the global record keeper.
 410 bool TGParser::resolve(const std::vector<RecordsEntry> &Source,
 411                        SubstStack &Substs, bool Final,
 412                        std::vector<RecordsEntry> *Dest, SMLoc *Loc) {
 413   bool Error = false;
 414   for (auto &E : Source) {
 415     if (E.Loop) {
 416       Error = resolve(*E.Loop, Substs, Final, Dest);
 417     } else {
 418       auto Rec = std::make_unique<Record>(*E.Rec);
 419       if (Loc)
 420         Rec->appendLoc(*Loc);
 421
 422       MapResolver R(Rec.get());
 423       for (const auto &S : Substs)
 424         R.set(S.first, S.second);
 425       Rec->resolveReferences(R);
 426
 427       if (Dest)
 428         Dest->push_back(std::move(Rec));
 429       else
 430         Error = addDefOne(std::move(Rec));
 431     }
 432     if (Error)
 433       break;
 434   }
 435   return Error;
 436 }
 437
 438 /// Resolve the record fully and add it to the record keeper.
 439 bool TGParser::addDefOne(std::unique_ptr<Record> Rec) {
 440   if (Record *Prev = Records.getDef(Rec->getNameInitAsString())) {
 441     if (!Rec->isAnonymous()) {
 442       PrintError(Rec->getLoc(),
 443                  "def already exists: " + Rec->getNameInitAsString());
 444       PrintNote(Prev->getLoc(), "location of previous definition");
 445       return true;
 446     }
 447     Rec->setName(Records.getNewAnonymousName());
 448   }
 449
 450   Rec->resolveReferences();
 451   checkConcrete(*Rec);
 452
 453   if (!isa<StringInit>(Rec->getNameInit())) {
 454     PrintError(Rec->getLoc(), Twine("record name '") +
 455                                   Rec->getNameInit()->getAsString() +
 456                                   "' could not be fully resolved");
 457     return true;
 458   }
 459
 460   // If ObjectBody has template arguments, it's an error.
 461   assert(Rec->getTemplateArgs().empty() && "How'd this get template args?");
 462
 463   for (DefsetRecord *Defset : Defsets) {
 464     DefInit *I = Rec->getDefInit();
 465     if (!I->getType()->typeIsA(Defset->EltTy)) {
 466       PrintError(Rec->getLoc(), Twine("adding record of incompatible type '") +
 467                                     I->getType()->getAsString() +
 468                                      "' to defset");
 469       PrintNote(Defset->Loc, "location of defset declaration");
 470       return true;
 471     }
 472     Defset->Elements.push_back(I);
 473   }
 474
 475   Records.addDef(std::move(Rec));
 476   return false;
 477 }
 478
 479 //===----------------------------------------------------------------------===//
 480 // Parser Code
 481 //===----------------------------------------------------------------------===//
 482
 483 /// isObjectStart - Return true if this is a valid first token for an Object.
 484 static bool isObjectStart(tgtok::TokKind K) {
 485   return K == tgtok::Class || K == tgtok::Def || K == tgtok::Defm ||
 486          K == tgtok::Let || K == tgtok::MultiClass || K == tgtok::Foreach ||
 487          K == tgtok::Defset || K == tgtok::Defvar || K == tgtok::If;
 488 }
 489
 490 /// ParseObjectName - If a valid object name is specified, return it. If no
 491 /// name is specified, return the unset initializer. Return nullptr on parse
 492 /// error.
 493 ///   ObjectName ::= Value [ '#' Value ]*
 494 ///   ObjectName ::= /*empty*/
 495 ///
 496 Init *TGParser::ParseObjectName(MultiClass *CurMultiClass) {
 497   switch (Lex.getCode()) {
 498   case tgtok::colon:
 499   case tgtok::semi:
 500   case tgtok::l_brace:
 501     // These are all of the tokens that can begin an object body.
 502     // Some of these can also begin values but we disallow those cases
 503     // because they are unlikely to be useful.
 504     return UnsetInit::get();
 505   default:
 506     break;
 507   }
 508
 509   Record *CurRec = nullptr;
 510   if (CurMultiClass)
 511     CurRec = &CurMultiClass->Rec;
 512
 513   Init *Name = ParseValue(CurRec, StringRecTy::get(), ParseNameMode);
 514   if (!Name)
 515     return nullptr;
 516
 517   if (CurMultiClass) {
 518     Init *NameStr = QualifiedNameOfImplicitName(CurMultiClass);
 519     HasReferenceResolver R(NameStr);
 520     Name->resolveReferences(R);
 521     if (!R.found())
 522       Name = BinOpInit::getStrConcat(VarInit::get(NameStr, StringRecTy::get()),
 523                                      Name);
 524   }
 525
 526   return Name;
 527 }
 528
 529 /// ParseClassID - Parse and resolve a reference to a class name.  This returns
 530 /// null on error.
 531 ///
 532 ///    ClassID ::= ID
 533 ///
 534 Record *TGParser::ParseClassID() {
 535   if (Lex.getCode() != tgtok::Id) {
 536     TokError("expected name for ClassID");
 537     return nullptr;
 538   }
 539
 540   Record *Result = Records.getClass(Lex.getCurStrVal());
 541   if (!Result) {
 542     std::string Msg("Couldn't find class '" + Lex.getCurStrVal() + "'");
 543     if (MultiClasses[Lex.getCurStrVal()].get())
 544       TokError(Msg + ". Use 'defm' if you meant to use multiclass '" +
 545                Lex.getCurStrVal() + "'");
 546     else
 547       TokError(Msg);
 548   }
 549
 550   Lex.Lex();
 551   return Result;
 552 }
 553
 554 /// ParseMultiClassID - Parse and resolve a reference to a multiclass name.
 555 /// This returns null on error.
 556 ///
 557 ///    MultiClassID ::= ID
 558 ///
 559 MultiClass *TGParser::ParseMultiClassID() {
 560   if (Lex.getCode() != tgtok::Id) {
 561     TokError("expected name for MultiClassID");
 562     return nullptr;
 563   }
 564
 565   MultiClass *Result = MultiClasses[Lex.getCurStrVal()].get();
 566   if (!Result)
 567     TokError("Couldn't find multiclass '" + Lex.getCurStrVal() + "'");
 568
 569   Lex.Lex();
 570   return Result;
 571 }
 572
 573 /// ParseSubClassReference - Parse a reference to a subclass or to a templated
 574 /// subclass.  This returns a SubClassRefTy with a null Record* on error.
 575 ///
 576 ///  SubClassRef ::= ClassID
 577 ///  SubClassRef ::= ClassID '<' ValueList '>'
 578 ///
 579 SubClassReference TGParser::
 580 ParseSubClassReference(Record *CurRec, bool isDefm) {
 581   SubClassReference Result;
 582   Result.RefRange.Start = Lex.getLoc();
 583
 584   if (isDefm) {
 585     if (MultiClass *MC = ParseMultiClassID())
 586       Result.Rec = &MC->Rec;
 587   } else {
 588     Result.Rec = ParseClassID();
 589   }
 590   if (!Result.Rec) return Result;
 591
 592   // If there is no template arg list, we're done.
 593   if (Lex.getCode() != tgtok::less) {
 594     Result.RefRange.End = Lex.getLoc();
 595     return Result;
 596   }
 597   Lex.Lex();  // Eat the '<'
 598
 599   if (Lex.getCode() == tgtok::greater) {
 600     TokError("subclass reference requires a non-empty list of template values");
 601     Result.Rec = nullptr;
 602     return Result;
 603   }
 604
 605   ParseValueList(Result.TemplateArgs, CurRec, Result.Rec);
 606   if (Result.TemplateArgs.empty()) {
 607     Result.Rec = nullptr;   // Error parsing value list.
 608     return Result;
 609   }
 610
 611   if (Lex.getCode() != tgtok::greater) {
 612     TokError("expected '>' in template value list");
 613     Result.Rec = nullptr;
 614     return Result;
 615   }
 616   Lex.Lex();
 617   Result.RefRange.End = Lex.getLoc();
 618
 619   return Result;
 620 }
 621
 622 /// ParseSubMultiClassReference - Parse a reference to a subclass or to a
 623 /// templated submulticlass.  This returns a SubMultiClassRefTy with a null
 624 /// Record* on error.
 625 ///
 626 ///  SubMultiClassRef ::= MultiClassID
 627 ///  SubMultiClassRef ::= MultiClassID '<' ValueList '>'
 628 ///
 629 SubMultiClassReference TGParser::
 630 ParseSubMultiClassReference(MultiClass *CurMC) {
 631   SubMultiClassReference Result;
 632   Result.RefRange.Start = Lex.getLoc();
 633
 634   Result.MC = ParseMultiClassID();
 635   if (!Result.MC) return Result;
 636
 637   // If there is no template arg list, we're done.
 638   if (Lex.getCode() != tgtok::less) {
 639     Result.RefRange.End = Lex.getLoc();
 640     return Result;
 641   }
 642   Lex.Lex();  // Eat the '<'
 643
 644   if (Lex.getCode() == tgtok::greater) {
 645     TokError("subclass reference requires a non-empty list of template values");
 646     Result.MC = nullptr;
 647     return Result;
 648   }
 649
 650   ParseValueList(Result.TemplateArgs, &CurMC->Rec, &Result.MC->Rec);
 651   if (Result.TemplateArgs.empty()) {
 652     Result.MC = nullptr;   // Error parsing value list.
 653     return Result;
 654   }
 655
 656   if (Lex.getCode() != tgtok::greater) {
 657     TokError("expected '>' in template value list");
 658     Result.MC = nullptr;
 659     return Result;
 660   }
 661   Lex.Lex();
 662   Result.RefRange.End = Lex.getLoc();
 663
 664   return Result;
 665 }
 666
 667 /// ParseRangePiece - Parse a bit/value range.
 668 ///   RangePiece ::= INTVAL
 669 ///   RangePiece ::= INTVAL '-' INTVAL
 670 ///   RangePiece ::= INTVAL INTVAL
 671 bool TGParser::ParseRangePiece(SmallVectorImpl<unsigned> &Ranges,
 672                                TypedInit *FirstItem) {
 673   Init *CurVal = FirstItem;
 674   if (!CurVal)
 675     CurVal = ParseValue(nullptr);
 676
 677   IntInit *II = dyn_cast_or_null<IntInit>(CurVal);
 678   if (!II)
 679     return TokError("expected integer or bitrange");
 680
 681   int64_t Start = II->getValue();
 682   int64_t End;
 683
 684   if (Start < 0)
 685     return TokError("invalid range, cannot be negative");
 686
 687   switch (Lex.getCode()) {
 688   default:
 689     Ranges.push_back(Start);
 690     return false;
 691   case tgtok::minus: {
 692     Lex.Lex(); // eat
 693
 694     Init *I_End = ParseValue(nullptr);
 695     IntInit *II_End = dyn_cast_or_null<IntInit>(I_End);
 696     if (!II_End) {
 697       TokError("expected integer value as end of range");
 698       return true;
 699     }
 700
 701     End = II_End->getValue();
 702     break;
 703   }
 704   case tgtok::IntVal: {
 705     End = -Lex.getCurIntVal();
 706     Lex.Lex();
 707     break;
 708   }
 709   }
 710   if (End < 0)
 711     return TokError("invalid range, cannot be negative");
 712
 713   // Add to the range.
 714   if (Start < End)
 715     for (; Start <= End; ++Start)
 716       Ranges.push_back(Start);
 717   else
 718     for (; Start >= End; --Start)
 719       Ranges.push_back(Start);
 720   return false;
 721 }
 722
 723 /// ParseRangeList - Parse a list of scalars and ranges into scalar values.
 724 ///
 725 ///   RangeList ::= RangePiece (',' RangePiece)*
 726 ///
 727 void TGParser::ParseRangeList(SmallVectorImpl<unsigned> &Result) {
 728   // Parse the first piece.
 729   if (ParseRangePiece(Result)) {
 730     Result.clear();
 731     return;
 732   }
 733   while (Lex.getCode() == tgtok::comma) {
 734     Lex.Lex();  // Eat the comma.
 735
 736     // Parse the next range piece.
 737     if (ParseRangePiece(Result)) {
 738       Result.clear();
 739       return;
 740     }
 741   }
 742 }
 743
 744 /// ParseOptionalRangeList - Parse either a range list in <>'s or nothing.
 745 ///   OptionalRangeList ::= '<' RangeList '>'
 746 ///   OptionalRangeList ::= /*empty*/
 747 bool TGParser::ParseOptionalRangeList(SmallVectorImpl<unsigned> &Ranges) {
 748   if (Lex.getCode() != tgtok::less)
 749     return false;
 750
 751   SMLoc StartLoc = Lex.getLoc();
 752   Lex.Lex(); // eat the '<'
 753
 754   // Parse the range list.
 755   ParseRangeList(Ranges);
 756   if (Ranges.empty()) return true;
 757
 758   if (Lex.getCode() != tgtok::greater) {
 759     TokError("expected '>' at end of range list");
 760     return Error(StartLoc, "to match this '<'");
 761   }
 762   Lex.Lex();   // eat the '>'.
 763   return false;
 764 }
 765
 766 /// ParseOptionalBitList - Parse either a bit list in {}'s or nothing.
 767 ///   OptionalBitList ::= '{' RangeList '}'
 768 ///   OptionalBitList ::= /*empty*/
 769 bool TGParser::ParseOptionalBitList(SmallVectorImpl<unsigned> &Ranges) {
 770   if (Lex.getCode() != tgtok::l_brace)
 771     return false;
 772
 773   SMLoc StartLoc = Lex.getLoc();
 774   Lex.Lex(); // eat the '{'
 775
 776   // Parse the range list.
 777   ParseRangeList(Ranges);
 778   if (Ranges.empty()) return true;
 779
 780   if (Lex.getCode() != tgtok::r_brace) {
 781     TokError("expected '}' at end of bit list");
 782     return Error(StartLoc, "to match this '{'");
 783   }
 784   Lex.Lex();   // eat the '}'.
 785   return false;
 786 }
 787
 788 /// ParseType - Parse and return a tblgen type.  This returns null on error.
 789 ///
 790 ///   Type ::= STRING                       // string type
 791 ///   Type ::= CODE                         // code type
 792 ///   Type ::= BIT                          // bit type
 793 ///   Type ::= BITS '<' INTVAL '>'          // bits<x> type
 794 ///   Type ::= INT                          // int type
 795 ///   Type ::= LIST '<' Type '>'            // list<x> type
 796 ///   Type ::= DAG                          // dag type
 797 ///   Type ::= ClassID                      // Record Type
 798 ///
 799 RecTy *TGParser::ParseType() {
 800   switch (Lex.getCode()) {
 801   default: TokError("Unknown token when expecting a type"); return nullptr;
 802   case tgtok::String: Lex.Lex(); return StringRecTy::get();
 803   case tgtok::Code:   Lex.Lex(); return CodeRecTy::get();
 804   case tgtok::Bit:    Lex.Lex(); return BitRecTy::get();
 805   case tgtok::Int:    Lex.Lex(); return IntRecTy::get();
 806   case tgtok::Dag:    Lex.Lex(); return DagRecTy::get();
 807   case tgtok::Id:
 808     if (Record *R = ParseClassID()) return RecordRecTy::get(R);
 809     TokError("unknown class name");
 810     return nullptr;
 811   case tgtok::Bits: {
 812     if (Lex.Lex() != tgtok::less) { // Eat 'bits'
 813       TokError("expected '<' after bits type");
 814       return nullptr;
 815     }
 816     if (Lex.Lex() != tgtok::IntVal) {  // Eat '<'
 817       TokError("expected integer in bits<n> type");
 818       return nullptr;
 819     }
 820     uint64_t Val = Lex.getCurIntVal();
 821     if (Lex.Lex() != tgtok::greater) {  // Eat count.
 822       TokError("expected '>' at end of bits<n> type");
 823       return nullptr;
 824     }
 825     Lex.Lex();  // Eat '>'
 826     return BitsRecTy::get(Val);
 827   }
 828   case tgtok::List: {
 829     if (Lex.Lex() != tgtok::less) { // Eat 'bits'
 830       TokError("expected '<' after list type");
 831       return nullptr;
 832     }
 833     Lex.Lex();  // Eat '<'
 834     RecTy *SubType = ParseType();
 835     if (!SubType) return nullptr;
 836
 837     if (Lex.getCode() != tgtok::greater) {
 838       TokError("expected '>' at end of list<ty> type");
 839       return nullptr;
 840     }
 841     Lex.Lex();  // Eat '>'
 842     return ListRecTy::get(SubType);
 843   }
 844   }
 845 }
 846
 847 /// ParseIDValue - This is just like ParseIDValue above, but it assumes the ID
 848 /// has already been read.
 849 Init *TGParser::ParseIDValue(Record *CurRec, StringInit *Name, SMLoc NameLoc,
 850                              IDParseMode Mode) {
 851   if (CurRec) {
 852     if (const RecordVal *RV = CurRec->getValue(Name))
 853       return VarInit::get(Name, RV->getType());
 854   }
 855
 856   if ((CurRec && CurRec->isClass()) || CurMultiClass) {
 857     Init *TemplateArgName;
 858     if (CurMultiClass) {
 859       TemplateArgName =
 860           QualifyName(CurMultiClass->Rec, CurMultiClass, Name, "::");
 861     } else
 862       TemplateArgName = QualifyName(*CurRec, CurMultiClass, Name, ":");
 863
 864     Record *TemplateRec = CurMultiClass ? &CurMultiClass->Rec : CurRec;
 865     if (TemplateRec->isTemplateArg(TemplateArgName)) {
 866       const RecordVal *RV = TemplateRec->getValue(TemplateArgName);
 867       assert(RV && "Template arg doesn't exist??");
 868       return VarInit::get(TemplateArgName, RV->getType());
 869     } else if (Name->getValue() == "NAME") {
 870       return VarInit::get(TemplateArgName, StringRecTy::get());
 871     }
 872   }
 873
 874   if (CurLocalScope)
 875     if (Init *I = CurLocalScope->getVar(Name->getValue()))
 876       return I;
 877
 878   // If this is in a foreach loop, make sure it's not a loop iterator
 879   for (const auto &L : Loops) {
 880     if (L->IterVar) {
 881       VarInit *IterVar = dyn_cast<VarInit>(L->IterVar);
 882       if (IterVar && IterVar->getNameInit() == Name)
 883         return IterVar;
 884     }
 885   }
 886
 887   if (Mode == ParseNameMode)
 888     return Name;
 889
 890   if (Init *I = Records.getGlobal(Name->getValue()))
 891     return I;
 892
 893   // Allow self-references of concrete defs, but delay the lookup so that we
 894   // get the correct type.
 895   if (CurRec && !CurRec->isClass() && !CurMultiClass &&
 896       CurRec->getNameInit() == Name)
 897     return UnOpInit::get(UnOpInit::CAST, Name, CurRec->getType());
 898
 899   Error(NameLoc, "Variable not defined: '" + Name->getValue() + "'");
 900   return nullptr;
 901 }
 902
 903 /// ParseOperation - Parse an operator.  This returns null on error.
 904 ///
 905 /// Operation ::= XOperator ['<' Type '>'] '(' Args ')'
 906 ///
 907 Init *TGParser::ParseOperation(Record *CurRec, RecTy *ItemType) {
 908   switch (Lex.getCode()) {
 909   default:
 910     TokError("unknown operation");
 911     return nullptr;
 912   case tgtok::XHead:
 913   case tgtok::XTail:
 914   case tgtok::XSize:
 915   case tgtok::XEmpty:
 916   case tgtok::XCast:
 917   case tgtok::XGetOp: {  // Value ::= !unop '(' Value ')'
 918     UnOpInit::UnaryOp Code;
 919     RecTy *Type = nullptr;
 920
 921     switch (Lex.getCode()) {
 922     default: llvm_unreachable("Unhandled code!");
 923     case tgtok::XCast:
 924       Lex.Lex();  // eat the operation
 925       Code = UnOpInit::CAST;
 926
 927       Type = ParseOperatorType();
 928
 929       if (!Type) {
 930         TokError("did not get type for unary operator");
 931         return nullptr;
 932       }
 933
 934       break;
 935     case tgtok::XHead:
 936       Lex.Lex();  // eat the operation
 937       Code = UnOpInit::HEAD;
 938       break;
 939     case tgtok::XTail:
 940       Lex.Lex();  // eat the operation
 941       Code = UnOpInit::TAIL;
 942       break;
 943     case tgtok::XSize:
 944       Lex.Lex();
 945       Code = UnOpInit::SIZE;
 946       Type = IntRecTy::get();
 947       break;
 948     case tgtok::XEmpty:
 949       Lex.Lex();  // eat the operation
 950       Code = UnOpInit::EMPTY;
 951       Type = IntRecTy::get();
 952       break;
 953     case tgtok::XGetOp:
 954       Lex.Lex();  // eat the operation
 955       if (Lex.getCode() == tgtok::less) {
 956         // Parse an optional type suffix, so that you can say
 957         // !getop<BaseClass>(someDag) as a shorthand for
 958         // !cast<BaseClass>(!getop(someDag)).
 959         Type = ParseOperatorType();
 960
 961         if (!Type) {
 962           TokError("did not get type for unary operator");
 963           return nullptr;
 964         }
 965
 966         if (!isa<RecordRecTy>(Type)) {
 967           TokError("type for !getop must be a record type");
 968           // but keep parsing, to consume the operand
 969         }
 970       } else {
 971         Type = RecordRecTy::get({});
 972       }
 973       Code = UnOpInit::GETOP;
 974       break;
 975     }
 976     if (Lex.getCode() != tgtok::l_paren) {
 977       TokError("expected '(' after unary operator");
 978       return nullptr;
 979     }
 980     Lex.Lex();  // eat the '('
 981
 982     Init *LHS = ParseValue(CurRec);
 983     if (!LHS) return nullptr;
 984
 985     if (Code == UnOpInit::HEAD ||
 986         Code == UnOpInit::TAIL ||
 987         Code == UnOpInit::EMPTY) {
 988       ListInit *LHSl = dyn_cast<ListInit>(LHS);
 989       StringInit *LHSs = dyn_cast<StringInit>(LHS);
 990       TypedInit *LHSt = dyn_cast<TypedInit>(LHS);
 991       if (!LHSl && !LHSs && !LHSt) {
 992         TokError("expected list or string type argument in unary operator");
 993         return nullptr;
 994       }
 995       if (LHSt) {
 996         ListRecTy *LType = dyn_cast<ListRecTy>(LHSt->getType());
 997         StringRecTy *SType = dyn_cast<StringRecTy>(LHSt->getType());
 998         if (!LType && !SType) {
 999           TokError("expected list or string type argument in unary operator");
1000           return nullptr;
1001         }
1002       }
1003
1004       if (Code == UnOpInit::HEAD || Code == UnOpInit::TAIL ||
1005           Code == UnOpInit::SIZE) {
1006         if (!LHSl && !LHSt) {
1007           TokError("expected list type argument in unary operator");
1008           return nullptr;
1009         }
1010       }
1011
1012       if (Code == UnOpInit::HEAD || Code == UnOpInit::TAIL) {
1013         if (LHSl && LHSl->empty()) {
1014           TokError("empty list argument in unary operator");
1015           return nullptr;
1016         }
1017         if (LHSl) {
1018           Init *Item = LHSl->getElement(0);
1019           TypedInit *Itemt = dyn_cast<TypedInit>(Item);
1020           if (!Itemt) {
1021             TokError("untyped list element in unary operator");
1022             return nullptr;
1023           }
1024           Type = (Code == UnOpInit::HEAD) ? Itemt->getType()
1025                                           : ListRecTy::get(Itemt->getType());
1026         } else {
1027           assert(LHSt && "expected list type argument in unary operator");
1028           ListRecTy *LType = dyn_cast<ListRecTy>(LHSt->getType());
1029           if (!LType) {
1030             TokError("expected list type argument in unary operator");
1031             return nullptr;
1032           }
1033           Type = (Code == UnOpInit::HEAD) ? LType->getElementType() : LType;
1034         }
1035       }
1036     }
1037
1038     if (Lex.getCode() != tgtok::r_paren) {
1039       TokError("expected ')' in unary operator");
1040       return nullptr;
1041     }
1042     Lex.Lex();  // eat the ')'
1043     return (UnOpInit::get(Code, LHS, Type))->Fold(CurRec);
1044   }
1045
1046   case tgtok::XIsA: {
1047     // Value ::= !isa '<' Type '>' '(' Value ')'
1048     Lex.Lex(); // eat the operation
1049
1050     RecTy *Type = ParseOperatorType();
1051     if (!Type)
1052       return nullptr;
1053
1054     if (Lex.getCode() != tgtok::l_paren) {
1055       TokError("expected '(' after type of !isa");
1056       return nullptr;
1057     }
1058     Lex.Lex(); // eat the '('
1059
1060     Init *LHS = ParseValue(CurRec);
1061     if (!LHS)
1062       return nullptr;
1063
1064     if (Lex.getCode() != tgtok::r_paren) {
1065       TokError("expected ')' in !isa");
1066       return nullptr;
1067     }
1068     Lex.Lex(); // eat the ')'
1069
1070     return (IsAOpInit::get(Type, LHS))->Fold();
1071   }
1072
1073   case tgtok::XConcat:
1074   case tgtok::XADD:
1075   case tgtok::XMUL:
1076   case tgtok::XAND:
1077   case tgtok::XOR:
1078   case tgtok::XSRA:
1079   case tgtok::XSRL:
1080   case tgtok::XSHL:
1081   case tgtok::XEq:
1082   case tgtok::XNe:
1083   case tgtok::XLe:
1084   case tgtok::XLt:
1085   case tgtok::XGe:
1086   case tgtok::XGt:
1087   case tgtok::XListConcat:
1088   case tgtok::XListSplat:
1089   case tgtok::XStrConcat:
1090   case tgtok::XSetOp: {  // Value ::= !binop '(' Value ',' Value ')'
1091     tgtok::TokKind OpTok = Lex.getCode();
1092     SMLoc OpLoc = Lex.getLoc();
1093     Lex.Lex();  // eat the operation
1094
1095     BinOpInit::BinaryOp Code;
1096     switch (OpTok) {
1097     default: llvm_unreachable("Unhandled code!");
1098     case tgtok::XConcat: Code = BinOpInit::CONCAT; break;
1099     case tgtok::XADD:    Code = BinOpInit::ADD; break;
1100     case tgtok::XMUL:    Code = BinOpInit::MUL; break;
1101     case tgtok::XAND:    Code = BinOpInit::AND; break;
1102     case tgtok::XOR:     Code = BinOpInit::OR; break;
1103     case tgtok::XSRA:    Code = BinOpInit::SRA; break;
1104     case tgtok::XSRL:    Code = BinOpInit::SRL; break;
1105     case tgtok::XSHL:    Code = BinOpInit::SHL; break;
1106     case tgtok::XEq:     Code = BinOpInit::EQ; break;
1107     case tgtok::XNe:     Code = BinOpInit::NE; break;
1108     case tgtok::XLe:     Code = BinOpInit::LE; break;
1109     case tgtok::XLt:     Code = BinOpInit::LT; break;
1110     case tgtok::XGe:     Code = BinOpInit::GE; break;
1111     case tgtok::XGt:     Code = BinOpInit::GT; break;
1112     case tgtok::XListConcat: Code = BinOpInit::LISTCONCAT; break;
1113     case tgtok::XListSplat: Code = BinOpInit::LISTSPLAT; break;
1114     case tgtok::XStrConcat: Code = BinOpInit::STRCONCAT; break;
1115     case tgtok::XSetOp: Code = BinOpInit::SETOP; break;
1116     }
1117
1118     RecTy *Type = nullptr;
1119     RecTy *ArgType = nullptr;
1120     switch (OpTok) {
1121     default:
1122       llvm_unreachable("Unhandled code!");
1123     case tgtok::XConcat:
1124     case tgtok::XSetOp:
1125       Type = DagRecTy::get();
1126       ArgType = DagRecTy::get();
1127       break;
1128     case tgtok::XAND:
1129     case tgtok::XOR:
1130     case tgtok::XSRA:
1131     case tgtok::XSRL:
1132     case tgtok::XSHL:
1133     case tgtok::XADD:
1134     case tgtok::XMUL:
1135       Type = IntRecTy::get();
1136       ArgType = IntRecTy::get();
1137       break;
1138     case tgtok::XEq:
1139     case tgtok::XNe:
1140       Type = BitRecTy::get();
1141       // ArgType for Eq / Ne is not known at this point
1142       break;
1143     case tgtok::XLe:
1144     case tgtok::XLt:
1145     case tgtok::XGe:
1146     case tgtok::XGt:
1147       Type = BitRecTy::get();
1148       ArgType = IntRecTy::get();
1149       break;
1150     case tgtok::XListConcat:
1151       // We don't know the list type until we parse the first argument
1152       ArgType = ItemType;
1153       break;
1154     case tgtok::XListSplat:
1155       // Can't do any typechecking until we parse the first argument.
1156       break;
1157     case tgtok::XStrConcat:
1158       Type = StringRecTy::get();
1159       ArgType = StringRecTy::get();
1160       break;
1161     }
1162
1163     if (Type && ItemType && !Type->typeIsConvertibleTo(ItemType)) {
1164       Error(OpLoc, Twine("expected value of type '") +
1165                    ItemType->getAsString() + "', got '" +
1166                    Type->getAsString() + "'");
1167       return nullptr;
1168     }
1169
1170     if (Lex.getCode() != tgtok::l_paren) {
1171       TokError("expected '(' after binary operator");
1172       return nullptr;
1173     }
1174     Lex.Lex();  // eat the '('
1175
1176     SmallVector<Init*, 2> InitList;
1177
1178     for (;;) {
1179       SMLoc InitLoc = Lex.getLoc();
1180       InitList.push_back(ParseValue(CurRec, ArgType));
1181       if (!InitList.back()) return nullptr;
1182
1183       RecTy *ListType = cast<TypedInit>(InitList.back())->getType();
1184       if (!ArgType) {
1185         ArgType = ListType;
1186
1187         switch (Code) {
1188         case BinOpInit::LISTCONCAT:
1189           if (!isa<ListRecTy>(ArgType)) {
1190             Error(InitLoc, Twine("expected a list, got value of type '") +
1191                            ArgType->getAsString() + "'");
1192             return nullptr;
1193           }
1194           break;
1195         case BinOpInit::LISTSPLAT:
1196           if (ItemType && InitList.size() == 1) {
1197             if (!isa<ListRecTy>(ItemType)) {
1198               Error(OpLoc,
1199                     Twine("expected output type to be a list, got type '") +
1200                         ItemType->getAsString() + "'");
1201               return nullptr;
1202             }
1203             if (!ArgType->getListTy()->typeIsConvertibleTo(ItemType)) {
1204               Error(OpLoc, Twine("expected first arg type to be '") +
1205                                ArgType->getAsString() +
1206                                "', got value of type '" +
1207                                cast<ListRecTy>(ItemType)
1208                                    ->getElementType()
1209                                    ->getAsString() +
1210                                "'");
1211               return nullptr;
1212             }
1213           }
1214           if (InitList.size() == 2 && !isa<IntRecTy>(ArgType)) {
1215             Error(InitLoc, Twine("expected second parameter to be an int, got "
1216                                  "value of type '") +
1217                                ArgType->getAsString() + "'");
1218             return nullptr;
1219           }
1220           ArgType = nullptr; // Broken invariant: types not identical.
1221           break;
1222         case BinOpInit::EQ:
1223         case BinOpInit::NE:
1224           if (!ArgType->typeIsConvertibleTo(IntRecTy::get()) &&
1225               !ArgType->typeIsConvertibleTo(StringRecTy::get())) {
1226             Error(InitLoc, Twine("expected int, bits, or string; got value of "
1227                                  "type '") + ArgType->getAsString() + "'");
1228             return nullptr;
1229           }
1230           break;
1231         default: llvm_unreachable("other ops have fixed argument types");
1232         }
1233       } else {
1234         RecTy *Resolved = resolveTypes(ArgType, ListType);
1235         if (!Resolved) {
1236           Error(InitLoc, Twine("expected value of type '") +
1237                              ArgType->getAsString() + "', got '" +
1238                              ListType->getAsString() + "'");
1239           return nullptr;
1240         }
1241         if (Code != BinOpInit::ADD && Code != BinOpInit::AND &&
1242             Code != BinOpInit::OR && Code != BinOpInit::SRA &&
1243             Code != BinOpInit::SRL && Code != BinOpInit::SHL &&
1244             Code != BinOpInit::MUL)
1245           ArgType = Resolved;
1246       }
1247
1248       // Deal with BinOps whose arguments have different types, by
1249       // rewriting ArgType in between them.
1250       switch (Code) {
1251         case BinOpInit::SETOP:
1252           // After parsing the first dag argument, switch to expecting
1253           // a record, with no restriction on its superclasses.
1254           ArgType = RecordRecTy::get({});
1255           break;
1256         default:
1257           break;
1258       }
1259
1260       if (Lex.getCode() != tgtok::comma)
1261         break;
1262       Lex.Lex();  // eat the ','
1263     }
1264
1265     if (Lex.getCode() != tgtok::r_paren) {
1266       TokError("expected ')' in operator");
1267       return nullptr;
1268     }
1269     Lex.Lex();  // eat the ')'
1270
1271     // listconcat returns a list with type of the argument.
1272     if (Code == BinOpInit::LISTCONCAT)
1273       Type = ArgType;
1274     // listsplat returns a list of type of the *first* argument.
1275     if (Code == BinOpInit::LISTSPLAT)
1276       Type = cast<TypedInit>(InitList.front())->getType()->getListTy();
1277
1278     // We allow multiple operands to associative operators like !strconcat as
1279     // shorthand for nesting them.
1280     if (Code == BinOpInit::STRCONCAT || Code == BinOpInit::LISTCONCAT ||
1281         Code == BinOpInit::CONCAT || Code == BinOpInit::ADD ||
1282         Code == BinOpInit::AND || Code == BinOpInit::OR ||
1283         Code == BinOpInit::MUL) {
1284       while (InitList.size() > 2) {
1285         Init *RHS = InitList.pop_back_val();
1286         RHS = (BinOpInit::get(Code, InitList.back(), RHS, Type))->Fold(CurRec);
1287         InitList.back() = RHS;
1288       }
1289     }
1290
1291     if (InitList.size() == 2)
1292       return (BinOpInit::get(Code, InitList[0], InitList[1], Type))
1293           ->Fold(CurRec);
1294
1295     Error(OpLoc, "expected two operands to operator");
1296     return nullptr;
1297   }
1298
1299   case tgtok::XForEach: { // Value ::= !foreach '(' Id ',' Value ',' Value ')'
1300     SMLoc OpLoc = Lex.getLoc();
1301     Lex.Lex(); // eat the operation
1302     if (Lex.getCode() != tgtok::l_paren) {
1303       TokError("expected '(' after !foreach");
1304       return nullptr;
1305     }
1306
1307     if (Lex.Lex() != tgtok::Id) { // eat the '('
1308       TokError("first argument of !foreach must be an identifier");
1309       return nullptr;
1310     }
1311
1312     Init *LHS = StringInit::get(Lex.getCurStrVal());
1313
1314     if (CurRec && CurRec->getValue(LHS)) {
1315       TokError((Twine("iteration variable '") + LHS->getAsString() +
1316                 "' already defined")
1317                    .str());
1318       return nullptr;
1319     }
1320
1321     if (Lex.Lex() != tgtok::comma) { // eat the id
1322       TokError("expected ',' in ternary operator");
1323       return nullptr;
1324     }
1325     Lex.Lex();  // eat the ','
1326
1327     Init *MHS = ParseValue(CurRec);
1328     if (!MHS)
1329       return nullptr;
1330
1331     if (Lex.getCode() != tgtok::comma) {
1332       TokError("expected ',' in ternary operator");
1333       return nullptr;
1334     }
1335     Lex.Lex();  // eat the ','
1336
1337     TypedInit *MHSt = dyn_cast<TypedInit>(MHS);
1338     if (!MHSt) {
1339       TokError("could not get type of !foreach input");
1340       return nullptr;
1341     }
1342
1343     RecTy *InEltType = nullptr;
1344     RecTy *OutEltType = nullptr;
1345     bool IsDAG = false;
1346
1347     if (ListRecTy *InListTy = dyn_cast<ListRecTy>(MHSt->getType())) {
1348       InEltType = InListTy->getElementType();
1349       if (ItemType) {
1350         if (ListRecTy *OutListTy = dyn_cast<ListRecTy>(ItemType)) {
1351           OutEltType = OutListTy->getElementType();
1352         } else {
1353           Error(OpLoc,
1354                 "expected value of type '" + Twine(ItemType->getAsString()) +
1355                 "', but got !foreach of list type");
1356           return nullptr;
1357         }
1358       }
1359     } else if (DagRecTy *InDagTy = dyn_cast<DagRecTy>(MHSt->getType())) {
1360       InEltType = InDagTy;
1361       if (ItemType && !isa<DagRecTy>(ItemType)) {
1362         Error(OpLoc,
1363               "expected value of type '" + Twine(ItemType->getAsString()) +
1364               "', but got !foreach of dag type");
1365         return nullptr;
1366       }
1367       IsDAG = true;
1368     } else {
1369       TokError("!foreach must have list or dag input");
1370       return nullptr;
1371     }
1372
1373     // We need to create a temporary record to provide a scope for the iteration
1374     // variable while parsing top-level foreach's.
1375     std::unique_ptr<Record> ParseRecTmp;
1376     Record *ParseRec = CurRec;
1377     if (!ParseRec) {
1378       ParseRecTmp = std::make_unique<Record>(".parse", ArrayRef<SMLoc>{}, Records);
1379       ParseRec = ParseRecTmp.get();
1380     }
1381
1382     ParseRec->addValue(RecordVal(LHS, InEltType, false));
1383     Init *RHS = ParseValue(ParseRec, OutEltType);
1384     ParseRec->removeValue(LHS);
1385     if (!RHS)
1386       return nullptr;
1387
1388     if (Lex.getCode() != tgtok::r_paren) {
1389       TokError("expected ')' in binary operator");
1390       return nullptr;
1391     }
1392     Lex.Lex();  // eat the ')'
1393
1394     RecTy *OutType;
1395     if (IsDAG) {
1396       OutType = InEltType;
1397     } else {
1398       TypedInit *RHSt = dyn_cast<TypedInit>(RHS);
1399       if (!RHSt) {
1400         TokError("could not get type of !foreach result");
1401         return nullptr;
1402       }
1403       OutType = RHSt->getType()->getListTy();
1404     }
1405
1406     return (TernOpInit::get(TernOpInit::FOREACH, LHS, MHS, RHS, OutType))
1407         ->Fold(CurRec);
1408   }
1409
1410   case tgtok::XDag:
1411   case tgtok::XIf:
1412   case tgtok::XSubst: {  // Value ::= !ternop '(' Value ',' Value ',' Value ')'
1413     TernOpInit::TernaryOp Code;
1414     RecTy *Type = nullptr;
1415
1416     tgtok::TokKind LexCode = Lex.getCode();
1417     Lex.Lex();  // eat the operation
1418     switch (LexCode) {
1419     default: llvm_unreachable("Unhandled code!");
1420     case tgtok::XDag:
1421       Code = TernOpInit::DAG;
1422       Type = DagRecTy::get();
1423       ItemType = nullptr;
1424       break;
1425     case tgtok::XIf:
1426       Code = TernOpInit::IF;
1427       break;
1428     case tgtok::XSubst:
1429       Code = TernOpInit::SUBST;
1430       break;
1431     }
1432     if (Lex.getCode() != tgtok::l_paren) {
1433       TokError("expected '(' after ternary operator");
1434       return nullptr;
1435     }
1436     Lex.Lex();  // eat the '('
1437
1438     Init *LHS = ParseValue(CurRec);
1439     if (!LHS) return nullptr;
1440
1441     if (Lex.getCode() != tgtok::comma) {
1442       TokError("expected ',' in ternary operator");
1443       return nullptr;
1444     }
1445     Lex.Lex();  // eat the ','
1446
1447     SMLoc MHSLoc = Lex.getLoc();
1448     Init *MHS = ParseValue(CurRec, ItemType);
1449     if (!MHS)
1450       return nullptr;
1451
1452     if (Lex.getCode() != tgtok::comma) {
1453       TokError("expected ',' in ternary operator");
1454       return nullptr;
1455     }
1456     Lex.Lex();  // eat the ','
1457
1458     SMLoc RHSLoc = Lex.getLoc();
1459     Init *RHS = ParseValue(CurRec, ItemType);
1460     if (!RHS)
1461       return nullptr;
1462
1463     if (Lex.getCode() != tgtok::r_paren) {
1464       TokError("expected ')' in binary operator");
1465       return nullptr;
1466     }
1467     Lex.Lex();  // eat the ')'
1468
1469     switch (LexCode) {
1470     default: llvm_unreachable("Unhandled code!");
1471     case tgtok::XDag: {
1472       TypedInit *MHSt = dyn_cast<TypedInit>(MHS);
1473       if (!MHSt && !isa<UnsetInit>(MHS)) {
1474         Error(MHSLoc, "could not determine type of the child list in !dag");
1475         return nullptr;
1476       }
1477       if (MHSt && !isa<ListRecTy>(MHSt->getType())) {
1478         Error(MHSLoc, Twine("expected list of children, got type '") +
1479                           MHSt->getType()->getAsString() + "'");
1480         return nullptr;
1481       }
1482
1483       TypedInit *RHSt = dyn_cast<TypedInit>(RHS);
1484       if (!RHSt && !isa<UnsetInit>(RHS)) {
1485         Error(RHSLoc, "could not determine type of the name list in !dag");
1486         return nullptr;
1487       }
1488       if (RHSt && StringRecTy::get()->getListTy() != RHSt->getType()) {
1489         Error(RHSLoc, Twine("expected list<string>, got type '") +
1490                           RHSt->getType()->getAsString() + "'");
1491         return nullptr;
1492       }
1493
1494       if (!MHSt && !RHSt) {
1495         Error(MHSLoc,
1496               "cannot have both unset children and unset names in !dag");
1497         return nullptr;
1498       }
1499       break;
1500     }
1501     case tgtok::XIf: {
1502       RecTy *MHSTy = nullptr;
1503       RecTy *RHSTy = nullptr;
1504
1505       if (TypedInit *MHSt = dyn_cast<TypedInit>(MHS))
1506         MHSTy = MHSt->getType();
1507       if (BitsInit *MHSbits = dyn_cast<BitsInit>(MHS))
1508         MHSTy = BitsRecTy::get(MHSbits->getNumBits());
1509       if (isa<BitInit>(MHS))
1510         MHSTy = BitRecTy::get();
1511
1512       if (TypedInit *RHSt = dyn_cast<TypedInit>(RHS))
1513         RHSTy = RHSt->getType();
1514       if (BitsInit *RHSbits = dyn_cast<BitsInit>(RHS))
1515         RHSTy = BitsRecTy::get(RHSbits->getNumBits());
1516       if (isa<BitInit>(RHS))
1517         RHSTy = BitRecTy::get();
1518
1519       // For UnsetInit, it's typed from the other hand.
1520       if (isa<UnsetInit>(MHS))
1521         MHSTy = RHSTy;
1522       if (isa<UnsetInit>(RHS))
1523         RHSTy = MHSTy;
1524
1525       if (!MHSTy || !RHSTy) {
1526         TokError("could not get type for !if");
1527         return nullptr;
1528       }
1529
1530       Type = resolveTypes(MHSTy, RHSTy);
1531       if (!Type) {
1532         TokError(Twine("inconsistent types '") + MHSTy->getAsString() +
1533                  "' and '" + RHSTy->getAsString() + "' for !if");
1534         return nullptr;
1535       }
1536       break;
1537     }
1538     case tgtok::XSubst: {
1539       TypedInit *RHSt = dyn_cast<TypedInit>(RHS);
1540       if (!RHSt) {
1541         TokError("could not get type for !subst");
1542         return nullptr;
1543       }
1544       Type = RHSt->getType();
1545       break;
1546     }
1547     }
1548     return (TernOpInit::get(Code, LHS, MHS, RHS, Type))->Fold(CurRec);
1549   }
1550
1551   case tgtok::XCond:
1552     return ParseOperationCond(CurRec, ItemType);
1553
1554   case tgtok::XFoldl: {
1555     // Value ::= !foldl '(' Id ',' Id ',' Value ',' Value ',' Value ')'
1556     Lex.Lex(); // eat the operation
1557     if (Lex.getCode() != tgtok::l_paren) {
1558       TokError("expected '(' after !foldl");
1559       return nullptr;
1560     }
1561     Lex.Lex(); // eat the '('
1562
1563     Init *StartUntyped = ParseValue(CurRec);
1564     if (!StartUntyped)
1565       return nullptr;
1566
1567     TypedInit *Start = dyn_cast<TypedInit>(StartUntyped);
1568     if (!Start) {
1569       TokError(Twine("could not get type of !foldl start: '") +
1570                StartUntyped->getAsString() + "'");
1571       return nullptr;
1572     }
1573
1574     if (Lex.getCode() != tgtok::comma) {
1575       TokError("expected ',' in !foldl");
1576       return nullptr;
1577     }
1578     Lex.Lex(); // eat the ','
1579
1580     Init *ListUntyped = ParseValue(CurRec);
1581     if (!ListUntyped)
1582       return nullptr;
1583
1584     TypedInit *List = dyn_cast<TypedInit>(ListUntyped);
1585     if (!List) {
1586       TokError(Twine("could not get type of !foldl list: '") +
1587                ListUntyped->getAsString() + "'");
1588       return nullptr;
1589     }
1590
1591     ListRecTy *ListType = dyn_cast<ListRecTy>(List->getType());
1592     if (!ListType) {
1593       TokError(Twine("!foldl list must be a list, but is of type '") +
1594                List->getType()->getAsString());
1595       return nullptr;
1596     }
1597
1598     if (Lex.getCode() != tgtok::comma) {
1599       TokError("expected ',' in !foldl");
1600       return nullptr;
1601     }
1602
1603     if (Lex.Lex() != tgtok::Id) { // eat the ','
1604       TokError("third argument of !foldl must be an identifier");
1605       return nullptr;
1606     }
1607
1608     Init *A = StringInit::get(Lex.getCurStrVal());
1609     if (CurRec && CurRec->getValue(A)) {
1610       TokError((Twine("left !foldl variable '") + A->getAsString() +
1611                 "' already defined")
1612                    .str());
1613       return nullptr;
1614     }
1615
1616     if (Lex.Lex() != tgtok::comma) { // eat the id
1617       TokError("expected ',' in !foldl");
1618       return nullptr;
1619     }
1620
1621     if (Lex.Lex() != tgtok::Id) { // eat the ','
1622       TokError("fourth argument of !foldl must be an identifier");
1623       return nullptr;
1624     }
1625
1626     Init *B = StringInit::get(Lex.getCurStrVal());
1627     if (CurRec && CurRec->getValue(B)) {
1628       TokError((Twine("right !foldl variable '") + B->getAsString() +
1629                 "' already defined")
1630                    .str());
1631       return nullptr;
1632     }
1633
1634     if (Lex.Lex() != tgtok::comma) { // eat the id
1635       TokError("expected ',' in !foldl");
1636       return nullptr;
1637     }
1638     Lex.Lex(); // eat the ','
1639
1640     // We need to create a temporary record to provide a scope for the iteration
1641     // variable while parsing top-level foreach's.
1642     std::unique_ptr<Record> ParseRecTmp;
1643     Record *ParseRec = CurRec;
1644     if (!ParseRec) {
1645       ParseRecTmp = std::make_unique<Record>(".parse", ArrayRef<SMLoc>{}, Records);
1646       ParseRec = ParseRecTmp.get();
1647     }
1648
1649     ParseRec->addValue(RecordVal(A, Start->getType(), false));
1650     ParseRec->addValue(RecordVal(B, ListType->getElementType(), false));
1651     Init *ExprUntyped = ParseValue(ParseRec);
1652     ParseRec->removeValue(A);
1653     ParseRec->removeValue(B);
1654     if (!ExprUntyped)
1655       return nullptr;
1656
1657     TypedInit *Expr = dyn_cast<TypedInit>(ExprUntyped);
1658     if (!Expr) {
1659       TokError("could not get type of !foldl expression");
1660       return nullptr;
1661     }
1662
1663     if (Expr->getType() != Start->getType()) {
1664       TokError(Twine("!foldl expression must be of same type as start (") +
1665                Start->getType()->getAsString() + "), but is of type " +
1666                Expr->getType()->getAsString());
1667       return nullptr;
1668     }
1669
1670     if (Lex.getCode() != tgtok::r_paren) {
1671       TokError("expected ')' in fold operator");
1672       return nullptr;
1673     }
1674     Lex.Lex(); // eat the ')'
1675
1676     return FoldOpInit::get(Start, List, A, B, Expr, Start->getType())
1677         ->Fold(CurRec);
1678   }
1679   }
1680 }
1681
1682 /// ParseOperatorType - Parse a type for an operator.  This returns
1683 /// null on error.
1684 ///
1685 /// OperatorType ::= '<' Type '>'
1686 ///
1687 RecTy *TGParser::ParseOperatorType() {
1688   RecTy *Type = nullptr;
1689
1690   if (Lex.getCode() != tgtok::less) {
1691     TokError("expected type name for operator");
1692     return nullptr;
1693   }
1694   Lex.Lex();  // eat the <
1695
1696   Type = ParseType();
1697
1698   if (!Type) {
1699     TokError("expected type name for operator");
1700     return nullptr;
1701   }
1702
1703   if (Lex.getCode() != tgtok::greater) {
1704     TokError("expected type name for operator");
1705     return nullptr;
1706   }
1707   Lex.Lex();  // eat the >
1708
1709   return Type;
1710 }
1711
1712 Init *TGParser::ParseOperationCond(Record *CurRec, RecTy *ItemType) {
1713   Lex.Lex();  // eat the operation 'cond'
1714
1715   if (Lex.getCode() != tgtok::l_paren) {
1716      TokError("expected '(' after !cond operator");
1717      return nullptr;
1718   }
1719   Lex.Lex();  // eat the '('
1720
1721   // Parse through '[Case: Val,]+'
1722   SmallVector<Init *, 4> Case;
1723   SmallVector<Init *, 4> Val;
1724   while (true) {
1725     if (Lex.getCode() == tgtok::r_paren) {
1726       Lex.Lex(); // eat the ')'
1727       break;
1728     }
1729
1730     Init *V = ParseValue(CurRec);
1731     if (!V)
1732       return nullptr;
1733     Case.push_back(V);
1734
1735     if (Lex.getCode() != tgtok::colon) {
1736       TokError("expected ':'  following a condition in !cond operator");
1737       return nullptr;
1738     }
1739     Lex.Lex(); // eat the ':'
1740
1741     V = ParseValue(CurRec, ItemType);
1742     if (!V)
1743       return nullptr;
1744     Val.push_back(V);
1745
1746     if (Lex.getCode() == tgtok::r_paren) {
1747       Lex.Lex(); // eat the ')'
1748       break;
1749     }
1750
1751     if (Lex.getCode() != tgtok::comma) {
1752       TokError("expected ',' or ')' following a value in !cond operator");
1753       return nullptr;
1754     }
1755     Lex.Lex();  // eat the ','
1756   }
1757
1758   if (Case.size() < 1) {
1759     TokError("there should be at least 1 'condition : value' in the !cond operator");
1760     return nullptr;
1761   }
1762
1763   // resolve type
1764   RecTy *Type = nullptr;
1765   for (Init *V : Val) {
1766     RecTy *VTy = nullptr;
1767     if (TypedInit *Vt = dyn_cast<TypedInit>(V))
1768       VTy = Vt->getType();
1769     if (BitsInit *Vbits = dyn_cast<BitsInit>(V))
1770       VTy = BitsRecTy::get(Vbits->getNumBits());
1771     if (isa<BitInit>(V))
1772       VTy = BitRecTy::get();
1773
1774     if (Type == nullptr) {
1775       if (!isa<UnsetInit>(V))
1776         Type = VTy;
1777     } else {
1778       if (!isa<UnsetInit>(V)) {
1779         RecTy *RType = resolveTypes(Type, VTy);
1780         if (!RType) {
1781           TokError(Twine("inconsistent types '") + Type->getAsString() +
1782                          "' and '" + VTy->getAsString() + "' for !cond");
1783           return nullptr;
1784         }
1785         Type = RType;
1786       }
1787     }
1788   }
1789
1790   if (!Type) {
1791     TokError("could not determine type for !cond from its arguments");
1792     return nullptr;
1793   }
1794   return CondOpInit::get(Case, Val, Type)->Fold(CurRec);
1795 }
1796
1797 /// ParseSimpleValue - Parse a tblgen value.  This returns null on error.
1798 ///
1799 ///   SimpleValue ::= IDValue
1800 ///   SimpleValue ::= INTVAL
1801 ///   SimpleValue ::= STRVAL+
1802 ///   SimpleValue ::= CODEFRAGMENT
1803 ///   SimpleValue ::= '?'
1804 ///   SimpleValue ::= '{' ValueList '}'
1805 ///   SimpleValue ::= ID '<' ValueListNE '>'
1806 ///   SimpleValue ::= '[' ValueList ']'
1807 ///   SimpleValue ::= '(' IDValue DagArgList ')'
1808 ///   SimpleValue ::= CONCATTOK '(' Value ',' Value ')'
1809 ///   SimpleValue ::= ADDTOK '(' Value ',' Value ')'
1810 ///   SimpleValue ::= SHLTOK '(' Value ',' Value ')'
1811 ///   SimpleValue ::= SRATOK '(' Value ',' Value ')'
1812 ///   SimpleValue ::= SRLTOK '(' Value ',' Value ')'
1813 ///   SimpleValue ::= LISTCONCATTOK '(' Value ',' Value ')'
1814 ///   SimpleValue ::= LISTSPLATTOK '(' Value ',' Value ')'
1815 ///   SimpleValue ::= STRCONCATTOK '(' Value ',' Value ')'
1816 ///   SimpleValue ::= COND '(' [Value ':' Value,]+ ')'
1817 ///
1818 Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType,
1819                                  IDParseMode Mode) {
1820   Init *R = nullptr;
1821   switch (Lex.getCode()) {
1822   default: TokError("Unknown token when parsing a value"); break;
1823   case tgtok::paste:
1824     // This is a leading paste operation.  This is deprecated but
1825     // still exists in some .td files.  Ignore it.
1826     Lex.Lex();  // Skip '#'.
1827     return ParseSimpleValue(CurRec, ItemType, Mode);
1828   case tgtok::IntVal: R = IntInit::get(Lex.getCurIntVal()); Lex.Lex(); break;
1829   case tgtok::BinaryIntVal: {
1830     auto BinaryVal = Lex.getCurBinaryIntVal();
1831     SmallVector<Init*, 16> Bits(BinaryVal.second);
1832     for (unsigned i = 0, e = BinaryVal.second; i != e; ++i)
1833       Bits[i] = BitInit::get(BinaryVal.first & (1LL << i));
1834     R = BitsInit::get(Bits);
1835     Lex.Lex();
1836     break;
1837   }
1838   case tgtok::StrVal: {
1839     std::string Val = Lex.getCurStrVal();
1840     Lex.Lex();
1841
1842     // Handle multiple consecutive concatenated strings.
1843     while (Lex.getCode() == tgtok::StrVal) {
1844       Val += Lex.getCurStrVal();
1845       Lex.Lex();
1846     }
1847
1848     R = StringInit::get(Val);
1849     break;
1850   }
1851   case tgtok::CodeFragment:
1852     R = CodeInit::get(Lex.getCurStrVal(), Lex.getLoc());
1853     Lex.Lex();
1854     break;
1855   case tgtok::question:
1856     R = UnsetInit::get();
1857     Lex.Lex();
1858     break;
1859   case tgtok::Id: {
1860     SMLoc NameLoc = Lex.getLoc();
1861     StringInit *Name = StringInit::get(Lex.getCurStrVal());
1862     if (Lex.Lex() != tgtok::less)  // consume the Id.
1863       return ParseIDValue(CurRec, Name, NameLoc, Mode);    // Value ::= IDValue
1864
1865     // Value ::= ID '<' ValueListNE '>'
1866     if (Lex.Lex() == tgtok::greater) {
1867       TokError("expected non-empty value list");
1868       return nullptr;
1869     }
1870
1871     // This is a CLASS<initvalslist> expression.  This is supposed to synthesize
1872     // a new anonymous definition, deriving from CLASS<initvalslist> with no
1873     // body.
1874     Record *Class = Records.getClass(Name->getValue());
1875     if (!Class) {
1876       Error(NameLoc, "Expected a class name, got '" + Name->getValue() + "'");
1877       return nullptr;
1878     }
1879
1880     SmallVector<Init *, 8> Args;
1881     ParseValueList(Args, CurRec, Class);
1882     if (Args.empty()) return nullptr;
1883
1884     if (Lex.getCode() != tgtok::greater) {
1885       TokError("expected '>' at end of value list");
1886       return nullptr;
1887     }
1888     Lex.Lex();  // eat the '>'
1889
1890     // Typecheck the template arguments list
1891     ArrayRef<Init *> ExpectedArgs = Class->getTemplateArgs();
1892     if (ExpectedArgs.size() < Args.size()) {
1893       Error(NameLoc,
1894             "More template args specified than expected");
1895       return nullptr;
1896     }
1897
1898     for (unsigned i = 0, e = ExpectedArgs.size(); i != e; ++i) {
1899       RecordVal *ExpectedArg = Class->getValue(ExpectedArgs[i]);
1900       if (i < Args.size()) {
1901         if (TypedInit *TI = dyn_cast<TypedInit>(Args[i])) {
1902           RecTy *ExpectedType = ExpectedArg->getType();
1903           if (!TI->getType()->typeIsConvertibleTo(ExpectedType)) {
1904             Error(NameLoc,
1905                   "Value specified for template argument #" + Twine(i) + " (" +
1906                   ExpectedArg->getNameInitAsString() + ") is of type '" +
1907                   TI->getType()->getAsString() + "', expected '" +
1908                   ExpectedType->getAsString() + "': " + TI->getAsString());
1909             return nullptr;
1910           }
1911           continue;
1912         }
1913       } else if (ExpectedArg->getValue()->isComplete())
1914         continue;
1915
1916       Error(NameLoc,
1917             "Value not specified for template argument #" + Twine(i) + " (" +
1918             ExpectedArgs[i]->getAsUnquotedString() + ")");
1919       return nullptr;
1920     }
1921
1922     return VarDefInit::get(Class, Args)->Fold();
1923   }
1924   case tgtok::l_brace: {           // Value ::= '{' ValueList '}'
1925     SMLoc BraceLoc = Lex.getLoc();
1926     Lex.Lex(); // eat the '{'
1927     SmallVector<Init*, 16> Vals;
1928
1929     if (Lex.getCode() != tgtok::r_brace) {
1930       ParseValueList(Vals, CurRec);
1931       if (Vals.empty()) return nullptr;
1932     }
1933     if (Lex.getCode() != tgtok::r_brace) {
1934       TokError("expected '}' at end of bit list value");
1935       return nullptr;
1936     }
1937     Lex.Lex();  // eat the '}'
1938
1939     SmallVector<Init *, 16> NewBits;
1940
1941     // As we parse { a, b, ... }, 'a' is the highest bit, but we parse it
1942     // first.  We'll first read everything in to a vector, then we can reverse
1943     // it to get the bits in the correct order for the BitsInit value.
1944     for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
1945       // FIXME: The following two loops would not be duplicated
1946       //        if the API was a little more orthogonal.
1947
1948       // bits<n> values are allowed to initialize n bits.
1949       if (BitsInit *BI = dyn_cast<BitsInit>(Vals[i])) {
1950         for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i)
1951           NewBits.push_back(BI->getBit((e - i) - 1));
1952         continue;
1953       }
1954       // bits<n> can also come from variable initializers.
1955       if (VarInit *VI = dyn_cast<VarInit>(Vals[i])) {
1956         if (BitsRecTy *BitsRec = dyn_cast<BitsRecTy>(VI->getType())) {
1957           for (unsigned i = 0, e = BitsRec->getNumBits(); i != e; ++i)
1958             NewBits.push_back(VI->getBit((e - i) - 1));
1959           continue;
1960         }
1961         // Fallthrough to try convert this to a bit.
1962       }
1963       // All other values must be convertible to just a single bit.
1964       Init *Bit = Vals[i]->getCastTo(BitRecTy::get());
1965       if (!Bit) {
1966         Error(BraceLoc, "Element #" + Twine(i) + " (" + Vals[i]->getAsString() +
1967               ") is not convertable to a bit");
1968         return nullptr;
1969       }
1970       NewBits.push_back(Bit);
1971     }
1972     std::reverse(NewBits.begin(), NewBits.end());
1973     return BitsInit::get(NewBits);
1974   }
1975   case tgtok::l_square: {          // Value ::= '[' ValueList ']'
1976     Lex.Lex(); // eat the '['
1977     SmallVector<Init*, 16> Vals;
1978
1979     RecTy *DeducedEltTy = nullptr;
1980     ListRecTy *GivenListTy = nullptr;
1981
1982     if (ItemType) {
1983       ListRecTy *ListType = dyn_cast<ListRecTy>(ItemType);
1984       if (!ListType) {
1985         TokError(Twine("Type mismatch for list, expected list type, got ") +
1986                  ItemType->getAsString());
1987         return nullptr;
1988       }
1989       GivenListTy = ListType;
1990     }
1991
1992     if (Lex.getCode() != tgtok::r_square) {
1993       ParseValueList(Vals, CurRec, nullptr,
1994                      GivenListTy ? GivenListTy->getElementType() : nullptr);
1995       if (Vals.empty()) return nullptr;
1996     }
1997     if (Lex.getCode() != tgtok::r_square) {
1998       TokError("expected ']' at end of list value");
1999       return nullptr;
2000     }
2001     Lex.Lex();  // eat the ']'
2002
2003     RecTy *GivenEltTy = nullptr;
2004     if (Lex.getCode() == tgtok::less) {
2005       // Optional list element type
2006       Lex.Lex();  // eat the '<'
2007
2008       GivenEltTy = ParseType();
2009       if (!GivenEltTy) {
2010         // Couldn't parse element type
2011         return nullptr;
2012       }
2013
2014       if (Lex.getCode() != tgtok::greater) {
2015         TokError("expected '>' at end of list element type");
2016         return nullptr;
2017       }
2018       Lex.Lex();  // eat the '>'
2019     }
2020
2021     // Check elements
2022     RecTy *EltTy = nullptr;
2023     for (Init *V : Vals) {
2024       TypedInit *TArg = dyn_cast<TypedInit>(V);
2025       if (TArg) {
2026         if (EltTy) {
2027           EltTy = resolveTypes(EltTy, TArg->getType());
2028           if (!EltTy) {
2029             TokError("Incompatible types in list elements");
2030             return nullptr;
2031           }
2032         } else {
2033           EltTy = TArg->getType();
2034         }
2035       }
2036     }
2037
2038     if (GivenEltTy) {
2039       if (EltTy) {
2040         // Verify consistency
2041         if (!EltTy->typeIsConvertibleTo(GivenEltTy)) {
2042           TokError("Incompatible types in list elements");
2043           return nullptr;
2044         }
2045       }
2046       EltTy = GivenEltTy;
2047     }
2048
2049     if (!EltTy) {
2050       if (!ItemType) {
2051         TokError("No type for list");
2052         return nullptr;
2053       }
2054       DeducedEltTy = GivenListTy->getElementType();
2055     } else {
2056       // Make sure the deduced type is compatible with the given type
2057       if (GivenListTy) {
2058         if (!EltTy->typeIsConvertibleTo(GivenListTy->getElementType())) {
2059           TokError(Twine("Element type mismatch for list: element type '") +
2060                    EltTy->getAsString() + "' not convertible to '" +
2061                    GivenListTy->getElementType()->getAsString());
2062           return nullptr;
2063         }
2064       }
2065       DeducedEltTy = EltTy;
2066     }
2067
2068     return ListInit::get(Vals, DeducedEltTy);
2069   }
2070   case tgtok::l_paren: {         // Value ::= '(' IDValue DagArgList ')'
2071     Lex.Lex();   // eat the '('
2072     if (Lex.getCode() != tgtok::Id && Lex.getCode() != tgtok::XCast &&
2073         Lex.getCode() != tgtok::question && Lex.getCode() != tgtok::XGetOp) {
2074       TokError("expected identifier in dag init");
2075       return nullptr;
2076     }
2077
2078     Init *Operator = ParseValue(CurRec);
2079     if (!Operator) return nullptr;
2080
2081     // If the operator name is present, parse it.
2082     StringInit *OperatorName = nullptr;
2083     if (Lex.getCode() == tgtok::colon) {
2084       if (Lex.Lex() != tgtok::VarName) { // eat the ':'
2085         TokError("expected variable name in dag operator");
2086         return nullptr;
2087       }
2088       OperatorName = StringInit::get(Lex.getCurStrVal());
2089       Lex.Lex();  // eat the VarName.
2090     }
2091
2092     SmallVector<std::pair<llvm::Init*, StringInit*>, 8> DagArgs;
2093     if (Lex.getCode() != tgtok::r_paren) {
2094       ParseDagArgList(DagArgs, CurRec);
2095       if (DagArgs.empty()) return nullptr;
2096     }
2097
2098     if (Lex.getCode() != tgtok::r_paren) {
2099       TokError("expected ')' in dag init");
2100       return nullptr;
2101     }
2102     Lex.Lex();  // eat the ')'
2103
2104     return DagInit::get(Operator, OperatorName, DagArgs);
2105   }
2106
2107   case tgtok::XHead:
2108   case tgtok::XTail:
2109   case tgtok::XSize:
2110   case tgtok::XEmpty:
2111   case tgtok::XCast:
2112   case tgtok::XGetOp:  // Value ::= !unop '(' Value ')'
2113   case tgtok::XIsA:
2114   case tgtok::XConcat:
2115   case tgtok::XDag:
2116   case tgtok::XADD:
2117   case tgtok::XMUL:
2118   case tgtok::XAND:
2119   case tgtok::XOR:
2120   case tgtok::XSRA:
2121   case tgtok::XSRL:
2122   case tgtok::XSHL:
2123   case tgtok::XEq:
2124   case tgtok::XNe:
2125   case tgtok::XLe:
2126   case tgtok::XLt:
2127   case tgtok::XGe:
2128   case tgtok::XGt:
2129   case tgtok::XListConcat:
2130   case tgtok::XListSplat:
2131   case tgtok::XStrConcat:
2132   case tgtok::XSetOp:   // Value ::= !binop '(' Value ',' Value ')'
2133   case tgtok::XIf:
2134   case tgtok::XCond:
2135   case tgtok::XFoldl:
2136   case tgtok::XForEach:
2137   case tgtok::XSubst: {  // Value ::= !ternop '(' Value ',' Value ',' Value ')'
2138     return ParseOperation(CurRec, ItemType);
2139   }
2140   }
2141
2142   return R;
2143 }
2144
2145 /// ParseValue - Parse a tblgen value.  This returns null on error.
2146 ///
2147 ///   Value       ::= SimpleValue ValueSuffix*
2148 ///   ValueSuffix ::= '{' BitList '}'
2149 ///   ValueSuffix ::= '[' BitList ']'
2150 ///   ValueSuffix ::= '.' ID
2151 ///
2152 Init *TGParser::ParseValue(Record *CurRec, RecTy *ItemType, IDParseMode Mode) {
2153   Init *Result = ParseSimpleValue(CurRec, ItemType, Mode);
2154   if (!Result) return nullptr;
2155
2156   // Parse the suffixes now if present.
2157   while (true) {
2158     switch (Lex.getCode()) {
2159     default: return Result;
2160     case tgtok::l_brace: {
2161       if (Mode == ParseNameMode)
2162         // This is the beginning of the object body.
2163         return Result;
2164
2165       SMLoc CurlyLoc = Lex.getLoc();
2166       Lex.Lex(); // eat the '{'
2167       SmallVector<unsigned, 16> Ranges;
2168       ParseRangeList(Ranges);
2169       if (Ranges.empty()) return nullptr;
2170
2171       // Reverse the bitlist.
2172       std::reverse(Ranges.begin(), Ranges.end());
2173       Result = Result->convertInitializerBitRange(Ranges);
2174       if (!Result) {
2175         Error(CurlyLoc, "Invalid bit range for value");
2176         return nullptr;
2177       }
2178
2179       // Eat the '}'.
2180       if (Lex.getCode() != tgtok::r_brace) {
2181         TokError("expected '}' at end of bit range list");
2182         return nullptr;
2183       }
2184       Lex.Lex();
2185       break;
2186     }
2187     case tgtok::l_square: {
2188       SMLoc SquareLoc = Lex.getLoc();
2189       Lex.Lex(); // eat the '['
2190       SmallVector<unsigned, 16> Ranges;
2191       ParseRangeList(Ranges);
2192       if (Ranges.empty()) return nullptr;
2193
2194       Result = Result->convertInitListSlice(Ranges);
2195       if (!Result) {
2196         Error(SquareLoc, "Invalid range for list slice");
2197         return nullptr;
2198       }
2199
2200       // Eat the ']'.
2201       if (Lex.getCode() != tgtok::r_square) {
2202         TokError("expected ']' at end of list slice");
2203         return nullptr;
2204       }
2205       Lex.Lex();
2206       break;
2207     }
2208     case tgtok::period: {
2209       if (Lex.Lex() != tgtok::Id) {  // eat the .
2210         TokError("expected field identifier after '.'");
2211         return nullptr;
2212       }
2213       StringInit *FieldName = StringInit::get(Lex.getCurStrVal());
2214       if (!Result->getFieldType(FieldName)) {
2215         TokError("Cannot access field '" + Lex.getCurStrVal() + "' of value '" +
2216                  Result->getAsString() + "'");
2217         return nullptr;
2218       }
2219       Result = FieldInit::get(Result, FieldName)->Fold(CurRec);
2220       Lex.Lex();  // eat field name
2221       break;
2222     }
2223
2224     case tgtok::paste:
2225       SMLoc PasteLoc = Lex.getLoc();
2226       TypedInit *LHS = dyn_cast<TypedInit>(Result);
2227       if (!LHS) {
2228         Error(PasteLoc, "LHS of paste is not typed!");
2229         return nullptr;
2230       }
2231
2232       // Check if it's a 'listA # listB'
2233       if (isa<ListRecTy>(LHS->getType())) {
2234         Lex.Lex();  // Eat the '#'.
2235
2236         switch (Lex.getCode()) {
2237         case tgtok::colon:
2238         case tgtok::semi:
2239         case tgtok::l_brace:
2240           Result = LHS; // trailing paste, ignore.
2241           break;
2242         default:
2243           Init *RHSResult = ParseValue(CurRec, ItemType, ParseNameMode);
2244           Result = BinOpInit::getListConcat(LHS, RHSResult);
2245         }
2246         break;
2247       }
2248
2249       // Create a !strconcat() operation, first casting each operand to
2250       // a string if necessary.
2251       if (LHS->getType() != StringRecTy::get()) {
2252         auto CastLHS = dyn_cast<TypedInit>(
2253             UnOpInit::get(UnOpInit::CAST, LHS, StringRecTy::get())
2254                 ->Fold(CurRec));
2255         if (!CastLHS) {
2256           Error(PasteLoc,
2257                 Twine("can't cast '") + LHS->getAsString() + "' to string");
2258           return nullptr;
2259         }
2260         LHS = CastLHS;
2261       }
2262
2263       TypedInit *RHS = nullptr;
2264
2265       Lex.Lex();  // Eat the '#'.
2266       switch (Lex.getCode()) {
2267       case tgtok::colon:
2268       case tgtok::semi:
2269       case tgtok::l_brace:
2270         // These are all of the tokens that can begin an object body.
2271         // Some of these can also begin values but we disallow those cases
2272         // because they are unlikely to be useful.
2273
2274         // Trailing paste, concat with an empty string.
2275         RHS = StringInit::get("");
2276         break;
2277
2278       default:
2279         Init *RHSResult = ParseValue(CurRec, nullptr, ParseNameMode);
2280         RHS = dyn_cast<TypedInit>(RHSResult);
2281         if (!RHS) {
2282           Error(PasteLoc, "RHS of paste is not typed!");
2283           return nullptr;
2284         }
2285
2286         if (RHS->getType() != StringRecTy::get()) {
2287           auto CastRHS = dyn_cast<TypedInit>(
2288               UnOpInit::get(UnOpInit::CAST, RHS, StringRecTy::get())
2289                   ->Fold(CurRec));
2290           if (!CastRHS) {
2291             Error(PasteLoc,
2292                   Twine("can't cast '") + RHS->getAsString() + "' to string");
2293             return nullptr;
2294           }
2295           RHS = CastRHS;
2296         }
2297
2298         break;
2299       }
2300
2301       Result = BinOpInit::getStrConcat(LHS, RHS);
2302       break;
2303     }
2304   }
2305 }
2306
2307 /// ParseDagArgList - Parse the argument list for a dag literal expression.
2308 ///
2309 ///    DagArg     ::= Value (':' VARNAME)?
2310 ///    DagArg     ::= VARNAME
2311 ///    DagArgList ::= DagArg
2312 ///    DagArgList ::= DagArgList ',' DagArg
2313 void TGParser::ParseDagArgList(
2314     SmallVectorImpl<std::pair<llvm::Init*, StringInit*>> &Result,
2315     Record *CurRec) {
2316
2317   while (true) {
2318     // DagArg ::= VARNAME
2319     if (Lex.getCode() == tgtok::VarName) {
2320       // A missing value is treated like '?'.
2321       StringInit *VarName = StringInit::get(Lex.getCurStrVal());
2322       Result.emplace_back(UnsetInit::get(), VarName);
2323       Lex.Lex();
2324     } else {
2325       // DagArg ::= Value (':' VARNAME)?
2326       Init *Val = ParseValue(CurRec);
2327       if (!Val) {
2328         Result.clear();
2329         return;
2330       }
2331
2332       // If the variable name is present, add it.
2333       StringInit *VarName = nullptr;
2334       if (Lex.getCode() == tgtok::colon) {
2335         if (Lex.Lex() != tgtok::VarName) { // eat the ':'
2336           TokError("expected variable name in dag literal");
2337           Result.clear();
2338           return;
2339         }
2340         VarName = StringInit::get(Lex.getCurStrVal());
2341         Lex.Lex();  // eat the VarName.
2342       }
2343
2344       Result.push_back(std::make_pair(Val, VarName));
2345     }
2346     if (Lex.getCode() != tgtok::comma) break;
2347     Lex.Lex(); // eat the ','
2348   }
2349 }
2350
2351 /// ParseValueList - Parse a comma separated list of values, returning them as a
2352 /// vector.  Note that this always expects to be able to parse at least one
2353 /// value.  It returns an empty list if this is not possible.
2354 ///
2355 ///   ValueList ::= Value (',' Value)
2356 ///
2357 void TGParser::ParseValueList(SmallVectorImpl<Init*> &Result, Record *CurRec,
2358                               Record *ArgsRec, RecTy *EltTy) {
2359   RecTy *ItemType = EltTy;
2360   unsigned int ArgN = 0;
2361   if (ArgsRec && !EltTy) {
2362     ArrayRef<Init *> TArgs = ArgsRec->getTemplateArgs();
2363     if (TArgs.empty()) {
2364       TokError("template argument provided to non-template class");
2365       Result.clear();
2366       return;
2367     }
2368     const RecordVal *RV = ArgsRec->getValue(TArgs[ArgN]);
2369     if (!RV) {
2370       errs() << "Cannot find template arg " << ArgN << " (" << TArgs[ArgN]
2371         << ")\n";
2372     }
2373     assert(RV && "Template argument record not found??");
2374     ItemType = RV->getType();
2375     ++ArgN;
2376   }
2377   Result.push_back(ParseValue(CurRec, ItemType));
2378   if (!Result.back()) {
2379     Result.clear();
2380     return;
2381   }
2382
2383   while (Lex.getCode() == tgtok::comma) {
2384     Lex.Lex();  // Eat the comma
2385
2386     // ignore trailing comma for lists
2387     if (Lex.getCode() == tgtok::r_square)
2388       return;
2389
2390     if (ArgsRec && !EltTy) {
2391       ArrayRef<Init *> TArgs = ArgsRec->getTemplateArgs();
2392       if (ArgN >= TArgs.size()) {
2393         TokError("too many template arguments");
2394         Result.clear();
2395         return;
2396       }
2397       const RecordVal *RV = ArgsRec->getValue(TArgs[ArgN]);
2398       assert(RV && "Template argument record not found??");
2399       ItemType = RV->getType();
2400       ++ArgN;
2401     }
2402     Result.push_back(ParseValue(CurRec, ItemType));
2403     if (!Result.back()) {
2404       Result.clear();
2405       return;
2406     }
2407   }
2408 }
2409
2410 /// ParseDeclaration - Read a declaration, returning the name of field ID, or an
2411 /// empty string on error.  This can happen in a number of different context's,
2412 /// including within a def or in the template args for a def (which which case
2413 /// CurRec will be non-null) and within the template args for a multiclass (in
2414 /// which case CurRec will be null, but CurMultiClass will be set).  This can
2415 /// also happen within a def that is within a multiclass, which will set both
2416 /// CurRec and CurMultiClass.
2417 ///
2418 ///  Declaration ::= FIELD? Type ID ('=' Value)?
2419 ///
2420 Init *TGParser::ParseDeclaration(Record *CurRec,
2421                                        bool ParsingTemplateArgs) {
2422   // Read the field prefix if present.
2423   bool HasField = Lex.getCode() == tgtok::Field;
2424   if (HasField) Lex.Lex();
2425
2426   RecTy *Type = ParseType();
2427   if (!Type) return nullptr;
2428
2429   if (Lex.getCode() != tgtok::Id) {
2430     TokError("Expected identifier in declaration");
2431     return nullptr;
2432   }
2433
2434   std::string Str = Lex.getCurStrVal();
2435   if (Str == "NAME") {
2436     TokError("'" + Str + "' is a reserved variable name");
2437     return nullptr;
2438   }
2439
2440   SMLoc IdLoc = Lex.getLoc();
2441   Init *DeclName = StringInit::get(Str);
2442   Lex.Lex();
2443
2444   if (ParsingTemplateArgs) {
2445     if (CurRec)
2446       DeclName = QualifyName(*CurRec, CurMultiClass, DeclName, ":");
2447     else
2448       assert(CurMultiClass);
2449     if (CurMultiClass)
2450       DeclName = QualifyName(CurMultiClass->Rec, CurMultiClass, DeclName,
2451                              "::");
2452   }
2453
2454   // Add the value.
2455   if (AddValue(CurRec, IdLoc, RecordVal(DeclName, Type, HasField)))
2456     return nullptr;
2457
2458   // If a value is present, parse it.
2459   if (Lex.getCode() == tgtok::equal) {
2460     Lex.Lex();
2461     SMLoc ValLoc = Lex.getLoc();
2462     Init *Val = ParseValue(CurRec, Type);
2463     if (!Val ||
2464         SetValue(CurRec, ValLoc, DeclName, None, Val))
2465       // Return the name, even if an error is thrown.  This is so that we can
2466       // continue to make some progress, even without the value having been
2467       // initialized.
2468       return DeclName;
2469   }
2470
2471   return DeclName;
2472 }
2473
2474 /// ParseForeachDeclaration - Read a foreach declaration, returning
2475 /// the name of the declared object or a NULL Init on error.  Return
2476 /// the name of the parsed initializer list through ForeachListName.
2477 ///
2478 ///  ForeachDeclaration ::= ID '=' '{' RangeList '}'
2479 ///  ForeachDeclaration ::= ID '=' RangePiece
2480 ///  ForeachDeclaration ::= ID '=' Value
2481 ///
2482 VarInit *TGParser::ParseForeachDeclaration(Init *&ForeachListValue) {
2483   if (Lex.getCode() != tgtok::Id) {
2484     TokError("Expected identifier in foreach declaration");
2485     return nullptr;
2486   }
2487
2488   Init *DeclName = StringInit::get(Lex.getCurStrVal());
2489   Lex.Lex();
2490
2491   // If a value is present, parse it.
2492   if (Lex.getCode() != tgtok::equal) {
2493     TokError("Expected '=' in foreach declaration");
2494     return nullptr;
2495   }
2496   Lex.Lex();  // Eat the '='
2497
2498   RecTy *IterType = nullptr;
2499   SmallVector<unsigned, 16> Ranges;
2500
2501   switch (Lex.getCode()) {
2502   case tgtok::l_brace: { // '{' RangeList '}'
2503     Lex.Lex(); // eat the '{'
2504     ParseRangeList(Ranges);
2505     if (Lex.getCode() != tgtok::r_brace) {
2506       TokError("expected '}' at end of bit range list");
2507       return nullptr;
2508     }
2509     Lex.Lex();
2510     break;
2511   }
2512
2513   default: {
2514     SMLoc ValueLoc = Lex.getLoc();
2515     Init *I = ParseValue(nullptr);
2516     if (!I)
2517       return nullptr;
2518
2519     TypedInit *TI = dyn_cast<TypedInit>(I);
2520     if (TI && isa<ListRecTy>(TI->getType())) {
2521       ForeachListValue = I;
2522       IterType = cast<ListRecTy>(TI->getType())->getElementType();
2523       break;
2524     }
2525
2526     if (TI) {
2527       if (ParseRangePiece(Ranges, TI))
2528         return nullptr;
2529       break;
2530     }
2531
2532     std::string Type;
2533     if (TI)
2534       Type = (Twine("' of type '") + TI->getType()->getAsString()).str();
2535     Error(ValueLoc, "expected a list, got '" + I->getAsString() + Type + "'");
2536     if (CurMultiClass) {
2537       PrintNote({}, "references to multiclass template arguments cannot be "
2538                 "resolved at this time");
2539     }
2540     return nullptr;
2541   }
2542   }
2543
2544
2545   if (!Ranges.empty()) {
2546     assert(!IterType && "Type already initialized?");
2547     IterType = IntRecTy::get();
2548     std::vector<Init*> Values;
2549     for (unsigned R : Ranges)
2550       Values.push_back(IntInit::get(R));
2551     ForeachListValue = ListInit::get(Values, IterType);
2552   }
2553
2554   if (!IterType)
2555     return nullptr;
2556
2557   return VarInit::get(DeclName, IterType);
2558 }
2559
2560 /// ParseTemplateArgList - Read a template argument list, which is a non-empty
2561 /// sequence of template-declarations in <>'s.  If CurRec is non-null, these are
2562 /// template args for a def, which may or may not be in a multiclass.  If null,
2563 /// these are the template args for a multiclass.
2564 ///
2565 ///    TemplateArgList ::= '<' Declaration (',' Declaration)* '>'
2566 ///
2567 bool TGParser::ParseTemplateArgList(Record *CurRec) {
2568   assert(Lex.getCode() == tgtok::less && "Not a template arg list!");
2569   Lex.Lex(); // eat the '<'
2570
2571   Record *TheRecToAddTo = CurRec ? CurRec : &CurMultiClass->Rec;
2572
2573   // Read the first declaration.
2574   Init *TemplArg = ParseDeclaration(CurRec, true/*templateargs*/);
2575   if (!TemplArg)
2576     return true;
2577
2578   TheRecToAddTo->addTemplateArg(TemplArg);
2579
2580   while (Lex.getCode() == tgtok::comma) {
2581     Lex.Lex(); // eat the ','
2582
2583     // Read the following declarations.
2584     SMLoc Loc = Lex.getLoc();
2585     TemplArg = ParseDeclaration(CurRec, true/*templateargs*/);
2586     if (!TemplArg)
2587       return true;
2588
2589     if (TheRecToAddTo->isTemplateArg(TemplArg))
2590       return Error(Loc, "template argument with the same name has already been "
2591                         "defined");
2592
2593     TheRecToAddTo->addTemplateArg(TemplArg);
2594   }
2595
2596   if (Lex.getCode() != tgtok::greater)
2597     return TokError("expected '>' at end of template argument list");
2598   Lex.Lex(); // eat the '>'.
2599   return false;
2600 }
2601
2602 /// ParseBodyItem - Parse a single item at within the body of a def or class.
2603 ///
2604 ///   BodyItem ::= Declaration ';'
2605 ///   BodyItem ::= LET ID OptionalBitList '=' Value ';'
2606 ///   BodyItem ::= Defvar
2607 bool TGParser::ParseBodyItem(Record *CurRec) {
2608   if (Lex.getCode() == tgtok::Defvar)
2609     return ParseDefvar();
2610
2611   if (Lex.getCode() != tgtok::Let) {
2612     if (!ParseDeclaration(CurRec, false))
2613       return true;
2614
2615     if (Lex.getCode() != tgtok::semi)
2616       return TokError("expected ';' after declaration");
2617     Lex.Lex();
2618     return false;
2619   }
2620
2621   // LET ID OptionalRangeList '=' Value ';'
2622   if (Lex.Lex() != tgtok::Id)
2623     return TokError("expected field identifier after let");
2624
2625   SMLoc IdLoc = Lex.getLoc();
2626   StringInit *FieldName = StringInit::get(Lex.getCurStrVal());
2627   Lex.Lex();  // eat the field name.
2628
2629   SmallVector<unsigned, 16> BitList;
2630   if (ParseOptionalBitList(BitList))
2631     return true;
2632   std::reverse(BitList.begin(), BitList.end());
2633
2634   if (Lex.getCode() != tgtok::equal)
2635     return TokError("expected '=' in let expression");
2636   Lex.Lex();  // eat the '='.
2637
2638   RecordVal *Field = CurRec->getValue(FieldName);
2639   if (!Field)
2640     return TokError("Value '" + FieldName->getValue() + "' unknown!");
2641
2642   RecTy *Type = Field->getType();
2643
2644   Init *Val = ParseValue(CurRec, Type);
2645   if (!Val) return true;
2646
2647   if (Lex.getCode() != tgtok::semi)
2648     return TokError("expected ';' after let expression");
2649   Lex.Lex();
2650
2651   return SetValue(CurRec, IdLoc, FieldName, BitList, Val);
2652 }
2653
2654 /// ParseBody - Read the body of a class or def.  Return true on error, false on
2655 /// success.
2656 ///
2657 ///   Body     ::= ';'
2658 ///   Body     ::= '{' BodyList '}'
2659 ///   BodyList BodyItem*
2660 ///
2661 bool TGParser::ParseBody(Record *CurRec) {
2662   // If this is a null definition, just eat the semi and return.
2663   if (Lex.getCode() == tgtok::semi) {
2664     Lex.Lex();
2665     return false;
2666   }
2667
2668   if (Lex.getCode() != tgtok::l_brace)
2669     return TokError("Expected ';' or '{' to start body");
2670   // Eat the '{'.
2671   Lex.Lex();
2672
2673   // An object body introduces a new scope for local variables.
2674   TGLocalVarScope *BodyScope = PushLocalScope();
2675
2676   while (Lex.getCode() != tgtok::r_brace)
2677     if (ParseBodyItem(CurRec))
2678       return true;
2679
2680   PopLocalScope(BodyScope);
2681
2682   // Eat the '}'.
2683   Lex.Lex();
2684   return false;
2685 }
2686
2687 /// Apply the current let bindings to \a CurRec.
2688 /// \returns true on error, false otherwise.
2689 bool TGParser::ApplyLetStack(Record *CurRec) {
2690   for (SmallVectorImpl<LetRecord> &LetInfo : LetStack)
2691     for (LetRecord &LR : LetInfo)
2692       if (SetValue(CurRec, LR.Loc, LR.Name, LR.Bits, LR.Value))
2693         return true;
2694   return false;
2695 }
2696
2697 bool TGParser::ApplyLetStack(RecordsEntry &Entry) {
2698   if (Entry.Rec)
2699     return ApplyLetStack(Entry.Rec.get());
2700
2701   for (auto &E : Entry.Loop->Entries) {
2702     if (ApplyLetStack(E))
2703       return true;
2704   }
2705
2706   return false;
2707 }
2708
2709 /// ParseObjectBody - Parse the body of a def or class.  This consists of an
2710 /// optional ClassList followed by a Body.  CurRec is the current def or class
2711 /// that is being parsed.
2712 ///
2713 ///   ObjectBody      ::= BaseClassList Body
2714 ///   BaseClassList   ::= /*empty*/
2715 ///   BaseClassList   ::= ':' BaseClassListNE
2716 ///   BaseClassListNE ::= SubClassRef (',' SubClassRef)*
2717 ///
2718 bool TGParser::ParseObjectBody(Record *CurRec) {
2719   // If there is a baseclass list, read it.
2720   if (Lex.getCode() == tgtok::colon) {
2721     Lex.Lex();
2722
2723     // Read all of the subclasses.
2724     SubClassReference SubClass = ParseSubClassReference(CurRec, false);
2725     while (true) {
2726       // Check for error.
2727       if (!SubClass.Rec) return true;
2728
2729       // Add it.
2730       if (AddSubClass(CurRec, SubClass))
2731         return true;
2732
2733       if (Lex.getCode() != tgtok::comma) break;
2734       Lex.Lex(); // eat ','.
2735       SubClass = ParseSubClassReference(CurRec, false);
2736     }
2737   }
2738
2739   if (ApplyLetStack(CurRec))
2740     return true;
2741
2742   return ParseBody(CurRec);
2743 }
2744
2745 /// ParseDef - Parse and return a top level or multiclass def, return the record
2746 /// corresponding to it.  This returns null on error.
2747 ///
2748 ///   DefInst ::= DEF ObjectName ObjectBody
2749 ///
2750 bool TGParser::ParseDef(MultiClass *CurMultiClass) {
2751   SMLoc DefLoc = Lex.getLoc();
2752   assert(Lex.getCode() == tgtok::Def && "Unknown tok");
2753   Lex.Lex();  // Eat the 'def' token.
2754
2755   // Parse ObjectName and make a record for it.
2756   std::unique_ptr<Record> CurRec;
2757   Init *Name = ParseObjectName(CurMultiClass);
2758   if (!Name)
2759     return true;
2760
2761   if (isa<UnsetInit>(Name))
2762     CurRec = std::make_unique<Record>(Records.getNewAnonymousName(), DefLoc, Records,
2763                                  /*Anonymous=*/true);
2764   else
2765     CurRec = std::make_unique<Record>(Name, DefLoc, Records);
2766
2767   if (ParseObjectBody(CurRec.get()))
2768     return true;
2769
2770   return addEntry(std::move(CurRec));
2771 }
2772
2773 /// ParseDefset - Parse a defset statement.
2774 ///
2775 ///   Defset ::= DEFSET Type Id '=' '{' ObjectList '}'
2776 ///
2777 bool TGParser::ParseDefset() {
2778   assert(Lex.getCode() == tgtok::Defset);
2779   Lex.Lex(); // Eat the 'defset' token
2780
2781   DefsetRecord Defset;
2782   Defset.Loc = Lex.getLoc();
2783   RecTy *Type = ParseType();
2784   if (!Type)
2785     return true;
2786   if (!isa<ListRecTy>(Type))
2787     return Error(Defset.Loc, "expected list type");
2788   Defset.EltTy = cast<ListRecTy>(Type)->getElementType();
2789
2790   if (Lex.getCode() != tgtok::Id)
2791     return TokError("expected identifier");
2792   StringInit *DeclName = StringInit::get(Lex.getCurStrVal());
2793   if (Records.getGlobal(DeclName->getValue()))
2794     return TokError("def or global variable of this name already exists");
2795
2796   if (Lex.Lex() != tgtok::equal) // Eat the identifier
2797     return TokError("expected '='");
2798   if (Lex.Lex() != tgtok::l_brace) // Eat the '='
2799     return TokError("expected '{'");
2800   SMLoc BraceLoc = Lex.getLoc();
2801   Lex.Lex(); // Eat the '{'
2802
2803   Defsets.push_back(&Defset);
2804   bool Err = ParseObjectList(nullptr);
2805   Defsets.pop_back();
2806   if (Err)
2807     return true;
2808
2809   if (Lex.getCode() != tgtok::r_brace) {
2810     TokError("expected '}' at end of defset");
2811     return Error(BraceLoc, "to match this '{'");
2812   }
2813   Lex.Lex();  // Eat the '}'
2814
2815   Records.addExtraGlobal(DeclName->getValue(),
2816                          ListInit::get(Defset.Elements, Defset.EltTy));
2817   return false;
2818 }
2819
2820 /// ParseDefvar - Parse a defvar statement.
2821 ///
2822 ///   Defvar ::= DEFVAR Id '=' Value ';'
2823 ///
2824 bool TGParser::ParseDefvar() {
2825   assert(Lex.getCode() == tgtok::Defvar);
2826   Lex.Lex(); // Eat the 'defvar' token
2827
2828   if (Lex.getCode() != tgtok::Id)
2829     return TokError("expected identifier");
2830   StringInit *DeclName = StringInit::get(Lex.getCurStrVal());
2831   if (CurLocalScope) {
2832     if (CurLocalScope->varAlreadyDefined(DeclName->getValue()))
2833       return TokError("local variable of this name already exists");
2834   } else {
2835     if (Records.getGlobal(DeclName->getValue()))
2836       return TokError("def or global variable of this name already exists");
2837   }
2838
2839   if (Lex.Lex() != tgtok::equal) // Eat the identifier
2840     return TokError("expected '='");
2841   Lex.Lex(); // Eat the '='
2842
2843   Init *Value = ParseValue(nullptr);
2844   if (!Value)
2845     return true;
2846
2847   if (Lex.getCode() != tgtok::semi)
2848     return TokError("expected ';'");
2849   Lex.Lex(); // Eat the ';'
2850
2851   if (CurLocalScope)
2852     CurLocalScope->addVar(DeclName->getValue(), Value);
2853   else
2854     Records.addExtraGlobal(DeclName->getValue(), Value);
2855
2856   return false;
2857 }
2858
2859 /// ParseForeach - Parse a for statement.  Return the record corresponding
2860 /// to it.  This returns true on error.
2861 ///
2862 ///   Foreach ::= FOREACH Declaration IN '{ ObjectList '}'
2863 ///   Foreach ::= FOREACH Declaration IN Object
2864 ///
2865 bool TGParser::ParseForeach(MultiClass *CurMultiClass) {
2866   SMLoc Loc = Lex.getLoc();
2867   assert(Lex.getCode() == tgtok::Foreach && "Unknown tok");
2868   Lex.Lex();  // Eat the 'for' token.
2869
2870   // Make a temporary object to record items associated with the for
2871   // loop.
2872   Init *ListValue = nullptr;
2873   VarInit *IterName = ParseForeachDeclaration(ListValue);
2874   if (!IterName)
2875     return TokError("expected declaration in for");
2876
2877   if (Lex.getCode() != tgtok::In)
2878     return TokError("Unknown tok");
2879   Lex.Lex();  // Eat the in
2880
2881   // Create a loop object and remember it.
2882   Loops.push_back(std::make_unique<ForeachLoop>(Loc, IterName, ListValue));
2883
2884   // A foreach loop introduces a new scope for local variables.
2885   TGLocalVarScope *ForeachScope = PushLocalScope();
2886
2887   if (Lex.getCode() != tgtok::l_brace) {
2888     // FOREACH Declaration IN Object
2889     if (ParseObject(CurMultiClass))
2890       return true;
2891   } else {
2892     SMLoc BraceLoc = Lex.getLoc();
2893     // Otherwise, this is a group foreach.
2894     Lex.Lex();  // eat the '{'.
2895
2896     // Parse the object list.
2897     if (ParseObjectList(CurMultiClass))
2898       return true;
2899
2900     if (Lex.getCode() != tgtok::r_brace) {
2901       TokError("expected '}' at end of foreach command");
2902       return Error(BraceLoc, "to match this '{'");
2903     }
2904     Lex.Lex();  // Eat the }
2905   }
2906
2907   PopLocalScope(ForeachScope);
2908
2909   // Resolve the loop or store it for later resolution.
2910   std::unique_ptr<ForeachLoop> Loop = std::move(Loops.back());
2911   Loops.pop_back();
2912
2913   return addEntry(std::move(Loop));
2914 }
2915
2916 /// ParseIf - Parse an if statement.
2917 ///
2918 ///   If ::= IF Value THEN IfBody
2919 ///   If ::= IF Value THEN IfBody ELSE IfBody
2920 ///
2921 bool TGParser::ParseIf(MultiClass *CurMultiClass) {
2922   SMLoc Loc = Lex.getLoc();
2923   assert(Lex.getCode() == tgtok::If && "Unknown tok");
2924   Lex.Lex(); // Eat the 'if' token.
2925
2926   // Make a temporary object to record items associated with the for
2927   // loop.
2928   Init *Condition = ParseValue(nullptr);
2929   if (!Condition)
2930     return true;
2931
2932   if (Lex.getCode() != tgtok::Then)
2933     return TokError("Unknown tok");
2934   Lex.Lex(); // Eat the 'then'
2935
2936   // We have to be able to save if statements to execute later, and they have
2937   // to live on the same stack as foreach loops. The simplest implementation
2938   // technique is to convert each 'then' or 'else' clause *into* a foreach
2939   // loop, over a list of length 0 or 1 depending on the condition, and with no
2940   // iteration variable being assigned.
2941
2942   ListInit *EmptyList = ListInit::get({}, BitRecTy::get());
2943   ListInit *SingletonList = ListInit::get({BitInit::get(1)}, BitRecTy::get());
2944   RecTy *BitListTy = ListRecTy::get(BitRecTy::get());
2945
2946   // The foreach containing the then-clause selects SingletonList if
2947   // the condition is true.
2948   Init *ThenClauseList =
2949       TernOpInit::get(TernOpInit::IF, Condition, SingletonList, EmptyList,
2950                       BitListTy)
2951           ->Fold(nullptr);
2952   Loops.push_back(std::make_unique<ForeachLoop>(Loc, nullptr, ThenClauseList));
2953
2954   if (ParseIfBody(CurMultiClass, "then"))
2955     return true;
2956
2957   std::unique_ptr<ForeachLoop> Loop = std::move(Loops.back());
2958   Loops.pop_back();
2959
2960   if (addEntry(std::move(Loop)))
2961     return true;
2962
2963   // Now look for an optional else clause. The if-else syntax has the usual
2964   // dangling-else ambiguity, and by greedily matching an else here if we can,
2965   // we implement the usual resolution of pairing with the innermost unmatched
2966   // if.
2967   if (Lex.getCode() == tgtok::ElseKW) {
2968     Lex.Lex(); // Eat the 'else'
2969
2970     // The foreach containing the else-clause uses the same pair of lists as
2971     // above, but this time, selects SingletonList if the condition is *false*.
2972     Init *ElseClauseList =
2973         TernOpInit::get(TernOpInit::IF, Condition, EmptyList, SingletonList,
2974                         BitListTy)
2975             ->Fold(nullptr);
2976     Loops.push_back(
2977         std::make_unique<ForeachLoop>(Loc, nullptr, ElseClauseList));
2978
2979     if (ParseIfBody(CurMultiClass, "else"))
2980       return true;
2981
2982     Loop = std::move(Loops.back());
2983     Loops.pop_back();
2984
2985     if (addEntry(std::move(Loop)))
2986       return true;
2987   }
2988
2989   return false;
2990 }
2991
2992 /// ParseIfBody - Parse the then-clause or else-clause of an if statement.
2993 ///
2994 ///   IfBody ::= Object
2995 ///   IfBody ::= '{' ObjectList '}'
2996 ///
2997 bool TGParser::ParseIfBody(MultiClass *CurMultiClass, StringRef Kind) {
2998   TGLocalVarScope *BodyScope = PushLocalScope();
2999
3000   if (Lex.getCode() != tgtok::l_brace) {
3001     // A single object.
3002     if (ParseObject(CurMultiClass))
3003       return true;
3004   } else {
3005     SMLoc BraceLoc = Lex.getLoc();
3006     // A braced block.
3007     Lex.Lex(); // eat the '{'.
3008
3009     // Parse the object list.
3010     if (ParseObjectList(CurMultiClass))
3011       return true;
3012
3013     if (Lex.getCode() != tgtok::r_brace) {
3014       TokError("expected '}' at end of '" + Kind + "' clause");
3015       return Error(BraceLoc, "to match this '{'");
3016     }
3017
3018     Lex.Lex(); // Eat the }
3019   }
3020
3021   PopLocalScope(BodyScope);
3022   return false;
3023 }
3024
3025 /// ParseClass - Parse a tblgen class definition.
3026 ///
3027 ///   ClassInst ::= CLASS ID TemplateArgList? ObjectBody
3028 ///
3029 bool TGParser::ParseClass() {
3030   assert(Lex.getCode() == tgtok::Class && "Unexpected token!");
3031   Lex.Lex();
3032
3033   if (Lex.getCode() != tgtok::Id)
3034     return TokError("expected class name after 'class' keyword");
3035
3036   Record *CurRec = Records.getClass(Lex.getCurStrVal());
3037   if (CurRec) {
3038     // If the body was previously defined, this is an error.
3039     if (!CurRec->getValues().empty() ||
3040         !CurRec->getSuperClasses().empty() ||
3041         !CurRec->getTemplateArgs().empty())
3042       return TokError("Class '" + CurRec->getNameInitAsString() +
3043                       "' already defined");
3044   } else {
3045     // If this is the first reference to this class, create and add it.
3046     auto NewRec =
3047         std::make_unique<Record>(Lex.getCurStrVal(), Lex.getLoc(), Records,
3048                                   /*Class=*/true);
3049     CurRec = NewRec.get();
3050     Records.addClass(std::move(NewRec));
3051   }
3052   Lex.Lex(); // eat the name.
3053
3054   // If there are template args, parse them.
3055   if (Lex.getCode() == tgtok::less)
3056     if (ParseTemplateArgList(CurRec))
3057       return true;
3058
3059   return ParseObjectBody(CurRec);
3060 }
3061
3062 /// ParseLetList - Parse a non-empty list of assignment expressions into a list
3063 /// of LetRecords.
3064 ///
3065 ///   LetList ::= LetItem (',' LetItem)*
3066 ///   LetItem ::= ID OptionalRangeList '=' Value
3067 ///
3068 void TGParser::ParseLetList(SmallVectorImpl<LetRecord> &Result) {
3069   while (true) {
3070     if (Lex.getCode() != tgtok::Id) {
3071       TokError("expected identifier in let definition");
3072       Result.clear();
3073       return;
3074     }
3075
3076     StringInit *Name = StringInit::get(Lex.getCurStrVal());
3077     SMLoc NameLoc = Lex.getLoc();
3078     Lex.Lex();  // Eat the identifier.
3079
3080     // Check for an optional RangeList.
3081     SmallVector<unsigned, 16> Bits;
3082     if (ParseOptionalRangeList(Bits)) {
3083       Result.clear();
3084       return;
3085     }
3086     std::reverse(Bits.begin(), Bits.end());
3087
3088     if (Lex.getCode() != tgtok::equal) {
3089       TokError("expected '=' in let expression");
3090       Result.clear();
3091       return;
3092     }
3093     Lex.Lex();  // eat the '='.
3094
3095     Init *Val = ParseValue(nullptr);
3096     if (!Val) {
3097       Result.clear();
3098       return;
3099     }
3100
3101     // Now that we have everything, add the record.
3102     Result.emplace_back(Name, Bits, Val, NameLoc);
3103
3104     if (Lex.getCode() != tgtok::comma)
3105       return;
3106     Lex.Lex();  // eat the comma.
3107   }
3108 }
3109
3110 /// ParseTopLevelLet - Parse a 'let' at top level.  This can be a couple of
3111 /// different related productions. This works inside multiclasses too.
3112 ///
3113 ///   Object ::= LET LetList IN '{' ObjectList '}'
3114 ///   Object ::= LET LetList IN Object
3115 ///
3116 bool TGParser::ParseTopLevelLet(MultiClass *CurMultiClass) {
3117   assert(Lex.getCode() == tgtok::Let && "Unexpected token");
3118   Lex.Lex();
3119
3120   // Add this entry to the let stack.
3121   SmallVector<LetRecord, 8> LetInfo;
3122   ParseLetList(LetInfo);
3123   if (LetInfo.empty()) return true;
3124   LetStack.push_back(std::move(LetInfo));
3125
3126   if (Lex.getCode() != tgtok::In)
3127     return TokError("expected 'in' at end of top-level 'let'");
3128   Lex.Lex();
3129
3130   TGLocalVarScope *LetScope = PushLocalScope();
3131
3132   // If this is a scalar let, just handle it now
3133   if (Lex.getCode() != tgtok::l_brace) {
3134     // LET LetList IN Object
3135     if (ParseObject(CurMultiClass))
3136       return true;
3137   } else {   // Object ::= LETCommand '{' ObjectList '}'
3138     SMLoc BraceLoc = Lex.getLoc();
3139     // Otherwise, this is a group let.
3140     Lex.Lex();  // eat the '{'.
3141
3142     // Parse the object list.
3143     if (ParseObjectList(CurMultiClass))
3144       return true;
3145
3146     if (Lex.getCode() != tgtok::r_brace) {
3147       TokError("expected '}' at end of top level let command");
3148       return Error(BraceLoc, "to match this '{'");
3149     }
3150     Lex.Lex();
3151   }
3152
3153   PopLocalScope(LetScope);
3154
3155   // Outside this let scope, this let block is not active.
3156   LetStack.pop_back();
3157   return false;
3158 }
3159
3160 /// ParseMultiClass - Parse a multiclass definition.
3161 ///
3162 ///  MultiClassInst ::= MULTICLASS ID TemplateArgList?
3163 ///                     ':' BaseMultiClassList '{' MultiClassObject+ '}'
3164 ///  MultiClassObject ::= DefInst
3165 ///  MultiClassObject ::= MultiClassInst
3166 ///  MultiClassObject ::= DefMInst
3167 ///  MultiClassObject ::= LETCommand '{' ObjectList '}'
3168 ///  MultiClassObject ::= LETCommand Object
3169 ///
3170 bool TGParser::ParseMultiClass() {
3171   assert(Lex.getCode() == tgtok::MultiClass && "Unexpected token");
3172   Lex.Lex();  // Eat the multiclass token.
3173
3174   if (Lex.getCode() != tgtok::Id)
3175     return TokError("expected identifier after multiclass for name");
3176   std::string Name = Lex.getCurStrVal();
3177
3178   auto Result =
3179     MultiClasses.insert(std::make_pair(Name,
3180                     std::make_unique<MultiClass>(Name, Lex.getLoc(),Records)));
3181
3182   if (!Result.second)
3183     return TokError("multiclass '" + Name + "' already defined");
3184
3185   CurMultiClass = Result.first->second.get();
3186   Lex.Lex();  // Eat the identifier.
3187
3188   // If there are template args, parse them.
3189   if (Lex.getCode() == tgtok::less)
3190     if (ParseTemplateArgList(nullptr))
3191       return true;
3192
3193   bool inherits = false;
3194
3195   // If there are submulticlasses, parse them.
3196   if (Lex.getCode() == tgtok::colon) {
3197     inherits = true;
3198
3199     Lex.Lex();
3200
3201     // Read all of the submulticlasses.
3202     SubMultiClassReference SubMultiClass =
3203       ParseSubMultiClassReference(CurMultiClass);
3204     while (true) {
3205       // Check for error.
3206       if (!SubMultiClass.MC) return true;
3207
3208       // Add it.
3209       if (AddSubMultiClass(CurMultiClass, SubMultiClass))
3210         return true;
3211
3212       if (Lex.getCode() != tgtok::comma) break;
3213       Lex.Lex(); // eat ','.
3214       SubMultiClass = ParseSubMultiClassReference(CurMultiClass);
3215     }
3216   }
3217
3218   if (Lex.getCode() != tgtok::l_brace) {
3219     if (!inherits)
3220       return TokError("expected '{' in multiclass definition");
3221     if (Lex.getCode() != tgtok::semi)
3222       return TokError("expected ';' in multiclass definition");
3223     Lex.Lex();  // eat the ';'.
3224   } else {
3225     if (Lex.Lex() == tgtok::r_brace)  // eat the '{'.
3226       return TokError("multiclass must contain at least one def");
3227
3228     // A multiclass body introduces a new scope for local variables.
3229     TGLocalVarScope *MulticlassScope = PushLocalScope();
3230
3231     while (Lex.getCode() != tgtok::r_brace) {
3232       switch (Lex.getCode()) {
3233       default:
3234         return TokError("expected 'let', 'def', 'defm', 'defvar', 'foreach' "
3235                         "or 'if' in multiclass body");
3236       case tgtok::Let:
3237       case tgtok::Def:
3238       case tgtok::Defm:
3239       case tgtok::Defvar:
3240       case tgtok::Foreach:
3241       case tgtok::If:
3242         if (ParseObject(CurMultiClass))
3243           return true;
3244         break;
3245       }
3246     }
3247     Lex.Lex();  // eat the '}'.
3248
3249     PopLocalScope(MulticlassScope);
3250   }
3251
3252   CurMultiClass = nullptr;
3253   return false;
3254 }
3255
3256 /// ParseDefm - Parse the instantiation of a multiclass.
3257 ///
3258 ///   DefMInst ::= DEFM ID ':' DefmSubClassRef ';'
3259 ///
3260 bool TGParser::ParseDefm(MultiClass *CurMultiClass) {
3261   assert(Lex.getCode() == tgtok::Defm && "Unexpected token!");
3262   Lex.Lex(); // eat the defm
3263
3264   Init *DefmName = ParseObjectName(CurMultiClass);
3265   if (!DefmName)
3266     return true;
3267   if (isa<UnsetInit>(DefmName)) {
3268     DefmName = Records.getNewAnonymousName();
3269     if (CurMultiClass)
3270       DefmName = BinOpInit::getStrConcat(
3271           VarInit::get(QualifiedNameOfImplicitName(CurMultiClass),
3272                        StringRecTy::get()),
3273           DefmName);
3274   }
3275
3276   if (Lex.getCode() != tgtok::colon)
3277     return TokError("expected ':' after defm identifier");
3278
3279   // Keep track of the new generated record definitions.
3280   std::vector<RecordsEntry> NewEntries;
3281
3282   // This record also inherits from a regular class (non-multiclass)?
3283   bool InheritFromClass = false;
3284
3285   // eat the colon.
3286   Lex.Lex();
3287
3288   SMLoc SubClassLoc = Lex.getLoc();
3289   SubClassReference Ref = ParseSubClassReference(nullptr, true);
3290
3291   while (true) {
3292     if (!Ref.Rec) return true;
3293
3294     // To instantiate a multiclass, we need to first get the multiclass, then
3295     // instantiate each def contained in the multiclass with the SubClassRef
3296     // template parameters.
3297     MultiClass *MC = MultiClasses[Ref.Rec->getName()].get();
3298     assert(MC && "Didn't lookup multiclass correctly?");
3299     ArrayRef<Init*> TemplateVals = Ref.TemplateArgs;
3300
3301     // Verify that the correct number of template arguments were specified.
3302     ArrayRef<Init *> TArgs = MC->Rec.getTemplateArgs();
3303     if (TArgs.size() < TemplateVals.size())
3304       return Error(SubClassLoc,
3305                    "more template args specified than multiclass expects");
3306
3307     SubstStack Substs;
3308     for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
3309       if (i < TemplateVals.size()) {
3310         Substs.emplace_back(TArgs[i], TemplateVals[i]);
3311       } else {
3312         Init *Default = MC->Rec.getValue(TArgs[i])->getValue();
3313         if (!Default->isComplete()) {
3314           return Error(SubClassLoc,
3315                        "value not specified for template argument #" +
3316                            Twine(i) + " (" + TArgs[i]->getAsUnquotedString() +
3317                            ") of multiclass '" + MC->Rec.getNameInitAsString() +
3318                            "'");
3319         }
3320         Substs.emplace_back(TArgs[i], Default);
3321       }
3322     }
3323
3324     Substs.emplace_back(QualifiedNameOfImplicitName(MC), DefmName);
3325
3326     if (resolve(MC->Entries, Substs, CurMultiClass == nullptr, &NewEntries,
3327                 &SubClassLoc))
3328       return true;
3329
3330     if (Lex.getCode() != tgtok::comma) break;
3331     Lex.Lex(); // eat ','.
3332
3333     if (Lex.getCode() != tgtok::Id)
3334       return TokError("expected identifier");
3335
3336     SubClassLoc = Lex.getLoc();
3337
3338     // A defm can inherit from regular classes (non-multiclass) as
3339     // long as they come in the end of the inheritance list.
3340     InheritFromClass = (Records.getClass(Lex.getCurStrVal()) != nullptr);
3341
3342     if (InheritFromClass)
3343       break;
3344
3345     Ref = ParseSubClassReference(nullptr, true);
3346   }
3347
3348   if (InheritFromClass) {
3349     // Process all the classes to inherit as if they were part of a
3350     // regular 'def' and inherit all record values.
3351     SubClassReference SubClass = ParseSubClassReference(nullptr, false);
3352     while (true) {
3353       // Check for error.
3354       if (!SubClass.Rec) return true;
3355
3356       // Get the expanded definition prototypes and teach them about
3357       // the record values the current class to inherit has
3358       for (auto &E : NewEntries) {
3359         // Add it.
3360         if (AddSubClass(E, SubClass))
3361           return true;
3362       }
3363
3364       if (Lex.getCode() != tgtok::comma) break;
3365       Lex.Lex(); // eat ','.
3366       SubClass = ParseSubClassReference(nullptr, false);
3367     }
3368   }
3369
3370   for (auto &E : NewEntries) {
3371     if (ApplyLetStack(E))
3372       return true;
3373
3374     addEntry(std::move(E));
3375   }
3376
3377   if (Lex.getCode() != tgtok::semi)
3378     return TokError("expected ';' at end of defm");
3379   Lex.Lex();
3380
3381   return false;
3382 }
3383
3384 /// ParseObject
3385 ///   Object ::= ClassInst
3386 ///   Object ::= DefInst
3387 ///   Object ::= MultiClassInst
3388 ///   Object ::= DefMInst
3389 ///   Object ::= LETCommand '{' ObjectList '}'
3390 ///   Object ::= LETCommand Object
3391 ///   Object ::= Defset
3392 ///   Object ::= Defvar
3393 bool TGParser::ParseObject(MultiClass *MC) {
3394   switch (Lex.getCode()) {
3395   default:
3396     return TokError("Expected class, def, defm, defset, multiclass, let, "
3397                     "foreach or if");
3398   case tgtok::Let:   return ParseTopLevelLet(MC);
3399   case tgtok::Def:   return ParseDef(MC);
3400   case tgtok::Foreach:   return ParseForeach(MC);
3401   case tgtok::If:    return ParseIf(MC);
3402   case tgtok::Defm:  return ParseDefm(MC);
3403   case tgtok::Defset:
3404     if (MC)
3405       return TokError("defset is not allowed inside multiclass");
3406     return ParseDefset();
3407   case tgtok::Defvar:
3408     return ParseDefvar();
3409   case tgtok::Class:
3410     if (MC)
3411       return TokError("class is not allowed inside multiclass");
3412     if (!Loops.empty())
3413       return TokError("class is not allowed inside foreach loop");
3414     return ParseClass();
3415   case tgtok::MultiClass:
3416     if (!Loops.empty())
3417       return TokError("multiclass is not allowed inside foreach loop");
3418     return ParseMultiClass();
3419   }
3420 }
3421
3422 /// ParseObjectList
3423 ///   ObjectList :== Object*
3424 bool TGParser::ParseObjectList(MultiClass *MC) {
3425   while (isObjectStart(Lex.getCode())) {
3426     if (ParseObject(MC))
3427       return true;
3428   }
3429   return false;
3430 }
3431
3432 bool TGParser::ParseFile() {
3433   Lex.Lex(); // Prime the lexer.
3434   if (ParseObjectList()) return true;
3435
3436   // If we have unread input at the end of the file, report it.
3437   if (Lex.getCode() == tgtok::Eof)
3438     return false;
3439
3440   return TokError("Unexpected input at top level");
3441 }
3442
3443 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3444 LLVM_DUMP_METHOD void RecordsEntry::dump() const {
3445   if (Loop)
3446     Loop->dump();
3447   if (Rec)
3448     Rec->dump();
3449 }
3450
3451 LLVM_DUMP_METHOD void ForeachLoop::dump() const {
3452   errs() << "foreach " << IterVar->getAsString() << " = "
3453          << ListValue->getAsString() << " in {\n";
3454
3455   for (const auto &E : Entries)
3456     E.dump();
3457
3458   errs() << "}\n";
3459 }
3460
3461 LLVM_DUMP_METHOD void MultiClass::dump() const {
3462   errs() << "Record:\n";
3463   Rec.dump();
3464
3465   errs() << "Defs:\n";
3466   for (const auto &E : Entries)
3467     E.dump();
3468 }
3469 #endif