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