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