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