xref: /freebsd/contrib/llvm-project/llvm/lib/TableGen/TGParser.cpp (revision b1879975794772ee51f0b4865753364c7d7626c3)
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/SmallVector.h"
15 #include "llvm/ADT/StringExtras.h"
16 #include "llvm/ADT/Twine.h"
17 #include "llvm/Config/llvm-config.h"
18 #include "llvm/Support/Casting.h"
19 #include "llvm/Support/Compiler.h"
20 #include "llvm/Support/ErrorHandling.h"
21 #include "llvm/Support/raw_ostream.h"
22 #include <algorithm>
23 #include <cassert>
24 #include <cstdint>
25 #include <limits>
26 
27 using namespace llvm;
28 
29 //===----------------------------------------------------------------------===//
30 // Support Code for the Semantic Actions.
31 //===----------------------------------------------------------------------===//
32 
33 namespace llvm {
34 
35 struct SubClassReference {
36   SMRange RefRange;
37   Record *Rec = nullptr;
38   SmallVector<ArgumentInit *, 4> TemplateArgs;
39 
40   SubClassReference() = default;
41 
42   bool isInvalid() const { return Rec == nullptr; }
43 };
44 
45 struct SubMultiClassReference {
46   SMRange RefRange;
47   MultiClass *MC = nullptr;
48   SmallVector<ArgumentInit *, 4> TemplateArgs;
49 
50   SubMultiClassReference() = default;
51 
52   bool isInvalid() const { return MC == nullptr; }
53   void dump() const;
54 };
55 
56 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
57 LLVM_DUMP_METHOD void SubMultiClassReference::dump() const {
58   errs() << "Multiclass:\n";
59 
60   MC->dump();
61 
62   errs() << "Template args:\n";
63   for (Init *TA : TemplateArgs)
64     TA->dump();
65 }
66 #endif
67 
68 } // end namespace llvm
69 
70 static bool checkBitsConcrete(Record &R, const RecordVal &RV) {
71   BitsInit *BV = cast<BitsInit>(RV.getValue());
72   for (unsigned i = 0, e = BV->getNumBits(); i != e; ++i) {
73     Init *Bit = BV->getBit(i);
74     bool IsReference = false;
75     if (auto VBI = dyn_cast<VarBitInit>(Bit)) {
76       if (auto VI = dyn_cast<VarInit>(VBI->getBitVar())) {
77         if (R.getValue(VI->getName()))
78           IsReference = true;
79       }
80     } else if (isa<VarInit>(Bit)) {
81       IsReference = true;
82     }
83     if (!(IsReference || Bit->isConcrete()))
84       return false;
85   }
86   return true;
87 }
88 
89 static void checkConcrete(Record &R) {
90   for (const RecordVal &RV : R.getValues()) {
91     // HACK: Disable this check for variables declared with 'field'. This is
92     // done merely because existing targets have legitimate cases of
93     // non-concrete variables in helper defs. Ideally, we'd introduce a
94     // 'maybe' or 'optional' modifier instead of this.
95     if (RV.isNonconcreteOK())
96       continue;
97 
98     if (Init *V = RV.getValue()) {
99       bool Ok = isa<BitsInit>(V) ? checkBitsConcrete(R, RV) : V->isConcrete();
100       if (!Ok) {
101         PrintError(R.getLoc(),
102                    Twine("Initializer of '") + RV.getNameInitAsString() +
103                    "' in '" + R.getNameInitAsString() +
104                    "' could not be fully resolved: " +
105                    RV.getValue()->getAsString());
106       }
107     }
108   }
109 }
110 
111 /// Return an Init with a qualifier prefix referring
112 /// to CurRec's name.
113 static Init *QualifyName(Record &CurRec, Init *Name) {
114   RecordKeeper &RK = CurRec.getRecords();
115   Init *NewName = BinOpInit::getStrConcat(
116       CurRec.getNameInit(),
117       StringInit::get(RK, CurRec.isMultiClass() ? "::" : ":"));
118   NewName = BinOpInit::getStrConcat(NewName, Name);
119 
120   if (BinOpInit *BinOp = dyn_cast<BinOpInit>(NewName))
121     NewName = BinOp->Fold(&CurRec);
122   return NewName;
123 }
124 
125 static Init *QualifyName(MultiClass *MC, Init *Name) {
126   return QualifyName(MC->Rec, Name);
127 }
128 
129 /// Return the qualified version of the implicit 'NAME' template argument.
130 static Init *QualifiedNameOfImplicitName(Record &Rec) {
131   return QualifyName(Rec, StringInit::get(Rec.getRecords(), "NAME"));
132 }
133 
134 static Init *QualifiedNameOfImplicitName(MultiClass *MC) {
135   return QualifiedNameOfImplicitName(MC->Rec);
136 }
137 
138 Init *TGVarScope::getVar(RecordKeeper &Records, MultiClass *ParsingMultiClass,
139                          StringInit *Name, SMRange NameLoc,
140                          bool TrackReferenceLocs) const {
141   // First, we search in local variables.
142   auto It = Vars.find(Name->getValue());
143   if (It != Vars.end())
144     return It->second;
145 
146   auto FindValueInArgs = [&](Record *Rec, StringInit *Name) -> Init * {
147     if (!Rec)
148       return nullptr;
149     Init *ArgName = QualifyName(*Rec, Name);
150     if (Rec->isTemplateArg(ArgName)) {
151       RecordVal *RV = Rec->getValue(ArgName);
152       assert(RV && "Template arg doesn't exist??");
153       RV->setUsed(true);
154       if (TrackReferenceLocs)
155         RV->addReferenceLoc(NameLoc);
156       return VarInit::get(ArgName, RV->getType());
157     }
158     return Name->getValue() == "NAME"
159                ? VarInit::get(ArgName, StringRecTy::get(Records))
160                : nullptr;
161   };
162 
163   // If not found, we try to find the variable in additional variables like
164   // arguments, loop iterator, etc.
165   switch (Kind) {
166   case SK_Local:
167     break; /* do nothing. */
168   case SK_Record: {
169     if (CurRec) {
170       // The variable is a record field?
171       if (RecordVal *RV = CurRec->getValue(Name)) {
172         if (TrackReferenceLocs)
173           RV->addReferenceLoc(NameLoc);
174         return VarInit::get(Name, RV->getType());
175       }
176 
177       // The variable is a class template argument?
178       if (CurRec->isClass())
179         if (auto *V = FindValueInArgs(CurRec, Name))
180           return V;
181     }
182     break;
183   }
184   case SK_ForeachLoop: {
185     // The variable is a loop iterator?
186     if (CurLoop->IterVar) {
187       VarInit *IterVar = dyn_cast<VarInit>(CurLoop->IterVar);
188       if (IterVar && IterVar->getNameInit() == Name)
189         return IterVar;
190     }
191     break;
192   }
193   case SK_MultiClass: {
194     // The variable is a multiclass template argument?
195     if (CurMultiClass)
196       if (auto *V = FindValueInArgs(&CurMultiClass->Rec, Name))
197         return V;
198     break;
199   }
200   }
201 
202   // Then, we try to find the name in parent scope.
203   if (Parent)
204     return Parent->getVar(Records, ParsingMultiClass, Name, NameLoc,
205                           TrackReferenceLocs);
206 
207   return nullptr;
208 }
209 
210 bool TGParser::AddValue(Record *CurRec, SMLoc Loc, const RecordVal &RV) {
211   if (!CurRec)
212     CurRec = &CurMultiClass->Rec;
213 
214   if (RecordVal *ERV = CurRec->getValue(RV.getNameInit())) {
215     // The value already exists in the class, treat this as a set.
216     if (ERV->setValue(RV.getValue()))
217       return Error(Loc, "New definition of '" + RV.getName() + "' of type '" +
218                    RV.getType()->getAsString() + "' is incompatible with " +
219                    "previous definition of type '" +
220                    ERV->getType()->getAsString() + "'");
221   } else {
222     CurRec->addValue(RV);
223   }
224   return false;
225 }
226 
227 /// SetValue -
228 /// Return true on error, false on success.
229 bool TGParser::SetValue(Record *CurRec, SMLoc Loc, Init *ValName,
230                         ArrayRef<unsigned> BitList, Init *V,
231                         bool AllowSelfAssignment, bool OverrideDefLoc) {
232   if (!V) return false;
233 
234   if (!CurRec) CurRec = &CurMultiClass->Rec;
235 
236   RecordVal *RV = CurRec->getValue(ValName);
237   if (!RV)
238     return Error(Loc, "Value '" + ValName->getAsUnquotedString() +
239                  "' unknown!");
240 
241   // Do not allow assignments like 'X = X'.  This will just cause infinite loops
242   // in the resolution machinery.
243   if (BitList.empty())
244     if (VarInit *VI = dyn_cast<VarInit>(V))
245       if (VI->getNameInit() == ValName && !AllowSelfAssignment)
246         return Error(Loc, "Recursion / self-assignment forbidden");
247 
248   // If we are assigning to a subset of the bits in the value... then we must be
249   // assigning to a field of BitsRecTy, which must have a BitsInit
250   // initializer.
251   //
252   if (!BitList.empty()) {
253     BitsInit *CurVal = dyn_cast<BitsInit>(RV->getValue());
254     if (!CurVal)
255       return Error(Loc, "Value '" + ValName->getAsUnquotedString() +
256                    "' is not a bits type");
257 
258     // Convert the incoming value to a bits type of the appropriate size...
259     Init *BI = V->getCastTo(BitsRecTy::get(Records, BitList.size()));
260     if (!BI)
261       return Error(Loc, "Initializer is not compatible with bit range");
262 
263     SmallVector<Init *, 16> NewBits(CurVal->getNumBits());
264 
265     // Loop over bits, assigning values as appropriate.
266     for (unsigned i = 0, e = BitList.size(); i != e; ++i) {
267       unsigned Bit = BitList[i];
268       if (NewBits[Bit])
269         return Error(Loc, "Cannot set bit #" + Twine(Bit) + " of value '" +
270                      ValName->getAsUnquotedString() + "' more than once");
271       NewBits[Bit] = BI->getBit(i);
272     }
273 
274     for (unsigned i = 0, e = CurVal->getNumBits(); i != e; ++i)
275       if (!NewBits[i])
276         NewBits[i] = CurVal->getBit(i);
277 
278     V = BitsInit::get(Records, NewBits);
279   }
280 
281   if (OverrideDefLoc ? RV->setValue(V, Loc) : RV->setValue(V)) {
282     std::string InitType;
283     if (BitsInit *BI = dyn_cast<BitsInit>(V))
284       InitType = (Twine("' of type bit initializer with length ") +
285                   Twine(BI->getNumBits())).str();
286     else if (TypedInit *TI = dyn_cast<TypedInit>(V))
287       InitType = (Twine("' of type '") + TI->getType()->getAsString()).str();
288     return Error(Loc, "Field '" + ValName->getAsUnquotedString() +
289                           "' of type '" + RV->getType()->getAsString() +
290                           "' is incompatible with value '" +
291                           V->getAsString() + InitType + "'");
292   }
293   return false;
294 }
295 
296 /// AddSubClass - Add SubClass as a subclass to CurRec, resolving its template
297 /// args as SubClass's template arguments.
298 bool TGParser::AddSubClass(Record *CurRec, SubClassReference &SubClass) {
299   Record *SC = SubClass.Rec;
300   MapResolver R(CurRec);
301 
302   // Loop over all the subclass record's fields. Add regular fields to the new
303   // record.
304   for (const RecordVal &Field : SC->getValues())
305     if (!Field.isTemplateArg())
306       if (AddValue(CurRec, SubClass.RefRange.Start, Field))
307         return true;
308 
309   if (resolveArgumentsOfClass(R, SC, SubClass.TemplateArgs,
310                               SubClass.RefRange.Start))
311     return true;
312 
313   // Copy the subclass record's assertions to the new record.
314   CurRec->appendAssertions(SC);
315 
316   // Copy the subclass record's dumps to the new record.
317   CurRec->appendDumps(SC);
318 
319   Init *Name;
320   if (CurRec->isClass())
321     Name = VarInit::get(QualifiedNameOfImplicitName(*CurRec),
322                         StringRecTy::get(Records));
323   else
324     Name = CurRec->getNameInit();
325   R.set(QualifiedNameOfImplicitName(*SC), Name);
326 
327   CurRec->resolveReferences(R);
328 
329   // Since everything went well, we can now set the "superclass" list for the
330   // current record.
331   ArrayRef<std::pair<Record *, SMRange>> SCs = SC->getSuperClasses();
332   for (const auto &SCPair : SCs) {
333     if (CurRec->isSubClassOf(SCPair.first))
334       return Error(SubClass.RefRange.Start,
335                    "Already subclass of '" + SCPair.first->getName() + "'!\n");
336     CurRec->addSuperClass(SCPair.first, SCPair.second);
337   }
338 
339   if (CurRec->isSubClassOf(SC))
340     return Error(SubClass.RefRange.Start,
341                  "Already subclass of '" + SC->getName() + "'!\n");
342   CurRec->addSuperClass(SC, SubClass.RefRange);
343   return false;
344 }
345 
346 bool TGParser::AddSubClass(RecordsEntry &Entry, SubClassReference &SubClass) {
347   if (Entry.Rec)
348     return AddSubClass(Entry.Rec.get(), SubClass);
349 
350   if (Entry.Assertion)
351     return false;
352 
353   for (auto &E : Entry.Loop->Entries) {
354     if (AddSubClass(E, SubClass))
355       return true;
356   }
357 
358   return false;
359 }
360 
361 /// AddSubMultiClass - Add SubMultiClass as a subclass to
362 /// CurMC, resolving its template args as SubMultiClass's
363 /// template arguments.
364 bool TGParser::AddSubMultiClass(MultiClass *CurMC,
365                                 SubMultiClassReference &SubMultiClass) {
366   MultiClass *SMC = SubMultiClass.MC;
367 
368   SubstStack Substs;
369   if (resolveArgumentsOfMultiClass(
370           Substs, SMC, SubMultiClass.TemplateArgs,
371           VarInit::get(QualifiedNameOfImplicitName(CurMC),
372                        StringRecTy::get(Records)),
373           SubMultiClass.RefRange.Start))
374     return true;
375 
376   // Add all of the defs in the subclass into the current multiclass.
377   return resolve(SMC->Entries, Substs, false, &CurMC->Entries);
378 }
379 
380 /// Add a record, foreach loop, or assertion to the current context.
381 bool TGParser::addEntry(RecordsEntry E) {
382   assert((!!E.Rec + !!E.Loop + !!E.Assertion + !!E.Dump) == 1 &&
383          "RecordsEntry has invalid number of items");
384 
385   // If we are parsing a loop, add it to the loop's entries.
386   if (!Loops.empty()) {
387     Loops.back()->Entries.push_back(std::move(E));
388     return false;
389   }
390 
391   // If it is a loop, then resolve and perform the loop.
392   if (E.Loop) {
393     SubstStack Stack;
394     return resolve(*E.Loop, Stack, CurMultiClass == nullptr,
395                    CurMultiClass ? &CurMultiClass->Entries : nullptr);
396   }
397 
398   // If we are parsing a multiclass, add it to the multiclass's entries.
399   if (CurMultiClass) {
400     CurMultiClass->Entries.push_back(std::move(E));
401     return false;
402   }
403 
404   // If it is an assertion, then it's a top-level one, so check it.
405   if (E.Assertion) {
406     CheckAssert(E.Assertion->Loc, E.Assertion->Condition, E.Assertion->Message);
407     return false;
408   }
409 
410   if (E.Dump) {
411     dumpMessage(E.Dump->Loc, E.Dump->Message);
412     return false;
413   }
414 
415   // It must be a record, so finish it off.
416   return addDefOne(std::move(E.Rec));
417 }
418 
419 /// Resolve the entries in \p Loop, going over inner loops recursively
420 /// and making the given subsitutions of (name, value) pairs.
421 ///
422 /// The resulting records are stored in \p Dest if non-null. Otherwise, they
423 /// are added to the global record keeper.
424 bool TGParser::resolve(const ForeachLoop &Loop, SubstStack &Substs,
425                        bool Final, std::vector<RecordsEntry> *Dest,
426                        SMLoc *Loc) {
427 
428   MapResolver R;
429   for (const auto &S : Substs)
430     R.set(S.first, S.second);
431   Init *List = Loop.ListValue->resolveReferences(R);
432 
433   // For if-then-else blocks, we lower to a foreach loop whose list is a
434   // ternary selection between lists of different length.  Since we don't
435   // have a means to track variable length record lists, we *must* resolve
436   // the condition here.  We want to defer final resolution of the arms
437   // until the resulting records are finalized.
438   // e.g. !if(!exists<SchedWrite>("__does_not_exist__"), [1], [])
439   if (auto *TI = dyn_cast<TernOpInit>(List);
440       TI && TI->getOpcode() == TernOpInit::IF && Final) {
441     Init *OldLHS = TI->getLHS();
442     R.setFinal(true);
443     Init *LHS = OldLHS->resolveReferences(R);
444     if (LHS == OldLHS) {
445       PrintError(Loop.Loc,
446                  Twine("unable to resolve if condition '") +
447                  LHS->getAsString() + "' at end of containing scope");
448       return true;
449     }
450     Init *MHS = TI->getMHS();
451     Init *RHS = TI->getRHS();
452     List = TernOpInit::get(TernOpInit::IF, LHS, MHS, RHS, TI->getType())
453       ->Fold(nullptr);
454   }
455 
456   auto LI = dyn_cast<ListInit>(List);
457   if (!LI) {
458     if (!Final) {
459       Dest->emplace_back(std::make_unique<ForeachLoop>(Loop.Loc, Loop.IterVar,
460                                                   List));
461       return resolve(Loop.Entries, Substs, Final, &Dest->back().Loop->Entries,
462                      Loc);
463     }
464 
465     PrintError(Loop.Loc, Twine("attempting to loop over '") +
466                               List->getAsString() + "', expected a list");
467     return true;
468   }
469 
470   bool Error = false;
471   for (auto *Elt : *LI) {
472     if (Loop.IterVar)
473       Substs.emplace_back(Loop.IterVar->getNameInit(), Elt);
474     Error = resolve(Loop.Entries, Substs, Final, Dest);
475     if (Loop.IterVar)
476       Substs.pop_back();
477     if (Error)
478       break;
479   }
480   return Error;
481 }
482 
483 /// Resolve the entries in \p Source, going over loops recursively and
484 /// making the given substitutions of (name, value) pairs.
485 ///
486 /// The resulting records are stored in \p Dest if non-null. Otherwise, they
487 /// are added to the global record keeper.
488 bool TGParser::resolve(const std::vector<RecordsEntry> &Source,
489                        SubstStack &Substs, bool Final,
490                        std::vector<RecordsEntry> *Dest, SMLoc *Loc) {
491   bool Error = false;
492   for (auto &E : Source) {
493     if (E.Loop) {
494       Error = resolve(*E.Loop, Substs, Final, Dest);
495 
496     } else if (E.Assertion) {
497       MapResolver R;
498       for (const auto &S : Substs)
499         R.set(S.first, S.second);
500       Init *Condition = E.Assertion->Condition->resolveReferences(R);
501       Init *Message = E.Assertion->Message->resolveReferences(R);
502 
503       if (Dest)
504         Dest->push_back(std::make_unique<Record::AssertionInfo>(
505             E.Assertion->Loc, Condition, Message));
506       else
507         CheckAssert(E.Assertion->Loc, Condition, Message);
508 
509     } else if (E.Dump) {
510       MapResolver R;
511       for (const auto &S : Substs)
512         R.set(S.first, S.second);
513       Init *Message = E.Dump->Message->resolveReferences(R);
514 
515       if (Dest)
516         Dest->push_back(
517             std::make_unique<Record::DumpInfo>(E.Dump->Loc, Message));
518       else
519         dumpMessage(E.Dump->Loc, Message);
520 
521     } else {
522       auto Rec = std::make_unique<Record>(*E.Rec);
523       if (Loc)
524         Rec->appendLoc(*Loc);
525 
526       MapResolver R(Rec.get());
527       for (const auto &S : Substs)
528         R.set(S.first, S.second);
529       Rec->resolveReferences(R);
530 
531       if (Dest)
532         Dest->push_back(std::move(Rec));
533       else
534         Error = addDefOne(std::move(Rec));
535     }
536     if (Error)
537       break;
538   }
539   return Error;
540 }
541 
542 /// Resolve the record fully and add it to the record keeper.
543 bool TGParser::addDefOne(std::unique_ptr<Record> Rec) {
544   Init *NewName = nullptr;
545   if (Record *Prev = Records.getDef(Rec->getNameInitAsString())) {
546     if (!Rec->isAnonymous()) {
547       PrintError(Rec->getLoc(),
548                  "def already exists: " + Rec->getNameInitAsString());
549       PrintNote(Prev->getLoc(), "location of previous definition");
550       return true;
551     }
552     NewName = Records.getNewAnonymousName();
553   }
554 
555   Rec->resolveReferences(NewName);
556   checkConcrete(*Rec);
557 
558   if (!isa<StringInit>(Rec->getNameInit())) {
559     PrintError(Rec->getLoc(), Twine("record name '") +
560                                   Rec->getNameInit()->getAsString() +
561                                   "' could not be fully resolved");
562     return true;
563   }
564 
565   // Check the assertions.
566   Rec->checkRecordAssertions();
567 
568   // Run the dumps.
569   Rec->emitRecordDumps();
570 
571   // If ObjectBody has template arguments, it's an error.
572   assert(Rec->getTemplateArgs().empty() && "How'd this get template args?");
573 
574   for (DefsetRecord *Defset : Defsets) {
575     DefInit *I = Rec->getDefInit();
576     if (!I->getType()->typeIsA(Defset->EltTy)) {
577       PrintError(Rec->getLoc(), Twine("adding record of incompatible type '") +
578                                     I->getType()->getAsString() +
579                                      "' to defset");
580       PrintNote(Defset->Loc, "location of defset declaration");
581       return true;
582     }
583     Defset->Elements.push_back(I);
584   }
585 
586   Records.addDef(std::move(Rec));
587   return false;
588 }
589 
590 bool TGParser::resolveArguments(Record *Rec, ArrayRef<ArgumentInit *> ArgValues,
591                                 SMLoc Loc, ArgValueHandler ArgValueHandler) {
592   ArrayRef<Init *> ArgNames = Rec->getTemplateArgs();
593   assert(ArgValues.size() <= ArgNames.size() &&
594          "Too many template arguments allowed");
595 
596   // Loop over the template arguments and handle the (name, value) pair.
597   SmallVector<Init *, 2> UnsolvedArgNames(ArgNames);
598   for (auto *Arg : ArgValues) {
599     Init *ArgName = nullptr;
600     Init *ArgValue = Arg->getValue();
601     if (Arg->isPositional())
602       ArgName = ArgNames[Arg->getIndex()];
603     if (Arg->isNamed())
604       ArgName = Arg->getName();
605 
606     // We can only specify the template argument once.
607     if (!is_contained(UnsolvedArgNames, ArgName))
608       return Error(Loc, "We can only specify the template argument '" +
609                             ArgName->getAsUnquotedString() + "' once");
610 
611     ArgValueHandler(ArgName, ArgValue);
612     llvm::erase(UnsolvedArgNames, ArgName);
613   }
614 
615   // For unsolved arguments, if there is no default value, complain.
616   for (auto *UnsolvedArgName : UnsolvedArgNames) {
617     Init *Default = Rec->getValue(UnsolvedArgName)->getValue();
618     if (!Default->isComplete()) {
619       std::string Name = UnsolvedArgName->getAsUnquotedString();
620       Error(Loc, "value not specified for template argument '" + Name + "'");
621       PrintNote(Rec->getFieldLoc(Name),
622                 "declared in '" + Rec->getNameInitAsString() + "'");
623       return true;
624     }
625     ArgValueHandler(UnsolvedArgName, Default);
626   }
627 
628   return false;
629 }
630 
631 /// Resolve the arguments of class and set them to MapResolver.
632 /// Returns true if failed.
633 bool TGParser::resolveArgumentsOfClass(MapResolver &R, Record *Rec,
634                                        ArrayRef<ArgumentInit *> ArgValues,
635                                        SMLoc Loc) {
636   return resolveArguments(Rec, ArgValues, Loc,
637                           [&](Init *Name, Init *Value) { R.set(Name, Value); });
638 }
639 
640 /// Resolve the arguments of multiclass and store them into SubstStack.
641 /// Returns true if failed.
642 bool TGParser::resolveArgumentsOfMultiClass(SubstStack &Substs, MultiClass *MC,
643                                             ArrayRef<ArgumentInit *> ArgValues,
644                                             Init *DefmName, SMLoc Loc) {
645   // Add an implicit argument NAME.
646   Substs.emplace_back(QualifiedNameOfImplicitName(MC), DefmName);
647   return resolveArguments(
648       &MC->Rec, ArgValues, Loc,
649       [&](Init *Name, Init *Value) { Substs.emplace_back(Name, Value); });
650 }
651 
652 //===----------------------------------------------------------------------===//
653 // Parser Code
654 //===----------------------------------------------------------------------===//
655 
656 bool TGParser::consume(tgtok::TokKind K) {
657   if (Lex.getCode() == K) {
658     Lex.Lex();
659     return true;
660   }
661   return false;
662 }
663 
664 /// ParseObjectName - If a valid object name is specified, return it. If no
665 /// name is specified, return the unset initializer. Return nullptr on parse
666 /// error.
667 ///   ObjectName ::= Value [ '#' Value ]*
668 ///   ObjectName ::= /*empty*/
669 ///
670 Init *TGParser::ParseObjectName(MultiClass *CurMultiClass) {
671   switch (Lex.getCode()) {
672   case tgtok::colon:
673   case tgtok::semi:
674   case tgtok::l_brace:
675     // These are all of the tokens that can begin an object body.
676     // Some of these can also begin values but we disallow those cases
677     // because they are unlikely to be useful.
678     return UnsetInit::get(Records);
679   default:
680     break;
681   }
682 
683   Record *CurRec = nullptr;
684   if (CurMultiClass)
685     CurRec = &CurMultiClass->Rec;
686 
687   Init *Name = ParseValue(CurRec, StringRecTy::get(Records), ParseNameMode);
688   if (!Name)
689     return nullptr;
690 
691   if (CurMultiClass) {
692     Init *NameStr = QualifiedNameOfImplicitName(CurMultiClass);
693     HasReferenceResolver R(NameStr);
694     Name->resolveReferences(R);
695     if (!R.found())
696       Name = BinOpInit::getStrConcat(
697           VarInit::get(NameStr, StringRecTy::get(Records)), Name);
698   }
699 
700   return Name;
701 }
702 
703 /// ParseClassID - Parse and resolve a reference to a class name.  This returns
704 /// null on error.
705 ///
706 ///    ClassID ::= ID
707 ///
708 Record *TGParser::ParseClassID() {
709   if (Lex.getCode() != tgtok::Id) {
710     TokError("expected name for ClassID");
711     return nullptr;
712   }
713 
714   Record *Result = Records.getClass(Lex.getCurStrVal());
715   if (!Result) {
716     std::string Msg("Couldn't find class '" + Lex.getCurStrVal() + "'");
717     if (MultiClasses[Lex.getCurStrVal()].get())
718       TokError(Msg + ". Use 'defm' if you meant to use multiclass '" +
719                Lex.getCurStrVal() + "'");
720     else
721       TokError(Msg);
722   } else if (TrackReferenceLocs) {
723     Result->appendReferenceLoc(Lex.getLocRange());
724   }
725 
726   Lex.Lex();
727   return Result;
728 }
729 
730 /// ParseMultiClassID - Parse and resolve a reference to a multiclass name.
731 /// This returns null on error.
732 ///
733 ///    MultiClassID ::= ID
734 ///
735 MultiClass *TGParser::ParseMultiClassID() {
736   if (Lex.getCode() != tgtok::Id) {
737     TokError("expected name for MultiClassID");
738     return nullptr;
739   }
740 
741   MultiClass *Result = MultiClasses[Lex.getCurStrVal()].get();
742   if (!Result)
743     TokError("Couldn't find multiclass '" + Lex.getCurStrVal() + "'");
744 
745   Lex.Lex();
746   return Result;
747 }
748 
749 /// ParseSubClassReference - Parse a reference to a subclass or a
750 /// multiclass. This returns a SubClassRefTy with a null Record* on error.
751 ///
752 ///  SubClassRef ::= ClassID
753 ///  SubClassRef ::= ClassID '<' ArgValueList '>'
754 ///
755 SubClassReference TGParser::
756 ParseSubClassReference(Record *CurRec, bool isDefm) {
757   SubClassReference Result;
758   Result.RefRange.Start = Lex.getLoc();
759 
760   if (isDefm) {
761     if (MultiClass *MC = ParseMultiClassID())
762       Result.Rec = &MC->Rec;
763   } else {
764     Result.Rec = ParseClassID();
765   }
766   if (!Result.Rec) return Result;
767 
768   // If there is no template arg list, we're done.
769   if (!consume(tgtok::less)) {
770     Result.RefRange.End = Lex.getLoc();
771     return Result;
772   }
773 
774   if (ParseTemplateArgValueList(Result.TemplateArgs, CurRec, Result.Rec)) {
775     Result.Rec = nullptr; // Error parsing value list.
776     return Result;
777   }
778 
779   if (CheckTemplateArgValues(Result.TemplateArgs, Result.RefRange.Start,
780                              Result.Rec)) {
781     Result.Rec = nullptr; // Error checking value list.
782     return Result;
783   }
784 
785   Result.RefRange.End = Lex.getLoc();
786   return Result;
787 }
788 
789 /// ParseSubMultiClassReference - Parse a reference to a subclass or to a
790 /// templated submulticlass.  This returns a SubMultiClassRefTy with a null
791 /// Record* on error.
792 ///
793 ///  SubMultiClassRef ::= MultiClassID
794 ///  SubMultiClassRef ::= MultiClassID '<' ArgValueList '>'
795 ///
796 SubMultiClassReference TGParser::
797 ParseSubMultiClassReference(MultiClass *CurMC) {
798   SubMultiClassReference Result;
799   Result.RefRange.Start = Lex.getLoc();
800 
801   Result.MC = ParseMultiClassID();
802   if (!Result.MC) return Result;
803 
804   // If there is no template arg list, we're done.
805   if (!consume(tgtok::less)) {
806     Result.RefRange.End = Lex.getLoc();
807     return Result;
808   }
809 
810   if (ParseTemplateArgValueList(Result.TemplateArgs, &CurMC->Rec,
811                                 &Result.MC->Rec)) {
812     Result.MC = nullptr; // Error parsing value list.
813     return Result;
814   }
815 
816   Result.RefRange.End = Lex.getLoc();
817 
818   return Result;
819 }
820 
821 /// ParseSliceElement - Parse subscript or range
822 ///
823 ///  SliceElement  ::= Value<list<int>>
824 ///  SliceElement  ::= Value<int>
825 ///  SliceElement  ::= Value<int> '...' Value<int>
826 ///  SliceElement  ::= Value<int> '-' Value<int> (deprecated)
827 ///  SliceElement  ::= Value<int> INTVAL(Negative; deprecated)
828 ///
829 /// SliceElement is either IntRecTy, ListRecTy, or nullptr
830 ///
831 TypedInit *TGParser::ParseSliceElement(Record *CurRec) {
832   auto LHSLoc = Lex.getLoc();
833   auto *CurVal = ParseValue(CurRec);
834   if (!CurVal)
835     return nullptr;
836   auto *LHS = cast<TypedInit>(CurVal);
837 
838   TypedInit *RHS = nullptr;
839   switch (Lex.getCode()) {
840   case tgtok::dotdotdot:
841   case tgtok::minus: { // Deprecated
842     Lex.Lex();         // eat
843     auto RHSLoc = Lex.getLoc();
844     CurVal = ParseValue(CurRec);
845     if (!CurVal)
846       return nullptr;
847     RHS = cast<TypedInit>(CurVal);
848     if (!isa<IntRecTy>(RHS->getType())) {
849       Error(RHSLoc,
850             "expected int...int, got " + Twine(RHS->getType()->getAsString()));
851       return nullptr;
852     }
853     break;
854   }
855   case tgtok::IntVal: { // Deprecated "-num"
856     auto i = -Lex.getCurIntVal();
857     if (i < 0) {
858       TokError("invalid range, cannot be negative");
859       return nullptr;
860     }
861     RHS = IntInit::get(Records, i);
862     Lex.Lex(); // eat IntVal
863     break;
864   }
865   default: // Single value (IntRecTy or ListRecTy)
866     return LHS;
867   }
868 
869   assert(RHS);
870   assert(isa<IntRecTy>(RHS->getType()));
871 
872   // Closed-interval range <LHS:IntRecTy>...<RHS:IntRecTy>
873   if (!isa<IntRecTy>(LHS->getType())) {
874     Error(LHSLoc,
875           "expected int...int, got " + Twine(LHS->getType()->getAsString()));
876     return nullptr;
877   }
878 
879   return cast<TypedInit>(BinOpInit::get(BinOpInit::RANGEC, LHS, RHS,
880                                         IntRecTy::get(Records)->getListTy())
881                              ->Fold(CurRec));
882 }
883 
884 /// ParseSliceElements - Parse subscripts in square brackets.
885 ///
886 ///  SliceElements ::= ( SliceElement ',' )* SliceElement ','?
887 ///
888 /// SliceElement is either IntRecTy, ListRecTy, or nullptr
889 ///
890 /// Returns ListRecTy by defaut.
891 /// Returns IntRecTy if;
892 ///  - Single=true
893 ///  - SliceElements is Value<int> w/o trailing comma
894 ///
895 TypedInit *TGParser::ParseSliceElements(Record *CurRec, bool Single) {
896   TypedInit *CurVal;
897   SmallVector<Init *, 2> Elems;       // int
898   SmallVector<TypedInit *, 2> Slices; // list<int>
899 
900   auto FlushElems = [&] {
901     if (!Elems.empty()) {
902       Slices.push_back(ListInit::get(Elems, IntRecTy::get(Records)));
903       Elems.clear();
904     }
905   };
906 
907   do {
908     auto LHSLoc = Lex.getLoc();
909     CurVal = ParseSliceElement(CurRec);
910     if (!CurVal)
911       return nullptr;
912     auto *CurValTy = CurVal->getType();
913 
914     if (auto *ListValTy = dyn_cast<ListRecTy>(CurValTy)) {
915       if (!isa<IntRecTy>(ListValTy->getElementType())) {
916         Error(LHSLoc,
917               "expected list<int>, got " + Twine(ListValTy->getAsString()));
918         return nullptr;
919       }
920 
921       FlushElems();
922       Slices.push_back(CurVal);
923       Single = false;
924       CurVal = nullptr;
925     } else if (!isa<IntRecTy>(CurValTy)) {
926       Error(LHSLoc,
927             "unhandled type " + Twine(CurValTy->getAsString()) + " in range");
928       return nullptr;
929     }
930 
931     if (Lex.getCode() != tgtok::comma)
932       break;
933 
934     Lex.Lex(); // eat comma
935 
936     // `[i,]` is not LISTELEM but LISTSLICE
937     Single = false;
938     if (CurVal)
939       Elems.push_back(CurVal);
940     CurVal = nullptr;
941   } while (Lex.getCode() != tgtok::r_square);
942 
943   if (CurVal) {
944     // LISTELEM
945     if (Single)
946       return CurVal;
947 
948     Elems.push_back(CurVal);
949   }
950 
951   FlushElems();
952 
953   // Concatenate lists in Slices
954   TypedInit *Result = nullptr;
955   for (auto *Slice : Slices) {
956     Result = (Result ? cast<TypedInit>(BinOpInit::getListConcat(Result, Slice))
957                      : Slice);
958   }
959 
960   return Result;
961 }
962 
963 /// ParseRangePiece - Parse a bit/value range.
964 ///   RangePiece ::= INTVAL
965 ///   RangePiece ::= INTVAL '...' INTVAL
966 ///   RangePiece ::= INTVAL '-' INTVAL
967 ///   RangePiece ::= INTVAL INTVAL
968 // The last two forms are deprecated.
969 bool TGParser::ParseRangePiece(SmallVectorImpl<unsigned> &Ranges,
970                                TypedInit *FirstItem) {
971   Init *CurVal = FirstItem;
972   if (!CurVal)
973     CurVal = ParseValue(nullptr);
974 
975   IntInit *II = dyn_cast_or_null<IntInit>(CurVal);
976   if (!II)
977     return TokError("expected integer or bitrange");
978 
979   int64_t Start = II->getValue();
980   int64_t End;
981 
982   if (Start < 0)
983     return TokError("invalid range, cannot be negative");
984 
985   switch (Lex.getCode()) {
986   default:
987     Ranges.push_back(Start);
988     return false;
989 
990   case tgtok::dotdotdot:
991   case tgtok::minus: {
992     Lex.Lex(); // eat
993 
994     Init *I_End = ParseValue(nullptr);
995     IntInit *II_End = dyn_cast_or_null<IntInit>(I_End);
996     if (!II_End) {
997       TokError("expected integer value as end of range");
998       return true;
999     }
1000 
1001     End = II_End->getValue();
1002     break;
1003   }
1004   case tgtok::IntVal: {
1005     End = -Lex.getCurIntVal();
1006     Lex.Lex();
1007     break;
1008   }
1009   }
1010   if (End < 0)
1011     return TokError("invalid range, cannot be negative");
1012 
1013   // Add to the range.
1014   if (Start < End)
1015     for (; Start <= End; ++Start)
1016       Ranges.push_back(Start);
1017   else
1018     for (; Start >= End; --Start)
1019       Ranges.push_back(Start);
1020   return false;
1021 }
1022 
1023 /// ParseRangeList - Parse a list of scalars and ranges into scalar values.
1024 ///
1025 ///   RangeList ::= RangePiece (',' RangePiece)*
1026 ///
1027 void TGParser::ParseRangeList(SmallVectorImpl<unsigned> &Result) {
1028   // Parse the first piece.
1029   if (ParseRangePiece(Result)) {
1030     Result.clear();
1031     return;
1032   }
1033   while (consume(tgtok::comma))
1034     // Parse the next range piece.
1035     if (ParseRangePiece(Result)) {
1036       Result.clear();
1037       return;
1038     }
1039 }
1040 
1041 /// ParseOptionalRangeList - Parse either a range list in <>'s or nothing.
1042 ///   OptionalRangeList ::= '<' RangeList '>'
1043 ///   OptionalRangeList ::= /*empty*/
1044 bool TGParser::ParseOptionalRangeList(SmallVectorImpl<unsigned> &Ranges) {
1045   SMLoc StartLoc = Lex.getLoc();
1046   if (!consume(tgtok::less))
1047     return false;
1048 
1049   // Parse the range list.
1050   ParseRangeList(Ranges);
1051   if (Ranges.empty()) return true;
1052 
1053   if (!consume(tgtok::greater)) {
1054     TokError("expected '>' at end of range list");
1055     return Error(StartLoc, "to match this '<'");
1056   }
1057   return false;
1058 }
1059 
1060 /// ParseOptionalBitList - Parse either a bit list in {}'s or nothing.
1061 ///   OptionalBitList ::= '{' RangeList '}'
1062 ///   OptionalBitList ::= /*empty*/
1063 bool TGParser::ParseOptionalBitList(SmallVectorImpl<unsigned> &Ranges) {
1064   SMLoc StartLoc = Lex.getLoc();
1065   if (!consume(tgtok::l_brace))
1066     return false;
1067 
1068   // Parse the range list.
1069   ParseRangeList(Ranges);
1070   if (Ranges.empty()) return true;
1071 
1072   if (!consume(tgtok::r_brace)) {
1073     TokError("expected '}' at end of bit list");
1074     return Error(StartLoc, "to match this '{'");
1075   }
1076   return false;
1077 }
1078 
1079 /// ParseType - Parse and return a tblgen type.  This returns null on error.
1080 ///
1081 ///   Type ::= STRING                       // string type
1082 ///   Type ::= CODE                         // code type
1083 ///   Type ::= BIT                          // bit type
1084 ///   Type ::= BITS '<' INTVAL '>'          // bits<x> type
1085 ///   Type ::= INT                          // int type
1086 ///   Type ::= LIST '<' Type '>'            // list<x> type
1087 ///   Type ::= DAG                          // dag type
1088 ///   Type ::= ClassID                      // Record Type
1089 ///
1090 RecTy *TGParser::ParseType() {
1091   switch (Lex.getCode()) {
1092   default: TokError("Unknown token when expecting a type"); return nullptr;
1093   case tgtok::String:
1094   case tgtok::Code:
1095     Lex.Lex();
1096     return StringRecTy::get(Records);
1097   case tgtok::Bit:
1098     Lex.Lex();
1099     return BitRecTy::get(Records);
1100   case tgtok::Int:
1101     Lex.Lex();
1102     return IntRecTy::get(Records);
1103   case tgtok::Dag:
1104     Lex.Lex();
1105     return DagRecTy::get(Records);
1106   case tgtok::Id: {
1107     auto I = TypeAliases.find(Lex.getCurStrVal());
1108     if (I != TypeAliases.end()) {
1109       Lex.Lex();
1110       return I->second;
1111     }
1112     if (Record *R = ParseClassID())
1113       return RecordRecTy::get(R);
1114     TokError("unknown class name");
1115     return nullptr;
1116   }
1117   case tgtok::Bits: {
1118     if (Lex.Lex() != tgtok::less) { // Eat 'bits'
1119       TokError("expected '<' after bits type");
1120       return nullptr;
1121     }
1122     if (Lex.Lex() != tgtok::IntVal) { // Eat '<'
1123       TokError("expected integer in bits<n> type");
1124       return nullptr;
1125     }
1126     uint64_t Val = Lex.getCurIntVal();
1127     if (Lex.Lex() != tgtok::greater) { // Eat count.
1128       TokError("expected '>' at end of bits<n> type");
1129       return nullptr;
1130     }
1131     Lex.Lex();  // Eat '>'
1132     return BitsRecTy::get(Records, Val);
1133   }
1134   case tgtok::List: {
1135     if (Lex.Lex() != tgtok::less) { // Eat 'bits'
1136       TokError("expected '<' after list type");
1137       return nullptr;
1138     }
1139     Lex.Lex();  // Eat '<'
1140     RecTy *SubType = ParseType();
1141     if (!SubType) return nullptr;
1142 
1143     if (!consume(tgtok::greater)) {
1144       TokError("expected '>' at end of list<ty> type");
1145       return nullptr;
1146     }
1147     return ListRecTy::get(SubType);
1148   }
1149   }
1150 }
1151 
1152 /// ParseIDValue
1153 Init *TGParser::ParseIDValue(Record *CurRec, StringInit *Name, SMRange NameLoc,
1154                              IDParseMode Mode) {
1155   if (Init *I = CurScope->getVar(Records, CurMultiClass, Name, NameLoc,
1156                                  TrackReferenceLocs))
1157     return I;
1158 
1159   if (Mode == ParseNameMode)
1160     return Name;
1161 
1162   if (Init *I = Records.getGlobal(Name->getValue())) {
1163     // Add a reference to the global if it's a record.
1164     if (TrackReferenceLocs) {
1165       if (auto *Def = dyn_cast<DefInit>(I))
1166         Def->getDef()->appendReferenceLoc(NameLoc);
1167     }
1168     return I;
1169   }
1170 
1171   // Allow self-references of concrete defs, but delay the lookup so that we
1172   // get the correct type.
1173   if (CurRec && !CurRec->isClass() && !CurMultiClass &&
1174       CurRec->getNameInit() == Name)
1175     return UnOpInit::get(UnOpInit::CAST, Name, CurRec->getType());
1176 
1177   Error(NameLoc.Start, "Variable not defined: '" + Name->getValue() + "'");
1178   return nullptr;
1179 }
1180 
1181 /// ParseOperation - Parse an operator.  This returns null on error.
1182 ///
1183 /// Operation ::= XOperator ['<' Type '>'] '(' Args ')'
1184 ///
1185 Init *TGParser::ParseOperation(Record *CurRec, RecTy *ItemType) {
1186   switch (Lex.getCode()) {
1187   default:
1188     TokError("unknown bang operator");
1189     return nullptr;
1190   case tgtok::XNOT:
1191   case tgtok::XToLower:
1192   case tgtok::XToUpper:
1193   case tgtok::XLOG2:
1194   case tgtok::XHead:
1195   case tgtok::XTail:
1196   case tgtok::XSize:
1197   case tgtok::XEmpty:
1198   case tgtok::XCast:
1199   case tgtok::XRepr:
1200   case tgtok::XGetDagOp: { // Value ::= !unop '(' Value ')'
1201     UnOpInit::UnaryOp Code;
1202     RecTy *Type = nullptr;
1203 
1204     switch (Lex.getCode()) {
1205     default: llvm_unreachable("Unhandled code!");
1206     case tgtok::XCast:
1207       Lex.Lex();  // eat the operation
1208       Code = UnOpInit::CAST;
1209 
1210       Type = ParseOperatorType();
1211 
1212       if (!Type) {
1213         TokError("did not get type for unary operator");
1214         return nullptr;
1215       }
1216 
1217       break;
1218     case tgtok::XRepr:
1219       Lex.Lex(); // eat the operation
1220       Code = UnOpInit::REPR;
1221       Type = StringRecTy::get(Records);
1222       break;
1223     case tgtok::XToLower:
1224       Lex.Lex(); // eat the operation
1225       Code = UnOpInit::TOLOWER;
1226       Type = StringRecTy::get(Records);
1227       break;
1228     case tgtok::XToUpper:
1229       Lex.Lex(); // eat the operation
1230       Code = UnOpInit::TOUPPER;
1231       Type = StringRecTy::get(Records);
1232       break;
1233     case tgtok::XNOT:
1234       Lex.Lex();  // eat the operation
1235       Code = UnOpInit::NOT;
1236       Type = IntRecTy::get(Records);
1237       break;
1238     case tgtok::XLOG2:
1239       Lex.Lex();  // eat the operation
1240       Code = UnOpInit::LOG2;
1241       Type = IntRecTy::get(Records);
1242       break;
1243     case tgtok::XHead:
1244       Lex.Lex();  // eat the operation
1245       Code = UnOpInit::HEAD;
1246       break;
1247     case tgtok::XTail:
1248       Lex.Lex();  // eat the operation
1249       Code = UnOpInit::TAIL;
1250       break;
1251     case tgtok::XSize:
1252       Lex.Lex();
1253       Code = UnOpInit::SIZE;
1254       Type = IntRecTy::get(Records);
1255       break;
1256     case tgtok::XEmpty:
1257       Lex.Lex();  // eat the operation
1258       Code = UnOpInit::EMPTY;
1259       Type = IntRecTy::get(Records);
1260       break;
1261     case tgtok::XGetDagOp:
1262       Lex.Lex();  // eat the operation
1263       if (Lex.getCode() == tgtok::less) {
1264         // Parse an optional type suffix, so that you can say
1265         // !getdagop<BaseClass>(someDag) as a shorthand for
1266         // !cast<BaseClass>(!getdagop(someDag)).
1267         Type = ParseOperatorType();
1268 
1269         if (!Type) {
1270           TokError("did not get type for unary operator");
1271           return nullptr;
1272         }
1273 
1274         if (!isa<RecordRecTy>(Type)) {
1275           TokError("type for !getdagop must be a record type");
1276           // but keep parsing, to consume the operand
1277         }
1278       } else {
1279         Type = RecordRecTy::get(Records, {});
1280       }
1281       Code = UnOpInit::GETDAGOP;
1282       break;
1283     }
1284     if (!consume(tgtok::l_paren)) {
1285       TokError("expected '(' after unary operator");
1286       return nullptr;
1287     }
1288 
1289     Init *LHS = ParseValue(CurRec);
1290     if (!LHS) return nullptr;
1291 
1292     if (Code == UnOpInit::EMPTY || Code == UnOpInit::SIZE) {
1293       ListInit *LHSl = dyn_cast<ListInit>(LHS);
1294       StringInit *LHSs = dyn_cast<StringInit>(LHS);
1295       DagInit *LHSd = dyn_cast<DagInit>(LHS);
1296       TypedInit *LHSt = dyn_cast<TypedInit>(LHS);
1297       if (!LHSl && !LHSs && !LHSd && !LHSt) {
1298         TokError("expected string, list, or dag type argument in unary operator");
1299         return nullptr;
1300       }
1301       if (LHSt) {
1302         ListRecTy *LType = dyn_cast<ListRecTy>(LHSt->getType());
1303         StringRecTy *SType = dyn_cast<StringRecTy>(LHSt->getType());
1304         DagRecTy *DType = dyn_cast<DagRecTy>(LHSt->getType());
1305         if (!LType && !SType && !DType) {
1306           TokError("expected string, list, or dag type argument in unary operator");
1307           return nullptr;
1308         }
1309       }
1310     }
1311 
1312     if (Code == UnOpInit::HEAD || Code == UnOpInit::TAIL) {
1313       ListInit *LHSl = dyn_cast<ListInit>(LHS);
1314       TypedInit *LHSt = dyn_cast<TypedInit>(LHS);
1315       if (!LHSl && !LHSt) {
1316         TokError("expected list type argument in unary operator");
1317         return nullptr;
1318       }
1319       if (LHSt) {
1320         ListRecTy *LType = dyn_cast<ListRecTy>(LHSt->getType());
1321         if (!LType) {
1322           TokError("expected list type argument in unary operator");
1323           return nullptr;
1324         }
1325       }
1326 
1327       if (LHSl && LHSl->empty()) {
1328         TokError("empty list argument in unary operator");
1329         return nullptr;
1330       }
1331       if (LHSl) {
1332         Init *Item = LHSl->getElement(0);
1333         TypedInit *Itemt = dyn_cast<TypedInit>(Item);
1334         if (!Itemt) {
1335           TokError("untyped list element in unary operator");
1336           return nullptr;
1337         }
1338         Type = (Code == UnOpInit::HEAD) ? Itemt->getType()
1339                                         : ListRecTy::get(Itemt->getType());
1340       } else {
1341         assert(LHSt && "expected list type argument in unary operator");
1342         ListRecTy *LType = dyn_cast<ListRecTy>(LHSt->getType());
1343         Type = (Code == UnOpInit::HEAD) ? LType->getElementType() : LType;
1344       }
1345     }
1346 
1347     if (!consume(tgtok::r_paren)) {
1348       TokError("expected ')' in unary operator");
1349       return nullptr;
1350     }
1351     return (UnOpInit::get(Code, LHS, Type))->Fold(CurRec);
1352   }
1353 
1354   case tgtok::XIsA: {
1355     // Value ::= !isa '<' Type '>' '(' Value ')'
1356     Lex.Lex(); // eat the operation
1357 
1358     RecTy *Type = ParseOperatorType();
1359     if (!Type)
1360       return nullptr;
1361 
1362     if (!consume(tgtok::l_paren)) {
1363       TokError("expected '(' after type of !isa");
1364       return nullptr;
1365     }
1366 
1367     Init *LHS = ParseValue(CurRec);
1368     if (!LHS)
1369       return nullptr;
1370 
1371     if (!consume(tgtok::r_paren)) {
1372       TokError("expected ')' in !isa");
1373       return nullptr;
1374     }
1375 
1376     return (IsAOpInit::get(Type, LHS))->Fold();
1377   }
1378 
1379   case tgtok::XExists: {
1380     // Value ::= !exists '<' Type '>' '(' Value ')'
1381     Lex.Lex(); // eat the operation
1382 
1383     RecTy *Type = ParseOperatorType();
1384     if (!Type)
1385       return nullptr;
1386 
1387     if (!consume(tgtok::l_paren)) {
1388       TokError("expected '(' after type of !exists");
1389       return nullptr;
1390     }
1391 
1392     SMLoc ExprLoc = Lex.getLoc();
1393     Init *Expr = ParseValue(CurRec);
1394     if (!Expr)
1395       return nullptr;
1396 
1397     TypedInit *ExprType = dyn_cast<TypedInit>(Expr);
1398     if (!ExprType) {
1399       Error(ExprLoc, "expected string type argument in !exists operator");
1400       return nullptr;
1401     }
1402 
1403     RecordRecTy *RecType = dyn_cast<RecordRecTy>(ExprType->getType());
1404     if (RecType) {
1405       Error(ExprLoc,
1406             "expected string type argument in !exists operator, please "
1407             "use !isa instead");
1408       return nullptr;
1409     }
1410 
1411     StringRecTy *SType = dyn_cast<StringRecTy>(ExprType->getType());
1412     if (!SType) {
1413       Error(ExprLoc, "expected string type argument in !exists operator");
1414       return nullptr;
1415     }
1416 
1417     if (!consume(tgtok::r_paren)) {
1418       TokError("expected ')' in !exists");
1419       return nullptr;
1420     }
1421 
1422     return (ExistsOpInit::get(Type, Expr))->Fold(CurRec);
1423   }
1424 
1425   case tgtok::XConcat:
1426   case tgtok::XADD:
1427   case tgtok::XSUB:
1428   case tgtok::XMUL:
1429   case tgtok::XDIV:
1430   case tgtok::XAND:
1431   case tgtok::XOR:
1432   case tgtok::XXOR:
1433   case tgtok::XSRA:
1434   case tgtok::XSRL:
1435   case tgtok::XSHL:
1436   case tgtok::XEq:
1437   case tgtok::XNe:
1438   case tgtok::XLe:
1439   case tgtok::XLt:
1440   case tgtok::XGe:
1441   case tgtok::XGt:
1442   case tgtok::XListConcat:
1443   case tgtok::XListSplat:
1444   case tgtok::XListRemove:
1445   case tgtok::XStrConcat:
1446   case tgtok::XInterleave:
1447   case tgtok::XGetDagArg:
1448   case tgtok::XGetDagName:
1449   case tgtok::XSetDagOp: { // Value ::= !binop '(' Value ',' Value ')'
1450     tgtok::TokKind OpTok = Lex.getCode();
1451     SMLoc OpLoc = Lex.getLoc();
1452     Lex.Lex();  // eat the operation
1453 
1454     BinOpInit::BinaryOp Code;
1455     switch (OpTok) {
1456     default: llvm_unreachable("Unhandled code!");
1457     case tgtok::XConcat: Code = BinOpInit::CONCAT; break;
1458     case tgtok::XADD:    Code = BinOpInit::ADD; break;
1459     case tgtok::XSUB:    Code = BinOpInit::SUB; break;
1460     case tgtok::XMUL:    Code = BinOpInit::MUL; break;
1461     case tgtok::XDIV:    Code = BinOpInit::DIV; break;
1462     case tgtok::XAND:    Code = BinOpInit::AND; break;
1463     case tgtok::XOR:     Code = BinOpInit::OR; break;
1464     case tgtok::XXOR:    Code = BinOpInit::XOR; break;
1465     case tgtok::XSRA:    Code = BinOpInit::SRA; break;
1466     case tgtok::XSRL:    Code = BinOpInit::SRL; break;
1467     case tgtok::XSHL:    Code = BinOpInit::SHL; break;
1468     case tgtok::XEq:     Code = BinOpInit::EQ; break;
1469     case tgtok::XNe:     Code = BinOpInit::NE; break;
1470     case tgtok::XLe:     Code = BinOpInit::LE; break;
1471     case tgtok::XLt:     Code = BinOpInit::LT; break;
1472     case tgtok::XGe:     Code = BinOpInit::GE; break;
1473     case tgtok::XGt:     Code = BinOpInit::GT; break;
1474     case tgtok::XListConcat: Code = BinOpInit::LISTCONCAT; break;
1475     case tgtok::XListSplat:  Code = BinOpInit::LISTSPLAT; break;
1476     case tgtok::XListRemove:
1477       Code = BinOpInit::LISTREMOVE;
1478       break;
1479     case tgtok::XStrConcat:  Code = BinOpInit::STRCONCAT; break;
1480     case tgtok::XInterleave: Code = BinOpInit::INTERLEAVE; break;
1481     case tgtok::XSetDagOp:   Code = BinOpInit::SETDAGOP; break;
1482     case tgtok::XGetDagArg:
1483       Code = BinOpInit::GETDAGARG;
1484       break;
1485     case tgtok::XGetDagName:
1486       Code = BinOpInit::GETDAGNAME;
1487       break;
1488     }
1489 
1490     RecTy *Type = nullptr;
1491     RecTy *ArgType = nullptr;
1492     switch (OpTok) {
1493     default:
1494       llvm_unreachable("Unhandled code!");
1495     case tgtok::XConcat:
1496     case tgtok::XSetDagOp:
1497       Type = DagRecTy::get(Records);
1498       ArgType = DagRecTy::get(Records);
1499       break;
1500     case tgtok::XGetDagArg:
1501       Type = ParseOperatorType();
1502       if (!Type) {
1503         TokError("did not get type for !getdagarg operator");
1504         return nullptr;
1505       }
1506       ArgType = DagRecTy::get(Records);
1507       break;
1508     case tgtok::XGetDagName:
1509       Type = StringRecTy::get(Records);
1510       ArgType = DagRecTy::get(Records);
1511       break;
1512     case tgtok::XAND:
1513     case tgtok::XOR:
1514     case tgtok::XXOR:
1515     case tgtok::XSRA:
1516     case tgtok::XSRL:
1517     case tgtok::XSHL:
1518     case tgtok::XADD:
1519     case tgtok::XSUB:
1520     case tgtok::XMUL:
1521     case tgtok::XDIV:
1522       Type = IntRecTy::get(Records);
1523       ArgType = IntRecTy::get(Records);
1524       break;
1525     case tgtok::XEq:
1526     case tgtok::XNe:
1527     case tgtok::XLe:
1528     case tgtok::XLt:
1529     case tgtok::XGe:
1530     case tgtok::XGt:
1531       Type = BitRecTy::get(Records);
1532       // ArgType for the comparison operators is not yet known.
1533       break;
1534     case tgtok::XListConcat:
1535       // We don't know the list type until we parse the first argument.
1536       ArgType = ItemType;
1537       break;
1538     case tgtok::XListSplat:
1539       // Can't do any typechecking until we parse the first argument.
1540       break;
1541     case tgtok::XListRemove:
1542       // We don't know the list type until we parse the first argument.
1543       ArgType = ItemType;
1544       break;
1545     case tgtok::XStrConcat:
1546       Type = StringRecTy::get(Records);
1547       ArgType = StringRecTy::get(Records);
1548       break;
1549     case tgtok::XInterleave:
1550       Type = StringRecTy::get(Records);
1551       // The first argument type is not yet known.
1552     }
1553 
1554     if (Type && ItemType && !Type->typeIsConvertibleTo(ItemType)) {
1555       Error(OpLoc, Twine("expected value of type '") +
1556                    ItemType->getAsString() + "', got '" +
1557                    Type->getAsString() + "'");
1558       return nullptr;
1559     }
1560 
1561     if (!consume(tgtok::l_paren)) {
1562       TokError("expected '(' after binary operator");
1563       return nullptr;
1564     }
1565 
1566     SmallVector<Init*, 2> InitList;
1567 
1568     // Note that this loop consumes an arbitrary number of arguments.
1569     // The actual count is checked later.
1570     for (;;) {
1571       SMLoc InitLoc = Lex.getLoc();
1572       InitList.push_back(ParseValue(CurRec, ArgType));
1573       if (!InitList.back()) return nullptr;
1574 
1575       TypedInit *InitListBack = dyn_cast<TypedInit>(InitList.back());
1576       if (!InitListBack) {
1577         Error(OpLoc, Twine("expected value to be a typed value, got '" +
1578                            InitList.back()->getAsString() + "'"));
1579         return nullptr;
1580       }
1581       RecTy *ListType = InitListBack->getType();
1582 
1583       if (!ArgType) {
1584         // Argument type must be determined from the argument itself.
1585         ArgType = ListType;
1586 
1587         switch (Code) {
1588         case BinOpInit::LISTCONCAT:
1589           if (!isa<ListRecTy>(ArgType)) {
1590             Error(InitLoc, Twine("expected a list, got value of type '") +
1591                            ArgType->getAsString() + "'");
1592             return nullptr;
1593           }
1594           break;
1595         case BinOpInit::LISTSPLAT:
1596           if (ItemType && InitList.size() == 1) {
1597             if (!isa<ListRecTy>(ItemType)) {
1598               Error(OpLoc,
1599                     Twine("expected output type to be a list, got type '") +
1600                         ItemType->getAsString() + "'");
1601               return nullptr;
1602             }
1603             if (!ArgType->getListTy()->typeIsConvertibleTo(ItemType)) {
1604               Error(OpLoc, Twine("expected first arg type to be '") +
1605                                ArgType->getAsString() +
1606                                "', got value of type '" +
1607                                cast<ListRecTy>(ItemType)
1608                                    ->getElementType()
1609                                    ->getAsString() +
1610                                "'");
1611               return nullptr;
1612             }
1613           }
1614           if (InitList.size() == 2 && !isa<IntRecTy>(ArgType)) {
1615             Error(InitLoc, Twine("expected second parameter to be an int, got "
1616                                  "value of type '") +
1617                                ArgType->getAsString() + "'");
1618             return nullptr;
1619           }
1620           ArgType = nullptr; // Broken invariant: types not identical.
1621           break;
1622         case BinOpInit::LISTREMOVE:
1623           if (!isa<ListRecTy>(ArgType)) {
1624             Error(InitLoc, Twine("expected a list, got value of type '") +
1625                                ArgType->getAsString() + "'");
1626             return nullptr;
1627           }
1628           break;
1629         case BinOpInit::EQ:
1630         case BinOpInit::NE:
1631           if (!ArgType->typeIsConvertibleTo(IntRecTy::get(Records)) &&
1632               !ArgType->typeIsConvertibleTo(StringRecTy::get(Records)) &&
1633               !ArgType->typeIsConvertibleTo(RecordRecTy::get(Records, {}))) {
1634             Error(InitLoc, Twine("expected bit, bits, int, string, or record; "
1635                                  "got value of type '") + ArgType->getAsString() +
1636                                  "'");
1637             return nullptr;
1638           }
1639           break;
1640         case BinOpInit::GETDAGARG: // The 2nd argument of !getdagarg could be
1641                                    // index or name.
1642         case BinOpInit::LE:
1643         case BinOpInit::LT:
1644         case BinOpInit::GE:
1645         case BinOpInit::GT:
1646           if (!ArgType->typeIsConvertibleTo(IntRecTy::get(Records)) &&
1647               !ArgType->typeIsConvertibleTo(StringRecTy::get(Records))) {
1648             Error(InitLoc, Twine("expected bit, bits, int, or string; "
1649                                  "got value of type '") + ArgType->getAsString() +
1650                                  "'");
1651             return nullptr;
1652           }
1653           break;
1654         case BinOpInit::INTERLEAVE:
1655           switch (InitList.size()) {
1656           case 1: // First argument must be a list of strings or integers.
1657             if (ArgType != StringRecTy::get(Records)->getListTy() &&
1658                 !ArgType->typeIsConvertibleTo(
1659                     IntRecTy::get(Records)->getListTy())) {
1660               Error(InitLoc, Twine("expected list of string, int, bits, or bit; "
1661                                    "got value of type '") +
1662                                    ArgType->getAsString() + "'");
1663               return nullptr;
1664             }
1665             break;
1666           case 2: // Second argument must be a string.
1667             if (!isa<StringRecTy>(ArgType)) {
1668               Error(InitLoc, Twine("expected second argument to be a string, "
1669                                    "got value of type '") +
1670                                  ArgType->getAsString() + "'");
1671               return nullptr;
1672             }
1673             break;
1674           default: ;
1675           }
1676           ArgType = nullptr; // Broken invariant: types not identical.
1677           break;
1678         default: llvm_unreachable("other ops have fixed argument types");
1679         }
1680 
1681       } else {
1682         // Desired argument type is a known and in ArgType.
1683         RecTy *Resolved = resolveTypes(ArgType, ListType);
1684         if (!Resolved) {
1685           Error(InitLoc, Twine("expected value of type '") +
1686                              ArgType->getAsString() + "', got '" +
1687                              ListType->getAsString() + "'");
1688           return nullptr;
1689         }
1690         if (Code != BinOpInit::ADD && Code != BinOpInit::SUB &&
1691             Code != BinOpInit::AND && Code != BinOpInit::OR &&
1692             Code != BinOpInit::XOR && Code != BinOpInit::SRA &&
1693             Code != BinOpInit::SRL && Code != BinOpInit::SHL &&
1694             Code != BinOpInit::MUL && Code != BinOpInit::DIV)
1695           ArgType = Resolved;
1696       }
1697 
1698       // Deal with BinOps whose arguments have different types, by
1699       // rewriting ArgType in between them.
1700       switch (Code) {
1701         case BinOpInit::SETDAGOP:
1702           // After parsing the first dag argument, switch to expecting
1703           // a record, with no restriction on its superclasses.
1704           ArgType = RecordRecTy::get(Records, {});
1705           break;
1706         case BinOpInit::GETDAGARG:
1707           // After parsing the first dag argument, expect an index integer or a
1708           // name string.
1709           ArgType = nullptr;
1710           break;
1711         case BinOpInit::GETDAGNAME:
1712           // After parsing the first dag argument, expect an index integer.
1713           ArgType = IntRecTy::get(Records);
1714           break;
1715         default:
1716           break;
1717       }
1718 
1719       if (!consume(tgtok::comma))
1720         break;
1721     }
1722 
1723     if (!consume(tgtok::r_paren)) {
1724       TokError("expected ')' in operator");
1725       return nullptr;
1726     }
1727 
1728     // listconcat returns a list with type of the argument.
1729     if (Code == BinOpInit::LISTCONCAT)
1730       Type = ArgType;
1731     // listsplat returns a list of type of the *first* argument.
1732     if (Code == BinOpInit::LISTSPLAT)
1733       Type = cast<TypedInit>(InitList.front())->getType()->getListTy();
1734     // listremove returns a list with type of the argument.
1735     if (Code == BinOpInit::LISTREMOVE)
1736       Type = ArgType;
1737 
1738     // We allow multiple operands to associative operators like !strconcat as
1739     // shorthand for nesting them.
1740     if (Code == BinOpInit::STRCONCAT || Code == BinOpInit::LISTCONCAT ||
1741         Code == BinOpInit::CONCAT || Code == BinOpInit::ADD ||
1742         Code == BinOpInit::AND || Code == BinOpInit::OR ||
1743         Code == BinOpInit::XOR || Code == BinOpInit::MUL) {
1744       while (InitList.size() > 2) {
1745         Init *RHS = InitList.pop_back_val();
1746         RHS = (BinOpInit::get(Code, InitList.back(), RHS, Type))->Fold(CurRec);
1747         InitList.back() = RHS;
1748       }
1749     }
1750 
1751     if (InitList.size() == 2)
1752       return (BinOpInit::get(Code, InitList[0], InitList[1], Type))
1753           ->Fold(CurRec);
1754 
1755     Error(OpLoc, "expected two operands to operator");
1756     return nullptr;
1757   }
1758 
1759   case tgtok::XForEach:
1760   case tgtok::XFilter: {
1761     return ParseOperationForEachFilter(CurRec, ItemType);
1762   }
1763 
1764   case tgtok::XRange: {
1765     SMLoc OpLoc = Lex.getLoc();
1766     Lex.Lex(); // eat the operation
1767 
1768     if (!consume(tgtok::l_paren)) {
1769       TokError("expected '(' after !range operator");
1770       return nullptr;
1771     }
1772 
1773     SmallVector<Init *, 2> Args;
1774     bool FirstArgIsList = false;
1775     for (;;) {
1776       if (Args.size() >= 3) {
1777         TokError("expected at most three values of integer");
1778         return nullptr;
1779       }
1780 
1781       SMLoc InitLoc = Lex.getLoc();
1782       Args.push_back(ParseValue(CurRec));
1783       if (!Args.back())
1784         return nullptr;
1785 
1786       TypedInit *ArgBack = dyn_cast<TypedInit>(Args.back());
1787       if (!ArgBack) {
1788         Error(OpLoc, Twine("expected value to be a typed value, got '" +
1789                            Args.back()->getAsString() + "'"));
1790         return nullptr;
1791       }
1792 
1793       RecTy *ArgBackType = ArgBack->getType();
1794       if (!FirstArgIsList || Args.size() == 1) {
1795         if (Args.size() == 1 && isa<ListRecTy>(ArgBackType)) {
1796           FirstArgIsList = true; // Detect error if 2nd arg were present.
1797         } else if (isa<IntRecTy>(ArgBackType)) {
1798           // Assume 2nd arg should be IntRecTy
1799         } else {
1800           if (Args.size() != 1)
1801             Error(InitLoc, Twine("expected value of type 'int', got '" +
1802                                  ArgBackType->getAsString() + "'"));
1803           else
1804             Error(InitLoc, Twine("expected list or int, got value of type '") +
1805                                ArgBackType->getAsString() + "'");
1806           return nullptr;
1807         }
1808       } else {
1809         // Don't come here unless 1st arg is ListRecTy.
1810         assert(isa<ListRecTy>(cast<TypedInit>(Args[0])->getType()));
1811         Error(InitLoc, Twine("expected one list, got extra value of type '") +
1812                            ArgBackType->getAsString() + "'");
1813         return nullptr;
1814       }
1815       if (!consume(tgtok::comma))
1816         break;
1817     }
1818 
1819     if (!consume(tgtok::r_paren)) {
1820       TokError("expected ')' in operator");
1821       return nullptr;
1822     }
1823 
1824     Init *LHS, *MHS, *RHS;
1825     auto ArgCount = Args.size();
1826     assert(ArgCount >= 1);
1827     auto *Arg0 = cast<TypedInit>(Args[0]);
1828     auto *Arg0Ty = Arg0->getType();
1829     if (ArgCount == 1) {
1830       if (isa<ListRecTy>(Arg0Ty)) {
1831         // (0, !size(arg), 1)
1832         LHS = IntInit::get(Records, 0);
1833         MHS = UnOpInit::get(UnOpInit::SIZE, Arg0, IntRecTy::get(Records))
1834                   ->Fold(CurRec);
1835         RHS = IntInit::get(Records, 1);
1836       } else {
1837         assert(isa<IntRecTy>(Arg0Ty));
1838         // (0, arg, 1)
1839         LHS = IntInit::get(Records, 0);
1840         MHS = Arg0;
1841         RHS = IntInit::get(Records, 1);
1842       }
1843     } else {
1844       assert(isa<IntRecTy>(Arg0Ty));
1845       auto *Arg1 = cast<TypedInit>(Args[1]);
1846       assert(isa<IntRecTy>(Arg1->getType()));
1847       LHS = Arg0;
1848       MHS = Arg1;
1849       if (ArgCount == 3) {
1850         // (start, end, step)
1851         auto *Arg2 = cast<TypedInit>(Args[2]);
1852         assert(isa<IntRecTy>(Arg2->getType()));
1853         RHS = Arg2;
1854       } else
1855         // (start, end, 1)
1856         RHS = IntInit::get(Records, 1);
1857     }
1858     return TernOpInit::get(TernOpInit::RANGE, LHS, MHS, RHS,
1859                            IntRecTy::get(Records)->getListTy())
1860         ->Fold(CurRec);
1861   }
1862 
1863   case tgtok::XSetDagArg:
1864   case tgtok::XSetDagName:
1865   case tgtok::XDag:
1866   case tgtok::XIf:
1867   case tgtok::XSubst: { // Value ::= !ternop '(' Value ',' Value ',' Value ')'
1868     TernOpInit::TernaryOp Code;
1869     RecTy *Type = nullptr;
1870 
1871     tgtok::TokKind LexCode = Lex.getCode();
1872     Lex.Lex();  // eat the operation
1873     switch (LexCode) {
1874     default: llvm_unreachable("Unhandled code!");
1875     case tgtok::XDag:
1876       Code = TernOpInit::DAG;
1877       Type = DagRecTy::get(Records);
1878       ItemType = nullptr;
1879       break;
1880     case tgtok::XIf:
1881       Code = TernOpInit::IF;
1882       break;
1883     case tgtok::XSubst:
1884       Code = TernOpInit::SUBST;
1885       break;
1886     case tgtok::XSetDagArg:
1887       Code = TernOpInit::SETDAGARG;
1888       Type = DagRecTy::get(Records);
1889       ItemType = nullptr;
1890       break;
1891     case tgtok::XSetDagName:
1892       Code = TernOpInit::SETDAGNAME;
1893       Type = DagRecTy::get(Records);
1894       ItemType = nullptr;
1895       break;
1896     }
1897     if (!consume(tgtok::l_paren)) {
1898       TokError("expected '(' after ternary operator");
1899       return nullptr;
1900     }
1901 
1902     Init *LHS = ParseValue(CurRec);
1903     if (!LHS) return nullptr;
1904 
1905     if (!consume(tgtok::comma)) {
1906       TokError("expected ',' in ternary operator");
1907       return nullptr;
1908     }
1909 
1910     SMLoc MHSLoc = Lex.getLoc();
1911     Init *MHS = ParseValue(CurRec, ItemType);
1912     if (!MHS)
1913       return nullptr;
1914 
1915     if (!consume(tgtok::comma)) {
1916       TokError("expected ',' in ternary operator");
1917       return nullptr;
1918     }
1919 
1920     SMLoc RHSLoc = Lex.getLoc();
1921     Init *RHS = ParseValue(CurRec, ItemType);
1922     if (!RHS)
1923       return nullptr;
1924 
1925     if (!consume(tgtok::r_paren)) {
1926       TokError("expected ')' in binary operator");
1927       return nullptr;
1928     }
1929 
1930     switch (LexCode) {
1931     default: llvm_unreachable("Unhandled code!");
1932     case tgtok::XDag: {
1933       TypedInit *MHSt = dyn_cast<TypedInit>(MHS);
1934       if (!MHSt && !isa<UnsetInit>(MHS)) {
1935         Error(MHSLoc, "could not determine type of the child list in !dag");
1936         return nullptr;
1937       }
1938       if (MHSt && !isa<ListRecTy>(MHSt->getType())) {
1939         Error(MHSLoc, Twine("expected list of children, got type '") +
1940                           MHSt->getType()->getAsString() + "'");
1941         return nullptr;
1942       }
1943 
1944       TypedInit *RHSt = dyn_cast<TypedInit>(RHS);
1945       if (!RHSt && !isa<UnsetInit>(RHS)) {
1946         Error(RHSLoc, "could not determine type of the name list in !dag");
1947         return nullptr;
1948       }
1949       if (RHSt && StringRecTy::get(Records)->getListTy() != RHSt->getType()) {
1950         Error(RHSLoc, Twine("expected list<string>, got type '") +
1951                           RHSt->getType()->getAsString() + "'");
1952         return nullptr;
1953       }
1954 
1955       if (!MHSt && !RHSt) {
1956         Error(MHSLoc,
1957               "cannot have both unset children and unset names in !dag");
1958         return nullptr;
1959       }
1960       break;
1961     }
1962     case tgtok::XIf: {
1963       RecTy *MHSTy = nullptr;
1964       RecTy *RHSTy = nullptr;
1965 
1966       if (TypedInit *MHSt = dyn_cast<TypedInit>(MHS))
1967         MHSTy = MHSt->getType();
1968       if (BitsInit *MHSbits = dyn_cast<BitsInit>(MHS))
1969         MHSTy = BitsRecTy::get(Records, MHSbits->getNumBits());
1970       if (isa<BitInit>(MHS))
1971         MHSTy = BitRecTy::get(Records);
1972 
1973       if (TypedInit *RHSt = dyn_cast<TypedInit>(RHS))
1974         RHSTy = RHSt->getType();
1975       if (BitsInit *RHSbits = dyn_cast<BitsInit>(RHS))
1976         RHSTy = BitsRecTy::get(Records, RHSbits->getNumBits());
1977       if (isa<BitInit>(RHS))
1978         RHSTy = BitRecTy::get(Records);
1979 
1980       // For UnsetInit, it's typed from the other hand.
1981       if (isa<UnsetInit>(MHS))
1982         MHSTy = RHSTy;
1983       if (isa<UnsetInit>(RHS))
1984         RHSTy = MHSTy;
1985 
1986       if (!MHSTy || !RHSTy) {
1987         TokError("could not get type for !if");
1988         return nullptr;
1989       }
1990 
1991       Type = resolveTypes(MHSTy, RHSTy);
1992       if (!Type) {
1993         TokError(Twine("inconsistent types '") + MHSTy->getAsString() +
1994                  "' and '" + RHSTy->getAsString() + "' for !if");
1995         return nullptr;
1996       }
1997       break;
1998     }
1999     case tgtok::XSubst: {
2000       TypedInit *RHSt = dyn_cast<TypedInit>(RHS);
2001       if (!RHSt) {
2002         TokError("could not get type for !subst");
2003         return nullptr;
2004       }
2005       Type = RHSt->getType();
2006       break;
2007     }
2008     case tgtok::XSetDagArg: {
2009       TypedInit *MHSt = dyn_cast<TypedInit>(MHS);
2010       if (!MHSt || !isa<IntRecTy, StringRecTy>(MHSt->getType())) {
2011         Error(MHSLoc, Twine("expected integer index or string name, got ") +
2012                           (MHSt ? ("type '" + MHSt->getType()->getAsString())
2013                                 : ("'" + MHS->getAsString())) +
2014                           "'");
2015         return nullptr;
2016       }
2017       break;
2018     }
2019     case tgtok::XSetDagName: {
2020       TypedInit *MHSt = dyn_cast<TypedInit>(MHS);
2021       if (!MHSt || !isa<IntRecTy, StringRecTy>(MHSt->getType())) {
2022         Error(MHSLoc, Twine("expected integer index or string name, got ") +
2023                           (MHSt ? ("type '" + MHSt->getType()->getAsString())
2024                                 : ("'" + MHS->getAsString())) +
2025                           "'");
2026         return nullptr;
2027       }
2028       TypedInit *RHSt = dyn_cast<TypedInit>(RHS);
2029       // The name could be a string or unset.
2030       if (RHSt && !isa<StringRecTy>(RHSt->getType())) {
2031         Error(RHSLoc, Twine("expected string or unset name, got type '") +
2032                           RHSt->getType()->getAsString() + "'");
2033         return nullptr;
2034       }
2035       break;
2036     }
2037     }
2038     return (TernOpInit::get(Code, LHS, MHS, RHS, Type))->Fold(CurRec);
2039   }
2040 
2041   case tgtok::XSubstr:
2042     return ParseOperationSubstr(CurRec, ItemType);
2043 
2044   case tgtok::XFind:
2045     return ParseOperationFind(CurRec, ItemType);
2046 
2047   case tgtok::XCond:
2048     return ParseOperationCond(CurRec, ItemType);
2049 
2050   case tgtok::XFoldl: {
2051     // Value ::= !foldl '(' Value ',' Value ',' Id ',' Id ',' Expr ')'
2052     Lex.Lex(); // eat the operation
2053     if (!consume(tgtok::l_paren)) {
2054       TokError("expected '(' after !foldl");
2055       return nullptr;
2056     }
2057 
2058     Init *StartUntyped = ParseValue(CurRec);
2059     if (!StartUntyped)
2060       return nullptr;
2061 
2062     TypedInit *Start = dyn_cast<TypedInit>(StartUntyped);
2063     if (!Start) {
2064       TokError(Twine("could not get type of !foldl start: '") +
2065                StartUntyped->getAsString() + "'");
2066       return nullptr;
2067     }
2068 
2069     if (!consume(tgtok::comma)) {
2070       TokError("expected ',' in !foldl");
2071       return nullptr;
2072     }
2073 
2074     Init *ListUntyped = ParseValue(CurRec);
2075     if (!ListUntyped)
2076       return nullptr;
2077 
2078     TypedInit *List = dyn_cast<TypedInit>(ListUntyped);
2079     if (!List) {
2080       TokError(Twine("could not get type of !foldl list: '") +
2081                ListUntyped->getAsString() + "'");
2082       return nullptr;
2083     }
2084 
2085     ListRecTy *ListType = dyn_cast<ListRecTy>(List->getType());
2086     if (!ListType) {
2087       TokError(Twine("!foldl list must be a list, but is of type '") +
2088                List->getType()->getAsString());
2089       return nullptr;
2090     }
2091 
2092     if (Lex.getCode() != tgtok::comma) {
2093       TokError("expected ',' in !foldl");
2094       return nullptr;
2095     }
2096 
2097     if (Lex.Lex() != tgtok::Id) { // eat the ','
2098       TokError("third argument of !foldl must be an identifier");
2099       return nullptr;
2100     }
2101 
2102     Init *A = StringInit::get(Records, Lex.getCurStrVal());
2103     if (CurRec && CurRec->getValue(A)) {
2104       TokError((Twine("left !foldl variable '") + A->getAsString() +
2105                 "' already defined")
2106                    .str());
2107       return nullptr;
2108     }
2109 
2110     if (Lex.Lex() != tgtok::comma) { // eat the id
2111       TokError("expected ',' in !foldl");
2112       return nullptr;
2113     }
2114 
2115     if (Lex.Lex() != tgtok::Id) { // eat the ','
2116       TokError("fourth argument of !foldl must be an identifier");
2117       return nullptr;
2118     }
2119 
2120     Init *B = StringInit::get(Records, Lex.getCurStrVal());
2121     if (CurRec && CurRec->getValue(B)) {
2122       TokError((Twine("right !foldl variable '") + B->getAsString() +
2123                 "' already defined")
2124                    .str());
2125       return nullptr;
2126     }
2127 
2128     if (Lex.Lex() != tgtok::comma) { // eat the id
2129       TokError("expected ',' in !foldl");
2130       return nullptr;
2131     }
2132     Lex.Lex(); // eat the ','
2133 
2134     // We need to create a temporary record to provide a scope for the
2135     // two variables.
2136     std::unique_ptr<Record> ParseRecTmp;
2137     Record *ParseRec = CurRec;
2138     if (!ParseRec) {
2139       ParseRecTmp = std::make_unique<Record>(".parse", ArrayRef<SMLoc>{}, Records);
2140       ParseRec = ParseRecTmp.get();
2141     }
2142 
2143     TGVarScope *FoldScope = PushScope(ParseRec);
2144     ParseRec->addValue(RecordVal(A, Start->getType(), RecordVal::FK_Normal));
2145     ParseRec->addValue(
2146         RecordVal(B, ListType->getElementType(), RecordVal::FK_Normal));
2147     Init *ExprUntyped = ParseValue(ParseRec);
2148     ParseRec->removeValue(A);
2149     ParseRec->removeValue(B);
2150     PopScope(FoldScope);
2151     if (!ExprUntyped)
2152       return nullptr;
2153 
2154     TypedInit *Expr = dyn_cast<TypedInit>(ExprUntyped);
2155     if (!Expr) {
2156       TokError("could not get type of !foldl expression");
2157       return nullptr;
2158     }
2159 
2160     if (Expr->getType() != Start->getType()) {
2161       TokError(Twine("!foldl expression must be of same type as start (") +
2162                Start->getType()->getAsString() + "), but is of type " +
2163                Expr->getType()->getAsString());
2164       return nullptr;
2165     }
2166 
2167     if (!consume(tgtok::r_paren)) {
2168       TokError("expected ')' in fold operator");
2169       return nullptr;
2170     }
2171 
2172     return FoldOpInit::get(Start, List, A, B, Expr, Start->getType())
2173         ->Fold(CurRec);
2174   }
2175   }
2176 }
2177 
2178 /// ParseOperatorType - Parse a type for an operator.  This returns
2179 /// null on error.
2180 ///
2181 /// OperatorType ::= '<' Type '>'
2182 ///
2183 RecTy *TGParser::ParseOperatorType() {
2184   RecTy *Type = nullptr;
2185 
2186   if (!consume(tgtok::less)) {
2187     TokError("expected type name for operator");
2188     return nullptr;
2189   }
2190 
2191   if (Lex.getCode() == tgtok::Code)
2192     TokError("the 'code' type is not allowed in bang operators; use 'string'");
2193 
2194   Type = ParseType();
2195 
2196   if (!Type) {
2197     TokError("expected type name for operator");
2198     return nullptr;
2199   }
2200 
2201   if (!consume(tgtok::greater)) {
2202     TokError("expected type name for operator");
2203     return nullptr;
2204   }
2205 
2206   return Type;
2207 }
2208 
2209 /// Parse the !substr operation. Return null on error.
2210 ///
2211 /// Substr ::= !substr(string, start-int [, length-int]) => string
2212 Init *TGParser::ParseOperationSubstr(Record *CurRec, RecTy *ItemType) {
2213   TernOpInit::TernaryOp Code = TernOpInit::SUBSTR;
2214   RecTy *Type = StringRecTy::get(Records);
2215 
2216   Lex.Lex(); // eat the operation
2217 
2218   if (!consume(tgtok::l_paren)) {
2219     TokError("expected '(' after !substr operator");
2220     return nullptr;
2221   }
2222 
2223   Init *LHS = ParseValue(CurRec);
2224   if (!LHS)
2225     return nullptr;
2226 
2227   if (!consume(tgtok::comma)) {
2228     TokError("expected ',' in !substr operator");
2229     return nullptr;
2230   }
2231 
2232   SMLoc MHSLoc = Lex.getLoc();
2233   Init *MHS = ParseValue(CurRec);
2234   if (!MHS)
2235     return nullptr;
2236 
2237   SMLoc RHSLoc = Lex.getLoc();
2238   Init *RHS;
2239   if (consume(tgtok::comma)) {
2240     RHSLoc = Lex.getLoc();
2241     RHS = ParseValue(CurRec);
2242     if (!RHS)
2243       return nullptr;
2244   } else {
2245     RHS = IntInit::get(Records, std::numeric_limits<int64_t>::max());
2246   }
2247 
2248   if (!consume(tgtok::r_paren)) {
2249     TokError("expected ')' in !substr operator");
2250     return nullptr;
2251   }
2252 
2253   if (ItemType && !Type->typeIsConvertibleTo(ItemType)) {
2254     Error(RHSLoc, Twine("expected value of type '") +
2255                   ItemType->getAsString() + "', got '" +
2256                   Type->getAsString() + "'");
2257   }
2258 
2259   TypedInit *LHSt = dyn_cast<TypedInit>(LHS);
2260   if (!LHSt && !isa<UnsetInit>(LHS)) {
2261     TokError("could not determine type of the string in !substr");
2262     return nullptr;
2263   }
2264   if (LHSt && !isa<StringRecTy>(LHSt->getType())) {
2265     TokError(Twine("expected string, got type '") +
2266              LHSt->getType()->getAsString() + "'");
2267     return nullptr;
2268   }
2269 
2270   TypedInit *MHSt = dyn_cast<TypedInit>(MHS);
2271   if (!MHSt && !isa<UnsetInit>(MHS)) {
2272     TokError("could not determine type of the start position in !substr");
2273     return nullptr;
2274   }
2275   if (MHSt && !isa<IntRecTy>(MHSt->getType())) {
2276     Error(MHSLoc, Twine("expected int, got type '") +
2277                       MHSt->getType()->getAsString() + "'");
2278     return nullptr;
2279   }
2280 
2281   if (RHS) {
2282     TypedInit *RHSt = dyn_cast<TypedInit>(RHS);
2283     if (!RHSt && !isa<UnsetInit>(RHS)) {
2284       TokError("could not determine type of the length in !substr");
2285       return nullptr;
2286     }
2287     if (RHSt && !isa<IntRecTy>(RHSt->getType())) {
2288       TokError(Twine("expected int, got type '") +
2289                RHSt->getType()->getAsString() + "'");
2290       return nullptr;
2291     }
2292   }
2293 
2294   return (TernOpInit::get(Code, LHS, MHS, RHS, Type))->Fold(CurRec);
2295 }
2296 
2297 /// Parse the !find operation. Return null on error.
2298 ///
2299 /// Substr ::= !find(string, string [, start-int]) => int
2300 Init *TGParser::ParseOperationFind(Record *CurRec, RecTy *ItemType) {
2301   TernOpInit::TernaryOp Code = TernOpInit::FIND;
2302   RecTy *Type = IntRecTy::get(Records);
2303 
2304   Lex.Lex(); // eat the operation
2305 
2306   if (!consume(tgtok::l_paren)) {
2307     TokError("expected '(' after !find operator");
2308     return nullptr;
2309   }
2310 
2311   Init *LHS = ParseValue(CurRec);
2312   if (!LHS)
2313     return nullptr;
2314 
2315   if (!consume(tgtok::comma)) {
2316     TokError("expected ',' in !find operator");
2317     return nullptr;
2318   }
2319 
2320   SMLoc MHSLoc = Lex.getLoc();
2321   Init *MHS = ParseValue(CurRec);
2322   if (!MHS)
2323     return nullptr;
2324 
2325   SMLoc RHSLoc = Lex.getLoc();
2326   Init *RHS;
2327   if (consume(tgtok::comma)) {
2328     RHSLoc = Lex.getLoc();
2329     RHS = ParseValue(CurRec);
2330     if (!RHS)
2331       return nullptr;
2332   } else {
2333     RHS = IntInit::get(Records, 0);
2334   }
2335 
2336   if (!consume(tgtok::r_paren)) {
2337     TokError("expected ')' in !find operator");
2338     return nullptr;
2339   }
2340 
2341   if (ItemType && !Type->typeIsConvertibleTo(ItemType)) {
2342     Error(RHSLoc, Twine("expected value of type '") +
2343                   ItemType->getAsString() + "', got '" +
2344                   Type->getAsString() + "'");
2345   }
2346 
2347   TypedInit *LHSt = dyn_cast<TypedInit>(LHS);
2348   if (!LHSt && !isa<UnsetInit>(LHS)) {
2349     TokError("could not determine type of the source string in !find");
2350     return nullptr;
2351   }
2352   if (LHSt && !isa<StringRecTy>(LHSt->getType())) {
2353     TokError(Twine("expected string, got type '") +
2354              LHSt->getType()->getAsString() + "'");
2355     return nullptr;
2356   }
2357 
2358   TypedInit *MHSt = dyn_cast<TypedInit>(MHS);
2359   if (!MHSt && !isa<UnsetInit>(MHS)) {
2360     TokError("could not determine type of the target string in !find");
2361     return nullptr;
2362   }
2363   if (MHSt && !isa<StringRecTy>(MHSt->getType())) {
2364     Error(MHSLoc, Twine("expected string, got type '") +
2365                       MHSt->getType()->getAsString() + "'");
2366     return nullptr;
2367   }
2368 
2369   if (RHS) {
2370     TypedInit *RHSt = dyn_cast<TypedInit>(RHS);
2371     if (!RHSt && !isa<UnsetInit>(RHS)) {
2372       TokError("could not determine type of the start position in !find");
2373       return nullptr;
2374     }
2375     if (RHSt && !isa<IntRecTy>(RHSt->getType())) {
2376       TokError(Twine("expected int, got type '") +
2377                RHSt->getType()->getAsString() + "'");
2378       return nullptr;
2379     }
2380   }
2381 
2382   return (TernOpInit::get(Code, LHS, MHS, RHS, Type))->Fold(CurRec);
2383 }
2384 
2385 /// Parse the !foreach and !filter operations. Return null on error.
2386 ///
2387 /// ForEach ::= !foreach(ID, list-or-dag, expr) => list<expr type>
2388 /// Filter  ::= !foreach(ID, list, predicate) ==> list<list type>
2389 Init *TGParser::ParseOperationForEachFilter(Record *CurRec, RecTy *ItemType) {
2390   SMLoc OpLoc = Lex.getLoc();
2391   tgtok::TokKind Operation = Lex.getCode();
2392   Lex.Lex(); // eat the operation
2393   if (Lex.getCode() != tgtok::l_paren) {
2394     TokError("expected '(' after !foreach/!filter");
2395     return nullptr;
2396   }
2397 
2398   if (Lex.Lex() != tgtok::Id) { // eat the '('
2399     TokError("first argument of !foreach/!filter must be an identifier");
2400     return nullptr;
2401   }
2402 
2403   Init *LHS = StringInit::get(Records, Lex.getCurStrVal());
2404   Lex.Lex(); // eat the ID.
2405 
2406   if (CurRec && CurRec->getValue(LHS)) {
2407     TokError((Twine("iteration variable '") + LHS->getAsString() +
2408               "' is already defined")
2409                  .str());
2410     return nullptr;
2411   }
2412 
2413   if (!consume(tgtok::comma)) {
2414     TokError("expected ',' in !foreach/!filter");
2415     return nullptr;
2416   }
2417 
2418   Init *MHS = ParseValue(CurRec);
2419   if (!MHS)
2420     return nullptr;
2421 
2422   if (!consume(tgtok::comma)) {
2423     TokError("expected ',' in !foreach/!filter");
2424     return nullptr;
2425   }
2426 
2427   TypedInit *MHSt = dyn_cast<TypedInit>(MHS);
2428   if (!MHSt) {
2429     TokError("could not get type of !foreach/!filter list or dag");
2430     return nullptr;
2431   }
2432 
2433   RecTy *InEltType = nullptr;
2434   RecTy *ExprEltType = nullptr;
2435   bool IsDAG = false;
2436 
2437   if (ListRecTy *InListTy = dyn_cast<ListRecTy>(MHSt->getType())) {
2438     InEltType = InListTy->getElementType();
2439     if (ItemType) {
2440       if (ListRecTy *OutListTy = dyn_cast<ListRecTy>(ItemType)) {
2441         ExprEltType = (Operation == tgtok::XForEach)
2442                           ? OutListTy->getElementType()
2443                           : IntRecTy::get(Records);
2444       } else {
2445         Error(OpLoc,
2446               "expected value of type '" +
2447                   Twine(ItemType->getAsString()) +
2448                   "', but got list type");
2449         return nullptr;
2450       }
2451     }
2452   } else if (DagRecTy *InDagTy = dyn_cast<DagRecTy>(MHSt->getType())) {
2453     if (Operation == tgtok::XFilter) {
2454       TokError("!filter must have a list argument");
2455       return nullptr;
2456     }
2457     InEltType = InDagTy;
2458     if (ItemType && !isa<DagRecTy>(ItemType)) {
2459       Error(OpLoc,
2460             "expected value of type '" + Twine(ItemType->getAsString()) +
2461                 "', but got dag type");
2462       return nullptr;
2463     }
2464     IsDAG = true;
2465   } else {
2466     if (Operation == tgtok::XForEach)
2467       TokError("!foreach must have a list or dag argument");
2468     else
2469       TokError("!filter must have a list argument");
2470     return nullptr;
2471   }
2472 
2473   // We need to create a temporary record to provide a scope for the
2474   // iteration variable.
2475   std::unique_ptr<Record> ParseRecTmp;
2476   Record *ParseRec = CurRec;
2477   if (!ParseRec) {
2478     ParseRecTmp =
2479         std::make_unique<Record>(".parse", ArrayRef<SMLoc>{}, Records);
2480     ParseRec = ParseRecTmp.get();
2481   }
2482   TGVarScope *TempScope = PushScope(ParseRec);
2483   ParseRec->addValue(RecordVal(LHS, InEltType, RecordVal::FK_Normal));
2484   Init *RHS = ParseValue(ParseRec, ExprEltType);
2485   ParseRec->removeValue(LHS);
2486   PopScope(TempScope);
2487   if (!RHS)
2488     return nullptr;
2489 
2490   if (!consume(tgtok::r_paren)) {
2491     TokError("expected ')' in !foreach/!filter");
2492     return nullptr;
2493   }
2494 
2495   RecTy *OutType = InEltType;
2496   if (Operation == tgtok::XForEach && !IsDAG) {
2497     TypedInit *RHSt = dyn_cast<TypedInit>(RHS);
2498     if (!RHSt) {
2499       TokError("could not get type of !foreach result expression");
2500       return nullptr;
2501     }
2502     OutType = RHSt->getType()->getListTy();
2503   } else if (Operation == tgtok::XFilter) {
2504     OutType = InEltType->getListTy();
2505   }
2506 
2507   return (TernOpInit::get((Operation == tgtok::XForEach) ? TernOpInit::FOREACH
2508                                                          : TernOpInit::FILTER,
2509                           LHS, MHS, RHS, OutType))
2510       ->Fold(CurRec);
2511 }
2512 
2513 Init *TGParser::ParseOperationCond(Record *CurRec, RecTy *ItemType) {
2514   Lex.Lex();  // eat the operation 'cond'
2515 
2516   if (!consume(tgtok::l_paren)) {
2517     TokError("expected '(' after !cond operator");
2518     return nullptr;
2519   }
2520 
2521   // Parse through '[Case: Val,]+'
2522   SmallVector<Init *, 4> Case;
2523   SmallVector<Init *, 4> Val;
2524   while (true) {
2525     if (consume(tgtok::r_paren))
2526       break;
2527 
2528     Init *V = ParseValue(CurRec);
2529     if (!V)
2530       return nullptr;
2531     Case.push_back(V);
2532 
2533     if (!consume(tgtok::colon)) {
2534       TokError("expected ':'  following a condition in !cond operator");
2535       return nullptr;
2536     }
2537 
2538     V = ParseValue(CurRec, ItemType);
2539     if (!V)
2540       return nullptr;
2541     Val.push_back(V);
2542 
2543     if (consume(tgtok::r_paren))
2544       break;
2545 
2546     if (!consume(tgtok::comma)) {
2547       TokError("expected ',' or ')' following a value in !cond operator");
2548       return nullptr;
2549     }
2550   }
2551 
2552   if (Case.size() < 1) {
2553     TokError("there should be at least 1 'condition : value' in the !cond operator");
2554     return nullptr;
2555   }
2556 
2557   // resolve type
2558   RecTy *Type = nullptr;
2559   for (Init *V : Val) {
2560     RecTy *VTy = nullptr;
2561     if (TypedInit *Vt = dyn_cast<TypedInit>(V))
2562       VTy = Vt->getType();
2563     if (BitsInit *Vbits = dyn_cast<BitsInit>(V))
2564       VTy = BitsRecTy::get(Records, Vbits->getNumBits());
2565     if (isa<BitInit>(V))
2566       VTy = BitRecTy::get(Records);
2567 
2568     if (Type == nullptr) {
2569       if (!isa<UnsetInit>(V))
2570         Type = VTy;
2571     } else {
2572       if (!isa<UnsetInit>(V)) {
2573         RecTy *RType = resolveTypes(Type, VTy);
2574         if (!RType) {
2575           TokError(Twine("inconsistent types '") + Type->getAsString() +
2576                          "' and '" + VTy->getAsString() + "' for !cond");
2577           return nullptr;
2578         }
2579         Type = RType;
2580       }
2581     }
2582   }
2583 
2584   if (!Type) {
2585     TokError("could not determine type for !cond from its arguments");
2586     return nullptr;
2587   }
2588   return CondOpInit::get(Case, Val, Type)->Fold(CurRec);
2589 }
2590 
2591 /// ParseSimpleValue - Parse a tblgen value.  This returns null on error.
2592 ///
2593 ///   SimpleValue ::= IDValue
2594 ///   SimpleValue ::= INTVAL
2595 ///   SimpleValue ::= STRVAL+
2596 ///   SimpleValue ::= CODEFRAGMENT
2597 ///   SimpleValue ::= '?'
2598 ///   SimpleValue ::= '{' ValueList '}'
2599 ///   SimpleValue ::= ID '<' ValueListNE '>'
2600 ///   SimpleValue ::= '[' ValueList ']'
2601 ///   SimpleValue ::= '(' IDValue DagArgList ')'
2602 ///   SimpleValue ::= CONCATTOK '(' Value ',' Value ')'
2603 ///   SimpleValue ::= ADDTOK '(' Value ',' Value ')'
2604 ///   SimpleValue ::= DIVTOK '(' Value ',' Value ')'
2605 ///   SimpleValue ::= SUBTOK '(' Value ',' Value ')'
2606 ///   SimpleValue ::= SHLTOK '(' Value ',' Value ')'
2607 ///   SimpleValue ::= SRATOK '(' Value ',' Value ')'
2608 ///   SimpleValue ::= SRLTOK '(' Value ',' Value ')'
2609 ///   SimpleValue ::= LISTCONCATTOK '(' Value ',' Value ')'
2610 ///   SimpleValue ::= LISTSPLATTOK '(' Value ',' Value ')'
2611 ///   SimpleValue ::= LISTREMOVETOK '(' Value ',' Value ')'
2612 ///   SimpleValue ::= RANGE '(' Value ')'
2613 ///   SimpleValue ::= RANGE '(' Value ',' Value ')'
2614 ///   SimpleValue ::= RANGE '(' Value ',' Value ',' Value ')'
2615 ///   SimpleValue ::= STRCONCATTOK '(' Value ',' Value ')'
2616 ///   SimpleValue ::= COND '(' [Value ':' Value,]+ ')'
2617 ///
2618 Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType,
2619                                  IDParseMode Mode) {
2620   Init *R = nullptr;
2621   tgtok::TokKind Code = Lex.getCode();
2622 
2623   // Parse bang operators.
2624   if (tgtok::isBangOperator(Code))
2625     return ParseOperation(CurRec, ItemType);
2626 
2627   switch (Code) {
2628   default: TokError("Unknown or reserved token when parsing a value"); break;
2629 
2630   case tgtok::TrueVal:
2631     R = IntInit::get(Records, 1);
2632     Lex.Lex();
2633     break;
2634   case tgtok::FalseVal:
2635     R = IntInit::get(Records, 0);
2636     Lex.Lex();
2637     break;
2638   case tgtok::IntVal:
2639     R = IntInit::get(Records, Lex.getCurIntVal());
2640     Lex.Lex();
2641     break;
2642   case tgtok::BinaryIntVal: {
2643     auto BinaryVal = Lex.getCurBinaryIntVal();
2644     SmallVector<Init*, 16> Bits(BinaryVal.second);
2645     for (unsigned i = 0, e = BinaryVal.second; i != e; ++i)
2646       Bits[i] = BitInit::get(Records, BinaryVal.first & (1LL << i));
2647     R = BitsInit::get(Records, Bits);
2648     Lex.Lex();
2649     break;
2650   }
2651   case tgtok::StrVal: {
2652     std::string Val = Lex.getCurStrVal();
2653     Lex.Lex();
2654 
2655     // Handle multiple consecutive concatenated strings.
2656     while (Lex.getCode() == tgtok::StrVal) {
2657       Val += Lex.getCurStrVal();
2658       Lex.Lex();
2659     }
2660 
2661     R = StringInit::get(Records, Val);
2662     break;
2663   }
2664   case tgtok::CodeFragment:
2665     R = StringInit::get(Records, Lex.getCurStrVal(), StringInit::SF_Code);
2666     Lex.Lex();
2667     break;
2668   case tgtok::question:
2669     R = UnsetInit::get(Records);
2670     Lex.Lex();
2671     break;
2672   case tgtok::Id: {
2673     SMRange NameLoc = Lex.getLocRange();
2674     StringInit *Name = StringInit::get(Records, Lex.getCurStrVal());
2675     tgtok::TokKind Next = Lex.Lex();
2676     if (Next == tgtok::equal) // Named argument.
2677       return Name;
2678     if (Next != tgtok::less)                            // consume the Id.
2679       return ParseIDValue(CurRec, Name, NameLoc, Mode); // Value ::= IDValue
2680 
2681     // Value ::= CLASSID '<' ArgValueList '>' (CLASSID has been consumed)
2682     // This is supposed to synthesize a new anonymous definition, deriving
2683     // from the class with the template arguments, but no body.
2684     Record *Class = Records.getClass(Name->getValue());
2685     if (!Class) {
2686       Error(NameLoc.Start,
2687             "Expected a class name, got '" + Name->getValue() + "'");
2688       return nullptr;
2689     }
2690 
2691     SmallVector<ArgumentInit *, 8> Args;
2692     Lex.Lex(); // consume the <
2693     if (ParseTemplateArgValueList(Args, CurRec, Class))
2694       return nullptr; // Error parsing value list.
2695 
2696     if (CheckTemplateArgValues(Args, NameLoc.Start, Class))
2697       return nullptr; // Error checking template argument values.
2698 
2699     if (resolveArguments(Class, Args, NameLoc.Start))
2700       return nullptr;
2701 
2702     if (TrackReferenceLocs)
2703       Class->appendReferenceLoc(NameLoc);
2704     return VarDefInit::get(Class, Args)->Fold();
2705   }
2706   case tgtok::l_brace: {           // Value ::= '{' ValueList '}'
2707     SMLoc BraceLoc = Lex.getLoc();
2708     Lex.Lex(); // eat the '{'
2709     SmallVector<Init*, 16> Vals;
2710 
2711     if (Lex.getCode() != tgtok::r_brace) {
2712       ParseValueList(Vals, CurRec);
2713       if (Vals.empty()) return nullptr;
2714     }
2715     if (!consume(tgtok::r_brace)) {
2716       TokError("expected '}' at end of bit list value");
2717       return nullptr;
2718     }
2719 
2720     SmallVector<Init *, 16> NewBits;
2721 
2722     // As we parse { a, b, ... }, 'a' is the highest bit, but we parse it
2723     // first.  We'll first read everything in to a vector, then we can reverse
2724     // it to get the bits in the correct order for the BitsInit value.
2725     for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
2726       // FIXME: The following two loops would not be duplicated
2727       //        if the API was a little more orthogonal.
2728 
2729       // bits<n> values are allowed to initialize n bits.
2730       if (BitsInit *BI = dyn_cast<BitsInit>(Vals[i])) {
2731         for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i)
2732           NewBits.push_back(BI->getBit((e - i) - 1));
2733         continue;
2734       }
2735       // bits<n> can also come from variable initializers.
2736       if (VarInit *VI = dyn_cast<VarInit>(Vals[i])) {
2737         if (BitsRecTy *BitsRec = dyn_cast<BitsRecTy>(VI->getType())) {
2738           for (unsigned i = 0, e = BitsRec->getNumBits(); i != e; ++i)
2739             NewBits.push_back(VI->getBit((e - i) - 1));
2740           continue;
2741         }
2742         // Fallthrough to try convert this to a bit.
2743       }
2744       // All other values must be convertible to just a single bit.
2745       Init *Bit = Vals[i]->getCastTo(BitRecTy::get(Records));
2746       if (!Bit) {
2747         Error(BraceLoc, "Element #" + Twine(i) + " (" + Vals[i]->getAsString() +
2748               ") is not convertable to a bit");
2749         return nullptr;
2750       }
2751       NewBits.push_back(Bit);
2752     }
2753     std::reverse(NewBits.begin(), NewBits.end());
2754     return BitsInit::get(Records, NewBits);
2755   }
2756   case tgtok::l_square: {          // Value ::= '[' ValueList ']'
2757     Lex.Lex(); // eat the '['
2758     SmallVector<Init*, 16> Vals;
2759 
2760     RecTy *DeducedEltTy = nullptr;
2761     ListRecTy *GivenListTy = nullptr;
2762 
2763     if (ItemType) {
2764       ListRecTy *ListType = dyn_cast<ListRecTy>(ItemType);
2765       if (!ListType) {
2766         TokError(Twine("Encountered a list when expecting a ") +
2767                  ItemType->getAsString());
2768         return nullptr;
2769       }
2770       GivenListTy = ListType;
2771     }
2772 
2773     if (Lex.getCode() != tgtok::r_square) {
2774       ParseValueList(Vals, CurRec,
2775                      GivenListTy ? GivenListTy->getElementType() : nullptr);
2776       if (Vals.empty()) return nullptr;
2777     }
2778     if (!consume(tgtok::r_square)) {
2779       TokError("expected ']' at end of list value");
2780       return nullptr;
2781     }
2782 
2783     RecTy *GivenEltTy = nullptr;
2784     if (consume(tgtok::less)) {
2785       // Optional list element type
2786       GivenEltTy = ParseType();
2787       if (!GivenEltTy) {
2788         // Couldn't parse element type
2789         return nullptr;
2790       }
2791 
2792       if (!consume(tgtok::greater)) {
2793         TokError("expected '>' at end of list element type");
2794         return nullptr;
2795       }
2796     }
2797 
2798     // Check elements
2799     RecTy *EltTy = nullptr;
2800     for (Init *V : Vals) {
2801       TypedInit *TArg = dyn_cast<TypedInit>(V);
2802       if (TArg) {
2803         if (EltTy) {
2804           EltTy = resolveTypes(EltTy, TArg->getType());
2805           if (!EltTy) {
2806             TokError("Incompatible types in list elements");
2807             return nullptr;
2808           }
2809         } else {
2810           EltTy = TArg->getType();
2811         }
2812       }
2813     }
2814 
2815     if (GivenEltTy) {
2816       if (EltTy) {
2817         // Verify consistency
2818         if (!EltTy->typeIsConvertibleTo(GivenEltTy)) {
2819           TokError("Incompatible types in list elements");
2820           return nullptr;
2821         }
2822       }
2823       EltTy = GivenEltTy;
2824     }
2825 
2826     if (!EltTy) {
2827       if (!ItemType) {
2828         TokError("No type for list");
2829         return nullptr;
2830       }
2831       DeducedEltTy = GivenListTy->getElementType();
2832     } else {
2833       // Make sure the deduced type is compatible with the given type
2834       if (GivenListTy) {
2835         if (!EltTy->typeIsConvertibleTo(GivenListTy->getElementType())) {
2836           TokError(Twine("Element type mismatch for list: element type '") +
2837                    EltTy->getAsString() + "' not convertible to '" +
2838                    GivenListTy->getElementType()->getAsString());
2839           return nullptr;
2840         }
2841       }
2842       DeducedEltTy = EltTy;
2843     }
2844 
2845     return ListInit::get(Vals, DeducedEltTy);
2846   }
2847   case tgtok::l_paren: {         // Value ::= '(' IDValue DagArgList ')'
2848     Lex.Lex();   // eat the '('
2849     if (Lex.getCode() != tgtok::Id && Lex.getCode() != tgtok::XCast &&
2850         Lex.getCode() != tgtok::question && Lex.getCode() != tgtok::XGetDagOp) {
2851       TokError("expected identifier in dag init");
2852       return nullptr;
2853     }
2854 
2855     Init *Operator = ParseValue(CurRec);
2856     if (!Operator) return nullptr;
2857 
2858     // If the operator name is present, parse it.
2859     StringInit *OperatorName = nullptr;
2860     if (consume(tgtok::colon)) {
2861       if (Lex.getCode() != tgtok::VarName) { // eat the ':'
2862         TokError("expected variable name in dag operator");
2863         return nullptr;
2864       }
2865       OperatorName = StringInit::get(Records, Lex.getCurStrVal());
2866       Lex.Lex();  // eat the VarName.
2867     }
2868 
2869     SmallVector<std::pair<llvm::Init*, StringInit*>, 8> DagArgs;
2870     if (Lex.getCode() != tgtok::r_paren) {
2871       ParseDagArgList(DagArgs, CurRec);
2872       if (DagArgs.empty()) return nullptr;
2873     }
2874 
2875     if (!consume(tgtok::r_paren)) {
2876       TokError("expected ')' in dag init");
2877       return nullptr;
2878     }
2879 
2880     return DagInit::get(Operator, OperatorName, DagArgs);
2881   }
2882   }
2883 
2884   return R;
2885 }
2886 
2887 /// ParseValue - Parse a TableGen value. This returns null on error.
2888 ///
2889 ///   Value       ::= SimpleValue ValueSuffix*
2890 ///   ValueSuffix ::= '{' BitList '}'
2891 ///   ValueSuffix ::= '[' SliceElements ']'
2892 ///   ValueSuffix ::= '.' ID
2893 ///
2894 Init *TGParser::ParseValue(Record *CurRec, RecTy *ItemType, IDParseMode Mode) {
2895   SMLoc LHSLoc = Lex.getLoc();
2896   Init *Result = ParseSimpleValue(CurRec, ItemType, Mode);
2897   if (!Result) return nullptr;
2898 
2899   // Parse the suffixes now if present.
2900   while (true) {
2901     switch (Lex.getCode()) {
2902     default: return Result;
2903     case tgtok::l_brace: {
2904       if (Mode == ParseNameMode)
2905         // This is the beginning of the object body.
2906         return Result;
2907 
2908       SMLoc CurlyLoc = Lex.getLoc();
2909       Lex.Lex(); // eat the '{'
2910       SmallVector<unsigned, 16> Ranges;
2911       ParseRangeList(Ranges);
2912       if (Ranges.empty()) return nullptr;
2913 
2914       // Reverse the bitlist.
2915       std::reverse(Ranges.begin(), Ranges.end());
2916       Result = Result->convertInitializerBitRange(Ranges);
2917       if (!Result) {
2918         Error(CurlyLoc, "Invalid bit range for value");
2919         return nullptr;
2920       }
2921 
2922       // Eat the '}'.
2923       if (!consume(tgtok::r_brace)) {
2924         TokError("expected '}' at end of bit range list");
2925         return nullptr;
2926       }
2927       break;
2928     }
2929     case tgtok::l_square: {
2930       auto *LHS = dyn_cast<TypedInit>(Result);
2931       if (!LHS) {
2932         Error(LHSLoc, "Invalid value, list expected");
2933         return nullptr;
2934       }
2935 
2936       auto *LHSTy = dyn_cast<ListRecTy>(LHS->getType());
2937       if (!LHSTy) {
2938         Error(LHSLoc, "Type '" + Twine(LHS->getType()->getAsString()) +
2939                           "' is invalid, list expected");
2940         return nullptr;
2941       }
2942 
2943       Lex.Lex(); // eat the '['
2944       TypedInit *RHS = ParseSliceElements(CurRec, /*Single=*/true);
2945       if (!RHS)
2946         return nullptr;
2947 
2948       if (isa<ListRecTy>(RHS->getType())) {
2949         Result =
2950             BinOpInit::get(BinOpInit::LISTSLICE, LHS, RHS, LHSTy)->Fold(CurRec);
2951       } else {
2952         Result = BinOpInit::get(BinOpInit::LISTELEM, LHS, RHS,
2953                                 LHSTy->getElementType())
2954                      ->Fold(CurRec);
2955       }
2956 
2957       assert(Result);
2958 
2959       // Eat the ']'.
2960       if (!consume(tgtok::r_square)) {
2961         TokError("expected ']' at end of list slice");
2962         return nullptr;
2963       }
2964       break;
2965     }
2966     case tgtok::dot: {
2967       if (Lex.Lex() != tgtok::Id) { // eat the .
2968         TokError("expected field identifier after '.'");
2969         return nullptr;
2970       }
2971       SMRange FieldNameLoc = Lex.getLocRange();
2972       StringInit *FieldName = StringInit::get(Records, Lex.getCurStrVal());
2973       if (!Result->getFieldType(FieldName)) {
2974         TokError("Cannot access field '" + Lex.getCurStrVal() + "' of value '" +
2975                  Result->getAsString() + "'");
2976         return nullptr;
2977       }
2978 
2979       // Add a reference to this field if we know the record class.
2980       if (TrackReferenceLocs) {
2981         if (auto *DI = dyn_cast<DefInit>(Result)) {
2982           DI->getDef()->getValue(FieldName)->addReferenceLoc(FieldNameLoc);
2983         } else if (auto *TI = dyn_cast<TypedInit>(Result)) {
2984           if (auto *RecTy = dyn_cast<RecordRecTy>(TI->getType())) {
2985             for (Record *R : RecTy->getClasses())
2986               if (auto *RV = R->getValue(FieldName))
2987                 RV->addReferenceLoc(FieldNameLoc);
2988           }
2989         }
2990       }
2991 
2992       Result = FieldInit::get(Result, FieldName)->Fold(CurRec);
2993       Lex.Lex();  // eat field name
2994       break;
2995     }
2996 
2997     case tgtok::paste:
2998       SMLoc PasteLoc = Lex.getLoc();
2999       TypedInit *LHS = dyn_cast<TypedInit>(Result);
3000       if (!LHS) {
3001         Error(PasteLoc, "LHS of paste is not typed!");
3002         return nullptr;
3003       }
3004 
3005       // Check if it's a 'listA # listB'
3006       if (isa<ListRecTy>(LHS->getType())) {
3007         Lex.Lex();  // Eat the '#'.
3008 
3009         assert(Mode == ParseValueMode && "encountered paste of lists in name");
3010 
3011         switch (Lex.getCode()) {
3012         case tgtok::colon:
3013         case tgtok::semi:
3014         case tgtok::l_brace:
3015           Result = LHS; // trailing paste, ignore.
3016           break;
3017         default:
3018           Init *RHSResult = ParseValue(CurRec, ItemType, ParseValueMode);
3019           if (!RHSResult)
3020             return nullptr;
3021           Result = BinOpInit::getListConcat(LHS, RHSResult);
3022           break;
3023         }
3024         break;
3025       }
3026 
3027       // Create a !strconcat() operation, first casting each operand to
3028       // a string if necessary.
3029       if (LHS->getType() != StringRecTy::get(Records)) {
3030         auto CastLHS = dyn_cast<TypedInit>(
3031             UnOpInit::get(UnOpInit::CAST, LHS, StringRecTy::get(Records))
3032                 ->Fold(CurRec));
3033         if (!CastLHS) {
3034           Error(PasteLoc,
3035                 Twine("can't cast '") + LHS->getAsString() + "' to string");
3036           return nullptr;
3037         }
3038         LHS = CastLHS;
3039       }
3040 
3041       TypedInit *RHS = nullptr;
3042 
3043       Lex.Lex();  // Eat the '#'.
3044       switch (Lex.getCode()) {
3045       case tgtok::colon:
3046       case tgtok::semi:
3047       case tgtok::l_brace:
3048         // These are all of the tokens that can begin an object body.
3049         // Some of these can also begin values but we disallow those cases
3050         // because they are unlikely to be useful.
3051 
3052         // Trailing paste, concat with an empty string.
3053         RHS = StringInit::get(Records, "");
3054         break;
3055 
3056       default:
3057         Init *RHSResult = ParseValue(CurRec, nullptr, ParseNameMode);
3058         if (!RHSResult)
3059           return nullptr;
3060         RHS = dyn_cast<TypedInit>(RHSResult);
3061         if (!RHS) {
3062           Error(PasteLoc, "RHS of paste is not typed!");
3063           return nullptr;
3064         }
3065 
3066         if (RHS->getType() != StringRecTy::get(Records)) {
3067           auto CastRHS = dyn_cast<TypedInit>(
3068               UnOpInit::get(UnOpInit::CAST, RHS, StringRecTy::get(Records))
3069                   ->Fold(CurRec));
3070           if (!CastRHS) {
3071             Error(PasteLoc,
3072                   Twine("can't cast '") + RHS->getAsString() + "' to string");
3073             return nullptr;
3074           }
3075           RHS = CastRHS;
3076         }
3077 
3078         break;
3079       }
3080 
3081       Result = BinOpInit::getStrConcat(LHS, RHS);
3082       break;
3083     }
3084   }
3085 }
3086 
3087 /// ParseDagArgList - Parse the argument list for a dag literal expression.
3088 ///
3089 ///    DagArg     ::= Value (':' VARNAME)?
3090 ///    DagArg     ::= VARNAME
3091 ///    DagArgList ::= DagArg
3092 ///    DagArgList ::= DagArgList ',' DagArg
3093 void TGParser::ParseDagArgList(
3094     SmallVectorImpl<std::pair<llvm::Init*, StringInit*>> &Result,
3095     Record *CurRec) {
3096 
3097   while (true) {
3098     // DagArg ::= VARNAME
3099     if (Lex.getCode() == tgtok::VarName) {
3100       // A missing value is treated like '?'.
3101       StringInit *VarName = StringInit::get(Records, Lex.getCurStrVal());
3102       Result.emplace_back(UnsetInit::get(Records), VarName);
3103       Lex.Lex();
3104     } else {
3105       // DagArg ::= Value (':' VARNAME)?
3106       Init *Val = ParseValue(CurRec);
3107       if (!Val) {
3108         Result.clear();
3109         return;
3110       }
3111 
3112       // If the variable name is present, add it.
3113       StringInit *VarName = nullptr;
3114       if (Lex.getCode() == tgtok::colon) {
3115         if (Lex.Lex() != tgtok::VarName) { // eat the ':'
3116           TokError("expected variable name in dag literal");
3117           Result.clear();
3118           return;
3119         }
3120         VarName = StringInit::get(Records, Lex.getCurStrVal());
3121         Lex.Lex();  // eat the VarName.
3122       }
3123 
3124       Result.push_back(std::make_pair(Val, VarName));
3125     }
3126     if (!consume(tgtok::comma))
3127       break;
3128   }
3129 }
3130 
3131 /// ParseValueList - Parse a comma separated list of values, returning them
3132 /// in a vector. Note that this always expects to be able to parse at least one
3133 /// value. It returns an empty list if this is not possible.
3134 ///
3135 ///   ValueList ::= Value (',' Value)
3136 ///
3137 void TGParser::ParseValueList(SmallVectorImpl<Init *> &Result, Record *CurRec,
3138                               RecTy *ItemType) {
3139 
3140   Result.push_back(ParseValue(CurRec, ItemType));
3141   if (!Result.back()) {
3142     Result.clear();
3143     return;
3144   }
3145 
3146   while (consume(tgtok::comma)) {
3147     // ignore trailing comma for lists
3148     if (Lex.getCode() == tgtok::r_square)
3149       return;
3150     Result.push_back(ParseValue(CurRec, ItemType));
3151     if (!Result.back()) {
3152       Result.clear();
3153       return;
3154     }
3155   }
3156 }
3157 
3158 // ParseTemplateArgValueList - Parse a template argument list with the syntax
3159 // shown, filling in the Result vector. The open angle has been consumed.
3160 // An empty argument list is allowed. Return false if okay, true if an
3161 // error was detected.
3162 //
3163 //   ArgValueList ::= '<' PostionalArgValueList [','] NamedArgValueList '>'
3164 //   PostionalArgValueList ::= [Value {',' Value}*]
3165 //   NamedArgValueList ::= [NameValue '=' Value {',' NameValue '=' Value}*]
3166 bool TGParser::ParseTemplateArgValueList(
3167     SmallVectorImpl<ArgumentInit *> &Result, Record *CurRec, Record *ArgsRec) {
3168   assert(Result.empty() && "Result vector is not empty");
3169   ArrayRef<Init *> TArgs = ArgsRec->getTemplateArgs();
3170 
3171   if (consume(tgtok::greater)) // empty value list
3172     return false;
3173 
3174   bool HasNamedArg = false;
3175   unsigned ArgIndex = 0;
3176   while (true) {
3177     if (ArgIndex >= TArgs.size()) {
3178       TokError("Too many template arguments: " + utostr(ArgIndex + 1));
3179       return true;
3180     }
3181 
3182     SMLoc ValueLoc = Lex.getLoc();
3183     // If we are parsing named argument, we don't need to know the argument name
3184     // and argument type will be resolved after we know the name.
3185     Init *Value = ParseValue(
3186         CurRec,
3187         HasNamedArg ? nullptr : ArgsRec->getValue(TArgs[ArgIndex])->getType());
3188     if (!Value)
3189       return true;
3190 
3191     // If we meet '=', then we are parsing named arguments.
3192     if (Lex.getCode() == tgtok::equal) {
3193       if (!isa<StringInit>(Value))
3194         return Error(ValueLoc,
3195                      "The name of named argument should be a valid identifier");
3196 
3197       auto *Name = cast<StringInit>(Value);
3198       Init *QualifiedName = QualifyName(*ArgsRec, Name);
3199       auto *NamedArg = ArgsRec->getValue(QualifiedName);
3200       if (!NamedArg)
3201         return Error(ValueLoc,
3202                      "Argument " + Name->getAsString() + " doesn't exist");
3203 
3204       Lex.Lex(); // eat the '='.
3205       ValueLoc = Lex.getLoc();
3206       Value = ParseValue(CurRec, NamedArg->getType());
3207       // Named value can't be uninitialized.
3208       if (isa<UnsetInit>(Value))
3209         return Error(ValueLoc,
3210                      "The value of named argument should be initialized, "
3211                      "but we got '" +
3212                          Value->getAsString() + "'");
3213 
3214       Result.push_back(ArgumentInit::get(Value, QualifiedName));
3215       HasNamedArg = true;
3216     } else {
3217       // Positional arguments should be put before named arguments.
3218       if (HasNamedArg)
3219         return Error(ValueLoc,
3220                      "Positional argument should be put before named argument");
3221 
3222       Result.push_back(ArgumentInit::get(Value, ArgIndex));
3223     }
3224 
3225     if (consume(tgtok::greater)) // end of argument list?
3226       return false;
3227     if (!consume(tgtok::comma))
3228       return TokError("Expected comma before next argument");
3229     ++ArgIndex;
3230   }
3231 }
3232 
3233 /// ParseDeclaration - Read a declaration, returning the name of field ID, or an
3234 /// empty string on error.  This can happen in a number of different contexts,
3235 /// including within a def or in the template args for a class (in which case
3236 /// CurRec will be non-null) and within the template args for a multiclass (in
3237 /// which case CurRec will be null, but CurMultiClass will be set).  This can
3238 /// also happen within a def that is within a multiclass, which will set both
3239 /// CurRec and CurMultiClass.
3240 ///
3241 ///  Declaration ::= FIELD? Type ID ('=' Value)?
3242 ///
3243 Init *TGParser::ParseDeclaration(Record *CurRec,
3244                                        bool ParsingTemplateArgs) {
3245   // Read the field prefix if present.
3246   bool HasField = consume(tgtok::Field);
3247 
3248   RecTy *Type = ParseType();
3249   if (!Type) return nullptr;
3250 
3251   if (Lex.getCode() != tgtok::Id) {
3252     TokError("Expected identifier in declaration");
3253     return nullptr;
3254   }
3255 
3256   std::string Str = Lex.getCurStrVal();
3257   if (Str == "NAME") {
3258     TokError("'" + Str + "' is a reserved variable name");
3259     return nullptr;
3260   }
3261 
3262   if (!ParsingTemplateArgs && CurScope->varAlreadyDefined(Str)) {
3263     TokError("local variable of this name already exists");
3264     return nullptr;
3265   }
3266 
3267   SMLoc IdLoc = Lex.getLoc();
3268   Init *DeclName = StringInit::get(Records, Str);
3269   Lex.Lex();
3270 
3271   bool BadField;
3272   if (!ParsingTemplateArgs) { // def, possibly in a multiclass
3273     BadField = AddValue(CurRec, IdLoc,
3274                         RecordVal(DeclName, IdLoc, Type,
3275                                   HasField ? RecordVal::FK_NonconcreteOK
3276                                            : RecordVal::FK_Normal));
3277   } else if (CurRec) { // class template argument
3278     DeclName = QualifyName(*CurRec, DeclName);
3279     BadField =
3280         AddValue(CurRec, IdLoc,
3281                  RecordVal(DeclName, IdLoc, Type, RecordVal::FK_TemplateArg));
3282   } else { // multiclass template argument
3283     assert(CurMultiClass && "invalid context for template argument");
3284     DeclName = QualifyName(CurMultiClass, DeclName);
3285     BadField =
3286         AddValue(CurRec, IdLoc,
3287                  RecordVal(DeclName, IdLoc, Type, RecordVal::FK_TemplateArg));
3288   }
3289   if (BadField)
3290     return nullptr;
3291 
3292   // If a value is present, parse it and set new field's value.
3293   if (consume(tgtok::equal)) {
3294     SMLoc ValLoc = Lex.getLoc();
3295     Init *Val = ParseValue(CurRec, Type);
3296     if (!Val ||
3297         SetValue(CurRec, ValLoc, DeclName, std::nullopt, Val,
3298                  /*AllowSelfAssignment=*/false, /*OverrideDefLoc=*/false)) {
3299       // Return the name, even if an error is thrown.  This is so that we can
3300       // continue to make some progress, even without the value having been
3301       // initialized.
3302       return DeclName;
3303     }
3304   }
3305 
3306   return DeclName;
3307 }
3308 
3309 /// ParseForeachDeclaration - Read a foreach declaration, returning
3310 /// the name of the declared object or a NULL Init on error.  Return
3311 /// the name of the parsed initializer list through ForeachListName.
3312 ///
3313 ///  ForeachDeclaration ::= ID '=' '{' RangeList '}'
3314 ///  ForeachDeclaration ::= ID '=' RangePiece
3315 ///  ForeachDeclaration ::= ID '=' Value
3316 ///
3317 VarInit *TGParser::ParseForeachDeclaration(Init *&ForeachListValue) {
3318   if (Lex.getCode() != tgtok::Id) {
3319     TokError("Expected identifier in foreach declaration");
3320     return nullptr;
3321   }
3322 
3323   Init *DeclName = StringInit::get(Records, Lex.getCurStrVal());
3324   Lex.Lex();
3325 
3326   // If a value is present, parse it.
3327   if (!consume(tgtok::equal)) {
3328     TokError("Expected '=' in foreach declaration");
3329     return nullptr;
3330   }
3331 
3332   RecTy *IterType = nullptr;
3333   SmallVector<unsigned, 16> Ranges;
3334 
3335   switch (Lex.getCode()) {
3336   case tgtok::l_brace: { // '{' RangeList '}'
3337     Lex.Lex(); // eat the '{'
3338     ParseRangeList(Ranges);
3339     if (!consume(tgtok::r_brace)) {
3340       TokError("expected '}' at end of bit range list");
3341       return nullptr;
3342     }
3343     break;
3344   }
3345 
3346   default: {
3347     SMLoc ValueLoc = Lex.getLoc();
3348     Init *I = ParseValue(nullptr);
3349     if (!I)
3350       return nullptr;
3351 
3352     TypedInit *TI = dyn_cast<TypedInit>(I);
3353     if (TI && isa<ListRecTy>(TI->getType())) {
3354       ForeachListValue = I;
3355       IterType = cast<ListRecTy>(TI->getType())->getElementType();
3356       break;
3357     }
3358 
3359     if (TI) {
3360       if (ParseRangePiece(Ranges, TI))
3361         return nullptr;
3362       break;
3363     }
3364 
3365     Error(ValueLoc, "expected a list, got '" + I->getAsString() + "'");
3366     if (CurMultiClass) {
3367       PrintNote({}, "references to multiclass template arguments cannot be "
3368                 "resolved at this time");
3369     }
3370     return nullptr;
3371   }
3372   }
3373 
3374 
3375   if (!Ranges.empty()) {
3376     assert(!IterType && "Type already initialized?");
3377     IterType = IntRecTy::get(Records);
3378     std::vector<Init *> Values;
3379     for (unsigned R : Ranges)
3380       Values.push_back(IntInit::get(Records, R));
3381     ForeachListValue = ListInit::get(Values, IterType);
3382   }
3383 
3384   if (!IterType)
3385     return nullptr;
3386 
3387   return VarInit::get(DeclName, IterType);
3388 }
3389 
3390 /// ParseTemplateArgList - Read a template argument list, which is a non-empty
3391 /// sequence of template-declarations in <>'s.  If CurRec is non-null, these are
3392 /// template args for a class. If null, these are the template args for a
3393 /// multiclass.
3394 ///
3395 ///    TemplateArgList ::= '<' Declaration (',' Declaration)* '>'
3396 ///
3397 bool TGParser::ParseTemplateArgList(Record *CurRec) {
3398   assert(Lex.getCode() == tgtok::less && "Not a template arg list!");
3399   Lex.Lex(); // eat the '<'
3400 
3401   Record *TheRecToAddTo = CurRec ? CurRec : &CurMultiClass->Rec;
3402 
3403   // Read the first declaration.
3404   Init *TemplArg = ParseDeclaration(CurRec, true/*templateargs*/);
3405   if (!TemplArg)
3406     return true;
3407 
3408   TheRecToAddTo->addTemplateArg(TemplArg);
3409 
3410   while (consume(tgtok::comma)) {
3411     // Read the following declarations.
3412     SMLoc Loc = Lex.getLoc();
3413     TemplArg = ParseDeclaration(CurRec, true/*templateargs*/);
3414     if (!TemplArg)
3415       return true;
3416 
3417     if (TheRecToAddTo->isTemplateArg(TemplArg))
3418       return Error(Loc, "template argument with the same name has already been "
3419                         "defined");
3420 
3421     TheRecToAddTo->addTemplateArg(TemplArg);
3422   }
3423 
3424   if (!consume(tgtok::greater))
3425     return TokError("expected '>' at end of template argument list");
3426   return false;
3427 }
3428 
3429 /// ParseBodyItem - Parse a single item within the body of a def or class.
3430 ///
3431 ///   BodyItem ::= Declaration ';'
3432 ///   BodyItem ::= LET ID OptionalBitList '=' Value ';'
3433 ///   BodyItem ::= Defvar
3434 ///   BodyItem ::= Dump
3435 ///   BodyItem ::= Assert
3436 ///
3437 bool TGParser::ParseBodyItem(Record *CurRec) {
3438   if (Lex.getCode() == tgtok::Assert)
3439     return ParseAssert(nullptr, CurRec);
3440 
3441   if (Lex.getCode() == tgtok::Defvar)
3442     return ParseDefvar(CurRec);
3443 
3444   if (Lex.getCode() == tgtok::Dump)
3445     return ParseDump(nullptr, CurRec);
3446 
3447   if (Lex.getCode() != tgtok::Let) {
3448     if (!ParseDeclaration(CurRec, false))
3449       return true;
3450 
3451     if (!consume(tgtok::semi))
3452       return TokError("expected ';' after declaration");
3453     return false;
3454   }
3455 
3456   // LET ID OptionalRangeList '=' Value ';'
3457   if (Lex.Lex() != tgtok::Id)
3458     return TokError("expected field identifier after let");
3459 
3460   SMLoc IdLoc = Lex.getLoc();
3461   StringInit *FieldName = StringInit::get(Records, Lex.getCurStrVal());
3462   Lex.Lex();  // eat the field name.
3463 
3464   SmallVector<unsigned, 16> BitList;
3465   if (ParseOptionalBitList(BitList))
3466     return true;
3467   std::reverse(BitList.begin(), BitList.end());
3468 
3469   if (!consume(tgtok::equal))
3470     return TokError("expected '=' in let expression");
3471 
3472   RecordVal *Field = CurRec->getValue(FieldName);
3473   if (!Field)
3474     return TokError("Value '" + FieldName->getValue() + "' unknown!");
3475 
3476   RecTy *Type = Field->getType();
3477   if (!BitList.empty() && isa<BitsRecTy>(Type)) {
3478     // When assigning to a subset of a 'bits' object, expect the RHS to have
3479     // the type of that subset instead of the type of the whole object.
3480     Type = BitsRecTy::get(Records, BitList.size());
3481   }
3482 
3483   Init *Val = ParseValue(CurRec, Type);
3484   if (!Val) return true;
3485 
3486   if (!consume(tgtok::semi))
3487     return TokError("expected ';' after let expression");
3488 
3489   return SetValue(CurRec, IdLoc, FieldName, BitList, Val);
3490 }
3491 
3492 /// ParseBody - Read the body of a class or def.  Return true on error, false on
3493 /// success.
3494 ///
3495 ///   Body     ::= ';'
3496 ///   Body     ::= '{' BodyList '}'
3497 ///   BodyList BodyItem*
3498 ///
3499 bool TGParser::ParseBody(Record *CurRec) {
3500   // If this is a null definition, just eat the semi and return.
3501   if (consume(tgtok::semi))
3502     return false;
3503 
3504   if (!consume(tgtok::l_brace))
3505     return TokError("Expected '{' to start body or ';' for declaration only");
3506 
3507   while (Lex.getCode() != tgtok::r_brace)
3508     if (ParseBodyItem(CurRec))
3509       return true;
3510 
3511   // Eat the '}'.
3512   Lex.Lex();
3513 
3514   // If we have a semicolon, print a gentle error.
3515   SMLoc SemiLoc = Lex.getLoc();
3516   if (consume(tgtok::semi)) {
3517     PrintError(SemiLoc, "A class or def body should not end with a semicolon");
3518     PrintNote("Semicolon ignored; remove to eliminate this error");
3519   }
3520 
3521   return false;
3522 }
3523 
3524 /// Apply the current let bindings to \a CurRec.
3525 /// \returns true on error, false otherwise.
3526 bool TGParser::ApplyLetStack(Record *CurRec) {
3527   for (SmallVectorImpl<LetRecord> &LetInfo : LetStack)
3528     for (LetRecord &LR : LetInfo)
3529       if (SetValue(CurRec, LR.Loc, LR.Name, LR.Bits, LR.Value))
3530         return true;
3531   return false;
3532 }
3533 
3534 /// Apply the current let bindings to the RecordsEntry.
3535 bool TGParser::ApplyLetStack(RecordsEntry &Entry) {
3536   if (Entry.Rec)
3537     return ApplyLetStack(Entry.Rec.get());
3538 
3539   // Let bindings are not applied to assertions.
3540   if (Entry.Assertion)
3541     return false;
3542 
3543   // Let bindings are not applied to dumps.
3544   if (Entry.Dump)
3545     return false;
3546 
3547   for (auto &E : Entry.Loop->Entries) {
3548     if (ApplyLetStack(E))
3549       return true;
3550   }
3551 
3552   return false;
3553 }
3554 
3555 /// ParseObjectBody - Parse the body of a def or class.  This consists of an
3556 /// optional ClassList followed by a Body.  CurRec is the current def or class
3557 /// that is being parsed.
3558 ///
3559 ///   ObjectBody      ::= BaseClassList Body
3560 ///   BaseClassList   ::= /*empty*/
3561 ///   BaseClassList   ::= ':' BaseClassListNE
3562 ///   BaseClassListNE ::= SubClassRef (',' SubClassRef)*
3563 ///
3564 bool TGParser::ParseObjectBody(Record *CurRec) {
3565   // An object body introduces a new scope for local variables.
3566   TGVarScope *ObjectScope = PushScope(CurRec);
3567   // If there is a baseclass list, read it.
3568   if (consume(tgtok::colon)) {
3569 
3570     // Read all of the subclasses.
3571     SubClassReference SubClass = ParseSubClassReference(CurRec, false);
3572     while (true) {
3573       // Check for error.
3574       if (!SubClass.Rec) return true;
3575 
3576       // Add it.
3577       if (AddSubClass(CurRec, SubClass))
3578         return true;
3579 
3580       if (!consume(tgtok::comma))
3581         break;
3582       SubClass = ParseSubClassReference(CurRec, false);
3583     }
3584   }
3585 
3586   if (ApplyLetStack(CurRec))
3587     return true;
3588 
3589   bool Result = ParseBody(CurRec);
3590   PopScope(ObjectScope);
3591   return Result;
3592 }
3593 
3594 /// ParseDef - Parse and return a top level or multiclass record definition.
3595 /// Return false if okay, true if error.
3596 ///
3597 ///   DefInst ::= DEF ObjectName ObjectBody
3598 ///
3599 bool TGParser::ParseDef(MultiClass *CurMultiClass) {
3600   SMLoc DefLoc = Lex.getLoc();
3601   assert(Lex.getCode() == tgtok::Def && "Unknown tok");
3602   Lex.Lex();  // Eat the 'def' token.
3603 
3604   // If the name of the def is an Id token, use that for the location.
3605   // Otherwise, the name is more complex and we use the location of the 'def'
3606   // token.
3607   SMLoc NameLoc = Lex.getCode() == tgtok::Id ? Lex.getLoc() : DefLoc;
3608 
3609   // Parse ObjectName and make a record for it.
3610   std::unique_ptr<Record> CurRec;
3611   Init *Name = ParseObjectName(CurMultiClass);
3612   if (!Name)
3613     return true;
3614 
3615   if (isa<UnsetInit>(Name)) {
3616     CurRec = std::make_unique<Record>(Records.getNewAnonymousName(), DefLoc,
3617                                       Records, Record::RK_AnonymousDef);
3618   } else {
3619     CurRec = std::make_unique<Record>(Name, NameLoc, Records);
3620   }
3621 
3622   if (ParseObjectBody(CurRec.get()))
3623     return true;
3624 
3625   return addEntry(std::move(CurRec));
3626 }
3627 
3628 /// ParseDefset - Parse a defset statement.
3629 ///
3630 ///   Defset ::= DEFSET Type Id '=' '{' ObjectList '}'
3631 ///
3632 bool TGParser::ParseDefset() {
3633   assert(Lex.getCode() == tgtok::Defset);
3634   Lex.Lex(); // Eat the 'defset' token
3635 
3636   DefsetRecord Defset;
3637   Defset.Loc = Lex.getLoc();
3638   RecTy *Type = ParseType();
3639   if (!Type)
3640     return true;
3641   if (!isa<ListRecTy>(Type))
3642     return Error(Defset.Loc, "expected list type");
3643   Defset.EltTy = cast<ListRecTy>(Type)->getElementType();
3644 
3645   if (Lex.getCode() != tgtok::Id)
3646     return TokError("expected identifier");
3647   StringInit *DeclName = StringInit::get(Records, Lex.getCurStrVal());
3648   if (Records.getGlobal(DeclName->getValue()))
3649     return TokError("def or global variable of this name already exists");
3650 
3651   if (Lex.Lex() != tgtok::equal) // Eat the identifier
3652     return TokError("expected '='");
3653   if (Lex.Lex() != tgtok::l_brace) // Eat the '='
3654     return TokError("expected '{'");
3655   SMLoc BraceLoc = Lex.getLoc();
3656   Lex.Lex(); // Eat the '{'
3657 
3658   Defsets.push_back(&Defset);
3659   bool Err = ParseObjectList(nullptr);
3660   Defsets.pop_back();
3661   if (Err)
3662     return true;
3663 
3664   if (!consume(tgtok::r_brace)) {
3665     TokError("expected '}' at end of defset");
3666     return Error(BraceLoc, "to match this '{'");
3667   }
3668 
3669   Records.addExtraGlobal(DeclName->getValue(),
3670                          ListInit::get(Defset.Elements, Defset.EltTy));
3671   return false;
3672 }
3673 
3674 /// ParseDeftype - Parse a defvar statement.
3675 ///
3676 ///   Deftype ::= DEFTYPE Id '=' Type ';'
3677 ///
3678 bool TGParser::ParseDeftype() {
3679   assert(Lex.getCode() == tgtok::Deftype);
3680   Lex.Lex(); // Eat the 'deftype' token
3681 
3682   if (Lex.getCode() != tgtok::Id)
3683     return TokError("expected identifier");
3684 
3685   const std::string TypeName = Lex.getCurStrVal();
3686   if (TypeAliases.count(TypeName) || Records.getClass(TypeName))
3687     return TokError("type of this name '" + TypeName + "' already exists");
3688 
3689   Lex.Lex();
3690   if (!consume(tgtok::equal))
3691     return TokError("expected '='");
3692 
3693   SMLoc Loc = Lex.getLoc();
3694   RecTy *Type = ParseType();
3695   if (!Type)
3696     return true;
3697 
3698   if (Type->getRecTyKind() == RecTy::RecordRecTyKind)
3699     return Error(Loc, "cannot define type alias for class type '" +
3700                           Type->getAsString() + "'");
3701 
3702   TypeAliases[TypeName] = Type;
3703 
3704   if (!consume(tgtok::semi))
3705     return TokError("expected ';'");
3706 
3707   return false;
3708 }
3709 
3710 /// ParseDefvar - Parse a defvar statement.
3711 ///
3712 ///   Defvar ::= DEFVAR Id '=' Value ';'
3713 ///
3714 bool TGParser::ParseDefvar(Record *CurRec) {
3715   assert(Lex.getCode() == tgtok::Defvar);
3716   Lex.Lex(); // Eat the 'defvar' token
3717 
3718   if (Lex.getCode() != tgtok::Id)
3719     return TokError("expected identifier");
3720   StringInit *DeclName = StringInit::get(Records, Lex.getCurStrVal());
3721   if (CurScope->varAlreadyDefined(DeclName->getValue()))
3722     return TokError("local variable of this name already exists");
3723 
3724   // The name should not be conflicted with existed field names.
3725   if (CurRec) {
3726     auto *V = CurRec->getValue(DeclName->getValue());
3727     if (V && !V->isTemplateArg())
3728       return TokError("field of this name already exists");
3729   }
3730 
3731   // If this defvar is in the top level, the name should not be conflicted
3732   // with existed global names.
3733   if (CurScope->isOutermost() && Records.getGlobal(DeclName->getValue()))
3734     return TokError("def or global variable of this name already exists");
3735 
3736   Lex.Lex();
3737   if (!consume(tgtok::equal))
3738     return TokError("expected '='");
3739 
3740   Init *Value = ParseValue(CurRec);
3741   if (!Value)
3742     return true;
3743 
3744   if (!consume(tgtok::semi))
3745     return TokError("expected ';'");
3746 
3747   if (!CurScope->isOutermost())
3748     CurScope->addVar(DeclName->getValue(), Value);
3749   else
3750     Records.addExtraGlobal(DeclName->getValue(), Value);
3751 
3752   return false;
3753 }
3754 
3755 /// ParseForeach - Parse a for statement.  Return the record corresponding
3756 /// to it.  This returns true on error.
3757 ///
3758 ///   Foreach ::= FOREACH Declaration IN '{ ObjectList '}'
3759 ///   Foreach ::= FOREACH Declaration IN Object
3760 ///
3761 bool TGParser::ParseForeach(MultiClass *CurMultiClass) {
3762   SMLoc Loc = Lex.getLoc();
3763   assert(Lex.getCode() == tgtok::Foreach && "Unknown tok");
3764   Lex.Lex();  // Eat the 'for' token.
3765 
3766   // Make a temporary object to record items associated with the for
3767   // loop.
3768   Init *ListValue = nullptr;
3769   VarInit *IterName = ParseForeachDeclaration(ListValue);
3770   if (!IterName)
3771     return TokError("expected declaration in for");
3772 
3773   if (!consume(tgtok::In))
3774     return TokError("Unknown tok");
3775 
3776   // Create a loop object and remember it.
3777   auto TheLoop = std::make_unique<ForeachLoop>(Loc, IterName, ListValue);
3778   // A foreach loop introduces a new scope for local variables.
3779   TGVarScope *ForeachScope = PushScope(TheLoop.get());
3780   Loops.push_back(std::move(TheLoop));
3781 
3782   if (Lex.getCode() != tgtok::l_brace) {
3783     // FOREACH Declaration IN Object
3784     if (ParseObject(CurMultiClass))
3785       return true;
3786   } else {
3787     SMLoc BraceLoc = Lex.getLoc();
3788     // Otherwise, this is a group foreach.
3789     Lex.Lex();  // eat the '{'.
3790 
3791     // Parse the object list.
3792     if (ParseObjectList(CurMultiClass))
3793       return true;
3794 
3795     if (!consume(tgtok::r_brace)) {
3796       TokError("expected '}' at end of foreach command");
3797       return Error(BraceLoc, "to match this '{'");
3798     }
3799   }
3800 
3801   PopScope(ForeachScope);
3802 
3803   // Resolve the loop or store it for later resolution.
3804   std::unique_ptr<ForeachLoop> Loop = std::move(Loops.back());
3805   Loops.pop_back();
3806 
3807   return addEntry(std::move(Loop));
3808 }
3809 
3810 /// ParseIf - Parse an if statement.
3811 ///
3812 ///   If ::= IF Value THEN IfBody
3813 ///   If ::= IF Value THEN IfBody ELSE IfBody
3814 ///
3815 bool TGParser::ParseIf(MultiClass *CurMultiClass) {
3816   SMLoc Loc = Lex.getLoc();
3817   assert(Lex.getCode() == tgtok::If && "Unknown tok");
3818   Lex.Lex(); // Eat the 'if' token.
3819 
3820   // Make a temporary object to record items associated with the for
3821   // loop.
3822   Init *Condition = ParseValue(nullptr);
3823   if (!Condition)
3824     return true;
3825 
3826   if (!consume(tgtok::Then))
3827     return TokError("Unknown tok");
3828 
3829   // We have to be able to save if statements to execute later, and they have
3830   // to live on the same stack as foreach loops. The simplest implementation
3831   // technique is to convert each 'then' or 'else' clause *into* a foreach
3832   // loop, over a list of length 0 or 1 depending on the condition, and with no
3833   // iteration variable being assigned.
3834 
3835   ListInit *EmptyList = ListInit::get({}, BitRecTy::get(Records));
3836   ListInit *SingletonList =
3837       ListInit::get({BitInit::get(Records, true)}, BitRecTy::get(Records));
3838   RecTy *BitListTy = ListRecTy::get(BitRecTy::get(Records));
3839 
3840   // The foreach containing the then-clause selects SingletonList if
3841   // the condition is true.
3842   Init *ThenClauseList =
3843       TernOpInit::get(TernOpInit::IF, Condition, SingletonList, EmptyList,
3844                       BitListTy)
3845           ->Fold(nullptr);
3846   Loops.push_back(std::make_unique<ForeachLoop>(Loc, nullptr, ThenClauseList));
3847 
3848   if (ParseIfBody(CurMultiClass, "then"))
3849     return true;
3850 
3851   std::unique_ptr<ForeachLoop> Loop = std::move(Loops.back());
3852   Loops.pop_back();
3853 
3854   if (addEntry(std::move(Loop)))
3855     return true;
3856 
3857   // Now look for an optional else clause. The if-else syntax has the usual
3858   // dangling-else ambiguity, and by greedily matching an else here if we can,
3859   // we implement the usual resolution of pairing with the innermost unmatched
3860   // if.
3861   if (consume(tgtok::ElseKW)) {
3862     // The foreach containing the else-clause uses the same pair of lists as
3863     // above, but this time, selects SingletonList if the condition is *false*.
3864     Init *ElseClauseList =
3865         TernOpInit::get(TernOpInit::IF, Condition, EmptyList, SingletonList,
3866                         BitListTy)
3867             ->Fold(nullptr);
3868     Loops.push_back(
3869         std::make_unique<ForeachLoop>(Loc, nullptr, ElseClauseList));
3870 
3871     if (ParseIfBody(CurMultiClass, "else"))
3872       return true;
3873 
3874     Loop = std::move(Loops.back());
3875     Loops.pop_back();
3876 
3877     if (addEntry(std::move(Loop)))
3878       return true;
3879   }
3880 
3881   return false;
3882 }
3883 
3884 /// ParseIfBody - Parse the then-clause or else-clause of an if statement.
3885 ///
3886 ///   IfBody ::= Object
3887 ///   IfBody ::= '{' ObjectList '}'
3888 ///
3889 bool TGParser::ParseIfBody(MultiClass *CurMultiClass, StringRef Kind) {
3890   // An if-statement introduces a new scope for local variables.
3891   TGVarScope *BodyScope = PushScope();
3892 
3893   if (Lex.getCode() != tgtok::l_brace) {
3894     // A single object.
3895     if (ParseObject(CurMultiClass))
3896       return true;
3897   } else {
3898     SMLoc BraceLoc = Lex.getLoc();
3899     // A braced block.
3900     Lex.Lex(); // eat the '{'.
3901 
3902     // Parse the object list.
3903     if (ParseObjectList(CurMultiClass))
3904       return true;
3905 
3906     if (!consume(tgtok::r_brace)) {
3907       TokError("expected '}' at end of '" + Kind + "' clause");
3908       return Error(BraceLoc, "to match this '{'");
3909     }
3910   }
3911 
3912   PopScope(BodyScope);
3913   return false;
3914 }
3915 
3916 /// ParseAssert - Parse an assert statement.
3917 ///
3918 ///   Assert ::= ASSERT condition , message ;
3919 bool TGParser::ParseAssert(MultiClass *CurMultiClass, Record *CurRec) {
3920   assert(Lex.getCode() == tgtok::Assert && "Unknown tok");
3921   Lex.Lex(); // Eat the 'assert' token.
3922 
3923   SMLoc ConditionLoc = Lex.getLoc();
3924   Init *Condition = ParseValue(CurRec);
3925   if (!Condition)
3926     return true;
3927 
3928   if (!consume(tgtok::comma)) {
3929     TokError("expected ',' in assert statement");
3930     return true;
3931   }
3932 
3933   Init *Message = ParseValue(CurRec);
3934   if (!Message)
3935     return true;
3936 
3937   if (!consume(tgtok::semi))
3938     return TokError("expected ';'");
3939 
3940   if (CurRec)
3941     CurRec->addAssertion(ConditionLoc, Condition, Message);
3942   else
3943     addEntry(std::make_unique<Record::AssertionInfo>(ConditionLoc, Condition,
3944                                                      Message));
3945   return false;
3946 }
3947 
3948 /// ParseClass - Parse a tblgen class definition.
3949 ///
3950 ///   ClassInst ::= CLASS ID TemplateArgList? ObjectBody
3951 ///
3952 bool TGParser::ParseClass() {
3953   assert(Lex.getCode() == tgtok::Class && "Unexpected token!");
3954   Lex.Lex();
3955 
3956   if (Lex.getCode() != tgtok::Id)
3957     return TokError("expected class name after 'class' keyword");
3958 
3959   const std::string &Name = Lex.getCurStrVal();
3960   Record *CurRec = Records.getClass(Name);
3961   if (CurRec) {
3962     // If the body was previously defined, this is an error.
3963     if (!CurRec->getValues().empty() ||
3964         !CurRec->getSuperClasses().empty() ||
3965         !CurRec->getTemplateArgs().empty())
3966       return TokError("Class '" + CurRec->getNameInitAsString() +
3967                       "' already defined");
3968 
3969     CurRec->updateClassLoc(Lex.getLoc());
3970   } else {
3971     // If this is the first reference to this class, create and add it.
3972     auto NewRec = std::make_unique<Record>(Lex.getCurStrVal(), Lex.getLoc(),
3973                                            Records, Record::RK_Class);
3974     CurRec = NewRec.get();
3975     Records.addClass(std::move(NewRec));
3976   }
3977 
3978   if (TypeAliases.count(Name))
3979     return TokError("there is already a defined type alias '" + Name + "'");
3980 
3981   Lex.Lex(); // eat the name.
3982 
3983   // A class definition introduces a new scope.
3984   TGVarScope *ClassScope = PushScope(CurRec);
3985   // If there are template args, parse them.
3986   if (Lex.getCode() == tgtok::less)
3987     if (ParseTemplateArgList(CurRec))
3988       return true;
3989 
3990   if (ParseObjectBody(CurRec))
3991     return true;
3992 
3993   if (!NoWarnOnUnusedTemplateArgs)
3994     CurRec->checkUnusedTemplateArgs();
3995 
3996   PopScope(ClassScope);
3997   return false;
3998 }
3999 
4000 /// ParseLetList - Parse a non-empty list of assignment expressions into a list
4001 /// of LetRecords.
4002 ///
4003 ///   LetList ::= LetItem (',' LetItem)*
4004 ///   LetItem ::= ID OptionalRangeList '=' Value
4005 ///
4006 void TGParser::ParseLetList(SmallVectorImpl<LetRecord> &Result) {
4007   do {
4008     if (Lex.getCode() != tgtok::Id) {
4009       TokError("expected identifier in let definition");
4010       Result.clear();
4011       return;
4012     }
4013 
4014     StringInit *Name = StringInit::get(Records, Lex.getCurStrVal());
4015     SMLoc NameLoc = Lex.getLoc();
4016     Lex.Lex();  // Eat the identifier.
4017 
4018     // Check for an optional RangeList.
4019     SmallVector<unsigned, 16> Bits;
4020     if (ParseOptionalRangeList(Bits)) {
4021       Result.clear();
4022       return;
4023     }
4024     std::reverse(Bits.begin(), Bits.end());
4025 
4026     if (!consume(tgtok::equal)) {
4027       TokError("expected '=' in let expression");
4028       Result.clear();
4029       return;
4030     }
4031 
4032     Init *Val = ParseValue(nullptr);
4033     if (!Val) {
4034       Result.clear();
4035       return;
4036     }
4037 
4038     // Now that we have everything, add the record.
4039     Result.emplace_back(Name, Bits, Val, NameLoc);
4040   } while (consume(tgtok::comma));
4041 }
4042 
4043 /// ParseTopLevelLet - Parse a 'let' at top level.  This can be a couple of
4044 /// different related productions. This works inside multiclasses too.
4045 ///
4046 ///   Object ::= LET LetList IN '{' ObjectList '}'
4047 ///   Object ::= LET LetList IN Object
4048 ///
4049 bool TGParser::ParseTopLevelLet(MultiClass *CurMultiClass) {
4050   assert(Lex.getCode() == tgtok::Let && "Unexpected token");
4051   Lex.Lex();
4052 
4053   // Add this entry to the let stack.
4054   SmallVector<LetRecord, 8> LetInfo;
4055   ParseLetList(LetInfo);
4056   if (LetInfo.empty()) return true;
4057   LetStack.push_back(std::move(LetInfo));
4058 
4059   if (!consume(tgtok::In))
4060     return TokError("expected 'in' at end of top-level 'let'");
4061 
4062   // If this is a scalar let, just handle it now
4063   if (Lex.getCode() != tgtok::l_brace) {
4064     // LET LetList IN Object
4065     if (ParseObject(CurMultiClass))
4066       return true;
4067   } else {   // Object ::= LETCommand '{' ObjectList '}'
4068     SMLoc BraceLoc = Lex.getLoc();
4069     // Otherwise, this is a group let.
4070     Lex.Lex();  // eat the '{'.
4071 
4072     // A group let introduces a new scope for local variables.
4073     TGVarScope *LetScope = PushScope();
4074 
4075     // Parse the object list.
4076     if (ParseObjectList(CurMultiClass))
4077       return true;
4078 
4079     if (!consume(tgtok::r_brace)) {
4080       TokError("expected '}' at end of top level let command");
4081       return Error(BraceLoc, "to match this '{'");
4082     }
4083 
4084     PopScope(LetScope);
4085   }
4086 
4087   // Outside this let scope, this let block is not active.
4088   LetStack.pop_back();
4089   return false;
4090 }
4091 
4092 /// ParseMultiClass - Parse a multiclass definition.
4093 ///
4094 ///  MultiClassInst ::= MULTICLASS ID TemplateArgList?
4095 ///                     ':' BaseMultiClassList '{' MultiClassObject+ '}'
4096 ///  MultiClassObject ::= Assert
4097 ///  MultiClassObject ::= DefInst
4098 ///  MultiClassObject ::= DefMInst
4099 ///  MultiClassObject ::= Defvar
4100 ///  MultiClassObject ::= Foreach
4101 ///  MultiClassObject ::= If
4102 ///  MultiClassObject ::= LETCommand '{' ObjectList '}'
4103 ///  MultiClassObject ::= LETCommand Object
4104 ///
4105 bool TGParser::ParseMultiClass() {
4106   assert(Lex.getCode() == tgtok::MultiClass && "Unexpected token");
4107   Lex.Lex();  // Eat the multiclass token.
4108 
4109   if (Lex.getCode() != tgtok::Id)
4110     return TokError("expected identifier after multiclass for name");
4111   std::string Name = Lex.getCurStrVal();
4112 
4113   auto Result =
4114     MultiClasses.insert(std::make_pair(Name,
4115                     std::make_unique<MultiClass>(Name, Lex.getLoc(),Records)));
4116 
4117   if (!Result.second)
4118     return TokError("multiclass '" + Name + "' already defined");
4119 
4120   CurMultiClass = Result.first->second.get();
4121   Lex.Lex();  // Eat the identifier.
4122 
4123   // A multiclass body introduces a new scope for local variables.
4124   TGVarScope *MulticlassScope = PushScope(CurMultiClass);
4125 
4126   // If there are template args, parse them.
4127   if (Lex.getCode() == tgtok::less)
4128     if (ParseTemplateArgList(nullptr))
4129       return true;
4130 
4131   bool inherits = false;
4132 
4133   // If there are submulticlasses, parse them.
4134   if (consume(tgtok::colon)) {
4135     inherits = true;
4136 
4137     // Read all of the submulticlasses.
4138     SubMultiClassReference SubMultiClass =
4139       ParseSubMultiClassReference(CurMultiClass);
4140     while (true) {
4141       // Check for error.
4142       if (!SubMultiClass.MC) return true;
4143 
4144       // Add it.
4145       if (AddSubMultiClass(CurMultiClass, SubMultiClass))
4146         return true;
4147 
4148       if (!consume(tgtok::comma))
4149         break;
4150       SubMultiClass = ParseSubMultiClassReference(CurMultiClass);
4151     }
4152   }
4153 
4154   if (Lex.getCode() != tgtok::l_brace) {
4155     if (!inherits)
4156       return TokError("expected '{' in multiclass definition");
4157     if (!consume(tgtok::semi))
4158       return TokError("expected ';' in multiclass definition");
4159   } else {
4160     if (Lex.Lex() == tgtok::r_brace)  // eat the '{'.
4161       return TokError("multiclass must contain at least one def");
4162 
4163     while (Lex.getCode() != tgtok::r_brace) {
4164       switch (Lex.getCode()) {
4165       default:
4166         return TokError("expected 'assert', 'def', 'defm', 'defvar', 'dump', "
4167                         "'foreach', 'if', or 'let' in multiclass body");
4168 
4169       case tgtok::Assert:
4170       case tgtok::Def:
4171       case tgtok::Defm:
4172       case tgtok::Defvar:
4173       case tgtok::Dump:
4174       case tgtok::Foreach:
4175       case tgtok::If:
4176       case tgtok::Let:
4177         if (ParseObject(CurMultiClass))
4178           return true;
4179         break;
4180       }
4181     }
4182     Lex.Lex();  // eat the '}'.
4183 
4184     // If we have a semicolon, print a gentle error.
4185     SMLoc SemiLoc = Lex.getLoc();
4186     if (consume(tgtok::semi)) {
4187       PrintError(SemiLoc, "A multiclass body should not end with a semicolon");
4188       PrintNote("Semicolon ignored; remove to eliminate this error");
4189     }
4190   }
4191 
4192   if (!NoWarnOnUnusedTemplateArgs)
4193     CurMultiClass->Rec.checkUnusedTemplateArgs();
4194 
4195   PopScope(MulticlassScope);
4196   CurMultiClass = nullptr;
4197   return false;
4198 }
4199 
4200 /// ParseDefm - Parse the instantiation of a multiclass.
4201 ///
4202 ///   DefMInst ::= DEFM ID ':' DefmSubClassRef ';'
4203 ///
4204 bool TGParser::ParseDefm(MultiClass *CurMultiClass) {
4205   assert(Lex.getCode() == tgtok::Defm && "Unexpected token!");
4206   Lex.Lex(); // eat the defm
4207 
4208   Init *DefmName = ParseObjectName(CurMultiClass);
4209   if (!DefmName)
4210     return true;
4211   if (isa<UnsetInit>(DefmName)) {
4212     DefmName = Records.getNewAnonymousName();
4213     if (CurMultiClass)
4214       DefmName = BinOpInit::getStrConcat(
4215           VarInit::get(QualifiedNameOfImplicitName(CurMultiClass),
4216                        StringRecTy::get(Records)),
4217           DefmName);
4218   }
4219 
4220   if (Lex.getCode() != tgtok::colon)
4221     return TokError("expected ':' after defm identifier");
4222 
4223   // Keep track of the new generated record definitions.
4224   std::vector<RecordsEntry> NewEntries;
4225 
4226   // This record also inherits from a regular class (non-multiclass)?
4227   bool InheritFromClass = false;
4228 
4229   // eat the colon.
4230   Lex.Lex();
4231 
4232   SMLoc SubClassLoc = Lex.getLoc();
4233   SubClassReference Ref = ParseSubClassReference(nullptr, true);
4234 
4235   while (true) {
4236     if (!Ref.Rec) return true;
4237 
4238     // To instantiate a multiclass, we get the multiclass and then loop
4239     // through its template argument names. Substs contains a substitution
4240     // value for each argument, either the value specified or the default.
4241     // Then we can resolve the template arguments.
4242     MultiClass *MC = MultiClasses[std::string(Ref.Rec->getName())].get();
4243     assert(MC && "Didn't lookup multiclass correctly?");
4244 
4245     SubstStack Substs;
4246     if (resolveArgumentsOfMultiClass(Substs, MC, Ref.TemplateArgs, DefmName,
4247                                      SubClassLoc))
4248       return true;
4249 
4250     if (resolve(MC->Entries, Substs, !CurMultiClass && Loops.empty(),
4251                 &NewEntries, &SubClassLoc))
4252       return true;
4253 
4254     if (!consume(tgtok::comma))
4255       break;
4256 
4257     if (Lex.getCode() != tgtok::Id)
4258       return TokError("expected identifier");
4259 
4260     SubClassLoc = Lex.getLoc();
4261 
4262     // A defm can inherit from regular classes (non-multiclasses) as
4263     // long as they come in the end of the inheritance list.
4264     InheritFromClass = (Records.getClass(Lex.getCurStrVal()) != nullptr);
4265 
4266     if (InheritFromClass)
4267       break;
4268 
4269     Ref = ParseSubClassReference(nullptr, true);
4270   }
4271 
4272   if (InheritFromClass) {
4273     // Process all the classes to inherit as if they were part of a
4274     // regular 'def' and inherit all record values.
4275     SubClassReference SubClass = ParseSubClassReference(nullptr, false);
4276     while (true) {
4277       // Check for error.
4278       if (!SubClass.Rec) return true;
4279 
4280       // Get the expanded definition prototypes and teach them about
4281       // the record values the current class to inherit has
4282       for (auto &E : NewEntries) {
4283         // Add it.
4284         if (AddSubClass(E, SubClass))
4285           return true;
4286       }
4287 
4288       if (!consume(tgtok::comma))
4289         break;
4290       SubClass = ParseSubClassReference(nullptr, false);
4291     }
4292   }
4293 
4294   for (auto &E : NewEntries) {
4295     if (ApplyLetStack(E))
4296       return true;
4297 
4298     addEntry(std::move(E));
4299   }
4300 
4301   if (!consume(tgtok::semi))
4302     return TokError("expected ';' at end of defm");
4303 
4304   return false;
4305 }
4306 
4307 /// ParseObject
4308 ///   Object ::= ClassInst
4309 ///   Object ::= DefInst
4310 ///   Object ::= MultiClassInst
4311 ///   Object ::= DefMInst
4312 ///   Object ::= LETCommand '{' ObjectList '}'
4313 ///   Object ::= LETCommand Object
4314 ///   Object ::= Defset
4315 ///   Object ::= Deftype
4316 ///   Object ::= Defvar
4317 ///   Object ::= Assert
4318 ///   Object ::= Dump
4319 bool TGParser::ParseObject(MultiClass *MC) {
4320   switch (Lex.getCode()) {
4321   default:
4322     return TokError(
4323         "Expected assert, class, def, defm, defset, dump, foreach, if, or let");
4324   case tgtok::Assert:  return ParseAssert(MC);
4325   case tgtok::Def:     return ParseDef(MC);
4326   case tgtok::Defm:    return ParseDefm(MC);
4327   case tgtok::Deftype:
4328     return ParseDeftype();
4329   case tgtok::Defvar:  return ParseDefvar();
4330   case tgtok::Dump:
4331     return ParseDump(MC);
4332   case tgtok::Foreach: return ParseForeach(MC);
4333   case tgtok::If:      return ParseIf(MC);
4334   case tgtok::Let:     return ParseTopLevelLet(MC);
4335   case tgtok::Defset:
4336     if (MC)
4337       return TokError("defset is not allowed inside multiclass");
4338     return ParseDefset();
4339   case tgtok::Class:
4340     if (MC)
4341       return TokError("class is not allowed inside multiclass");
4342     if (!Loops.empty())
4343       return TokError("class is not allowed inside foreach loop");
4344     return ParseClass();
4345   case tgtok::MultiClass:
4346     if (!Loops.empty())
4347       return TokError("multiclass is not allowed inside foreach loop");
4348     return ParseMultiClass();
4349   }
4350 }
4351 
4352 /// ParseObjectList
4353 ///   ObjectList :== Object*
4354 bool TGParser::ParseObjectList(MultiClass *MC) {
4355   while (tgtok::isObjectStart(Lex.getCode())) {
4356     if (ParseObject(MC))
4357       return true;
4358   }
4359   return false;
4360 }
4361 
4362 bool TGParser::ParseFile() {
4363   Lex.Lex(); // Prime the lexer.
4364   TGVarScope *GlobalScope = PushScope();
4365   if (ParseObjectList())
4366     return true;
4367   PopScope(GlobalScope);
4368 
4369   // If we have unread input at the end of the file, report it.
4370   if (Lex.getCode() == tgtok::Eof)
4371     return false;
4372 
4373   return TokError("Unexpected token at top level");
4374 }
4375 
4376 // Check the types of the template argument values for a class
4377 // inheritance, multiclass invocation, or anonymous class invocation.
4378 // If necessary, replace an argument with a cast to the required type.
4379 // The argument count has already been checked.
4380 bool TGParser::CheckTemplateArgValues(
4381     SmallVectorImpl<llvm::ArgumentInit *> &Values, SMLoc Loc, Record *ArgsRec) {
4382   ArrayRef<Init *> TArgs = ArgsRec->getTemplateArgs();
4383 
4384   for (llvm::ArgumentInit *&Value : Values) {
4385     Init *ArgName = nullptr;
4386     if (Value->isPositional())
4387       ArgName = TArgs[Value->getIndex()];
4388     if (Value->isNamed())
4389       ArgName = Value->getName();
4390 
4391     RecordVal *Arg = ArgsRec->getValue(ArgName);
4392     RecTy *ArgType = Arg->getType();
4393 
4394     if (TypedInit *ArgValue = dyn_cast<TypedInit>(Value->getValue())) {
4395       auto *CastValue = ArgValue->getCastTo(ArgType);
4396       if (CastValue) {
4397         assert((!isa<TypedInit>(CastValue) ||
4398                 cast<TypedInit>(CastValue)->getType()->typeIsA(ArgType)) &&
4399                "result of template arg value cast has wrong type");
4400         Value = Value->cloneWithValue(CastValue);
4401       } else {
4402         PrintFatalError(Loc, "Value specified for template argument '" +
4403                                  Arg->getNameInitAsString() + "' is of type " +
4404                                  ArgValue->getType()->getAsString() +
4405                                  "; expected type " + ArgType->getAsString() +
4406                                  ": " + ArgValue->getAsString());
4407       }
4408     }
4409   }
4410 
4411   return false;
4412 }
4413 
4414 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
4415 LLVM_DUMP_METHOD void RecordsEntry::dump() const {
4416   if (Loop)
4417     Loop->dump();
4418   if (Rec)
4419     Rec->dump();
4420 }
4421 
4422 LLVM_DUMP_METHOD void ForeachLoop::dump() const {
4423   errs() << "foreach " << IterVar->getAsString() << " = "
4424          << ListValue->getAsString() << " in {\n";
4425 
4426   for (const auto &E : Entries)
4427     E.dump();
4428 
4429   errs() << "}\n";
4430 }
4431 
4432 LLVM_DUMP_METHOD void MultiClass::dump() const {
4433   errs() << "Record:\n";
4434   Rec.dump();
4435 
4436   errs() << "Defs:\n";
4437   for (const auto &E : Entries)
4438     E.dump();
4439 }
4440 #endif
4441 
4442 bool TGParser::ParseDump(MultiClass *CurMultiClass, Record *CurRec) {
4443   // Location of the `dump` statement.
4444   SMLoc Loc = Lex.getLoc();
4445   assert(Lex.getCode() == tgtok::Dump && "Unknown tok");
4446   Lex.Lex(); // eat the operation
4447 
4448   Init *Message = ParseValue(CurRec);
4449   if (!Message)
4450     return true;
4451 
4452   // Allow to use dump directly on `defvar` and `def`, by wrapping
4453   // them with a `!repl`.
4454   if (isa<DefInit>(Message))
4455     Message = UnOpInit::get(UnOpInit::REPR, Message, StringRecTy::get(Records))
4456                   ->Fold(CurRec);
4457 
4458   if (!consume(tgtok::semi))
4459     return TokError("expected ';'");
4460 
4461   if (CurRec)
4462     CurRec->addDump(Loc, Message);
4463   else
4464     addEntry(std::make_unique<Record::DumpInfo>(Loc, Message));
4465 
4466   return false;
4467 }
4468