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