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