utils/TableGen/Record.cpp

   1 //===- Record.cpp - Record implementation ---------------------------------===//
   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 tablegen record classes.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "Record.h"
  15 #include "Error.h"
  16 #include "llvm/Support/DataTypes.h"
  17 #include "llvm/Support/Format.h"
  18 #include "llvm/ADT/StringExtras.h"
  19
  20 using namespace llvm;
  21
  22 //===----------------------------------------------------------------------===//
  23 //    std::string wrapper for DenseMap purposes
  24 //===----------------------------------------------------------------------===//
  25
  26 /// TableGenStringKey - This is a wrapper for std::string suitable for
  27 /// using as a key to a DenseMap.  Because there isn't a particularly
  28 /// good way to indicate tombstone or empty keys for strings, we want
  29 /// to wrap std::string to indicate that this is a "special" string
  30 /// not expected to take on certain values (those of the tombstone and
  31 /// empty keys).  This makes things a little safer as it clarifies
  32 /// that DenseMap is really not appropriate for general strings.
  33
  34 class TableGenStringKey {
  35 public:
  36   TableGenStringKey(const std::string &str) : data(str) {}
  37   TableGenStringKey(const char *str) : data(str) {}
  38
  39   const std::string &str() const { return data; }
  40
  41 private:
  42   std::string data;
  43 };
  44
  45 /// Specialize DenseMapInfo for TableGenStringKey.
  46 namespace llvm {
  47
  48 template<> struct DenseMapInfo<TableGenStringKey> {
  49   static inline TableGenStringKey getEmptyKey() {
  50     TableGenStringKey Empty("<<<EMPTY KEY>>>");
  51     return Empty;
  52   }
  53   static inline TableGenStringKey getTombstoneKey() {
  54     TableGenStringKey Tombstone("<<<TOMBSTONE KEY>>>");
  55     return Tombstone;
  56   }
  57   static unsigned getHashValue(const TableGenStringKey& Val) {
  58     return HashString(Val.str());
  59   }
  60   static bool isEqual(const TableGenStringKey& LHS,
  61                       const TableGenStringKey& RHS) {
  62     return LHS.str() == RHS.str();
  63   }
  64 };
  65
  66 }
  67
  68 //===----------------------------------------------------------------------===//
  69 //    Type implementations
  70 //===----------------------------------------------------------------------===//
  71
  72 BitRecTy BitRecTy::Shared;
  73 IntRecTy IntRecTy::Shared;
  74 StringRecTy StringRecTy::Shared;
  75 CodeRecTy CodeRecTy::Shared;
  76 DagRecTy DagRecTy::Shared;
  77
  78 void RecTy::dump() const { print(errs()); }
  79
  80 ListRecTy *RecTy::getListTy() {
  81   if (!ListTy)
  82     ListTy = new ListRecTy(this);
  83   return ListTy;
  84 }
  85
  86 Init *BitRecTy::convertValue(BitsInit *BI) {
  87   if (BI->getNumBits() != 1) return 0; // Only accept if just one bit!
  88   return BI->getBit(0);
  89 }
  90
  91 bool BitRecTy::baseClassOf(const BitsRecTy *RHS) const {
  92   return RHS->getNumBits() == 1;
  93 }
  94
  95 Init *BitRecTy::convertValue(IntInit *II) {
  96   int64_t Val = II->getValue();
  97   if (Val != 0 && Val != 1) return 0;  // Only accept 0 or 1 for a bit!
  98
  99   return new BitInit(Val != 0);
 100 }
 101
 102 Init *BitRecTy::convertValue(TypedInit *VI) {
 103   if (dynamic_cast<BitRecTy*>(VI->getType()))
 104     return VI;  // Accept variable if it is already of bit type!
 105   return 0;
 106 }
 107
 108 BitsRecTy *BitsRecTy::get(unsigned Sz) {
 109   static std::vector<BitsRecTy*> Shared;
 110   if (Sz >= Shared.size())
 111     Shared.resize(Sz + 1);
 112   BitsRecTy *&Ty = Shared[Sz];
 113   if (!Ty)
 114     Ty = new BitsRecTy(Sz);
 115   return Ty;
 116 }
 117
 118 std::string BitsRecTy::getAsString() const {
 119   return "bits<" + utostr(Size) + ">";
 120 }
 121
 122 Init *BitsRecTy::convertValue(UnsetInit *UI) {
 123   BitsInit *Ret = new BitsInit(Size);
 124
 125   for (unsigned i = 0; i != Size; ++i)
 126     Ret->setBit(i, new UnsetInit());
 127   return Ret;
 128 }
 129
 130 Init *BitsRecTy::convertValue(BitInit *UI) {
 131   if (Size != 1) return 0;  // Can only convert single bit.
 132   BitsInit *Ret = new BitsInit(1);
 133   Ret->setBit(0, UI);
 134   return Ret;
 135 }
 136
 137 /// canFitInBitfield - Return true if the number of bits is large enough to hold
 138 /// the integer value.
 139 static bool canFitInBitfield(int64_t Value, unsigned NumBits) {
 140   // For example, with NumBits == 4, we permit Values from [-7 .. 15].
 141   return (NumBits >= sizeof(Value) * 8) ||
 142          (Value >> NumBits == 0) || (Value >> (NumBits-1) == -1);
 143 }
 144
 145 /// convertValue from Int initializer to bits type: Split the integer up into the
 146 /// appropriate bits.
 147 ///
 148 Init *BitsRecTy::convertValue(IntInit *II) {
 149   int64_t Value = II->getValue();
 150   // Make sure this bitfield is large enough to hold the integer value.
 151   if (!canFitInBitfield(Value, Size))
 152     return 0;
 153
 154   BitsInit *Ret = new BitsInit(Size);
 155   for (unsigned i = 0; i != Size; ++i)
 156     Ret->setBit(i, new BitInit(Value & (1LL << i)));
 157
 158   return Ret;
 159 }
 160
 161 Init *BitsRecTy::convertValue(BitsInit *BI) {
 162   // If the number of bits is right, return it.  Otherwise we need to expand or
 163   // truncate.
 164   if (BI->getNumBits() == Size) return BI;
 165   return 0;
 166 }
 167
 168 Init *BitsRecTy::convertValue(TypedInit *VI) {
 169   if (BitsRecTy *BRT = dynamic_cast<BitsRecTy*>(VI->getType()))
 170     if (BRT->Size == Size) {
 171       BitsInit *Ret = new BitsInit(Size);
 172       for (unsigned i = 0; i != Size; ++i)
 173         Ret->setBit(i, new VarBitInit(VI, i));
 174       return Ret;
 175     }
 176
 177   if (Size == 1 && dynamic_cast<BitRecTy*>(VI->getType())) {
 178     BitsInit *Ret = new BitsInit(1);
 179     Ret->setBit(0, VI);
 180     return Ret;
 181   }
 182
 183   if (TernOpInit *Tern = dynamic_cast<TernOpInit*>(VI)) {
 184     if (Tern->getOpcode() == TernOpInit::IF) {
 185       Init *LHS = Tern->getLHS();
 186       Init *MHS = Tern->getMHS();
 187       Init *RHS = Tern->getRHS();
 188
 189       IntInit *MHSi = dynamic_cast<IntInit*>(MHS);
 190       IntInit *RHSi = dynamic_cast<IntInit*>(RHS);
 191
 192       if (MHSi && RHSi) {
 193         int64_t MHSVal = MHSi->getValue();
 194         int64_t RHSVal = RHSi->getValue();
 195
 196         if (canFitInBitfield(MHSVal, Size) && canFitInBitfield(RHSVal, Size)) {
 197           BitsInit *Ret = new BitsInit(Size);
 198
 199           for (unsigned i = 0; i != Size; ++i)
 200             Ret->setBit(i, new TernOpInit(TernOpInit::IF, LHS,
 201                                           new IntInit((MHSVal & (1LL << i)) ? 1 : 0),
 202                                           new IntInit((RHSVal & (1LL << i)) ? 1 : 0),
 203                                           VI->getType()));
 204
 205           return Ret;
 206         }
 207       } else {
 208         BitsInit *MHSbs = dynamic_cast<BitsInit*>(MHS);
 209         BitsInit *RHSbs = dynamic_cast<BitsInit*>(RHS);
 210
 211         if (MHSbs && RHSbs) {
 212           BitsInit *Ret = new BitsInit(Size);
 213
 214           for (unsigned i = 0; i != Size; ++i)
 215             Ret->setBit(i, new TernOpInit(TernOpInit::IF, LHS,
 216                                           MHSbs->getBit(i),
 217                                           RHSbs->getBit(i),
 218                                           VI->getType()));
 219
 220           return Ret;
 221         }
 222       }
 223     }
 224   }
 225
 226   return 0;
 227 }
 228
 229 Init *IntRecTy::convertValue(BitInit *BI) {
 230   return new IntInit(BI->getValue());
 231 }
 232
 233 Init *IntRecTy::convertValue(BitsInit *BI) {
 234   int64_t Result = 0;
 235   for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i)
 236     if (BitInit *Bit = dynamic_cast<BitInit*>(BI->getBit(i))) {
 237       Result |= Bit->getValue() << i;
 238     } else {
 239       return 0;
 240     }
 241   return new IntInit(Result);
 242 }
 243
 244 Init *IntRecTy::convertValue(TypedInit *TI) {
 245   if (TI->getType()->typeIsConvertibleTo(this))
 246     return TI;  // Accept variable if already of the right type!
 247   return 0;
 248 }
 249
 250 Init *StringRecTy::convertValue(UnOpInit *BO) {
 251   if (BO->getOpcode() == UnOpInit::CAST) {
 252     Init *L = BO->getOperand()->convertInitializerTo(this);
 253     if (L == 0) return 0;
 254     if (L != BO->getOperand())
 255       return new UnOpInit(UnOpInit::CAST, L, new StringRecTy);
 256     return BO;
 257   }
 258
 259   return convertValue((TypedInit*)BO);
 260 }
 261
 262 Init *StringRecTy::convertValue(BinOpInit *BO) {
 263   if (BO->getOpcode() == BinOpInit::STRCONCAT) {
 264     Init *L = BO->getLHS()->convertInitializerTo(this);
 265     Init *R = BO->getRHS()->convertInitializerTo(this);
 266     if (L == 0 || R == 0) return 0;
 267     if (L != BO->getLHS() || R != BO->getRHS())
 268       return new BinOpInit(BinOpInit::STRCONCAT, L, R, new StringRecTy);
 269     return BO;
 270   }
 271
 272   return convertValue((TypedInit*)BO);
 273 }
 274
 275
 276 Init *StringRecTy::convertValue(TypedInit *TI) {
 277   if (dynamic_cast<StringRecTy*>(TI->getType()))
 278     return TI;  // Accept variable if already of the right type!
 279   return 0;
 280 }
 281
 282 std::string ListRecTy::getAsString() const {
 283   return "list<" + Ty->getAsString() + ">";
 284 }
 285
 286 Init *ListRecTy::convertValue(ListInit *LI) {
 287   std::vector<Init*> Elements;
 288
 289   // Verify that all of the elements of the list are subclasses of the
 290   // appropriate class!
 291   for (unsigned i = 0, e = LI->getSize(); i != e; ++i)
 292     if (Init *CI = LI->getElement(i)->convertInitializerTo(Ty))
 293       Elements.push_back(CI);
 294     else
 295       return 0;
 296
 297   ListRecTy *LType = dynamic_cast<ListRecTy*>(LI->getType());
 298   if (LType == 0) {
 299     return 0;
 300   }
 301
 302   return new ListInit(Elements, this);
 303 }
 304
 305 Init *ListRecTy::convertValue(TypedInit *TI) {
 306   // Ensure that TI is compatible with our class.
 307   if (ListRecTy *LRT = dynamic_cast<ListRecTy*>(TI->getType()))
 308     if (LRT->getElementType()->typeIsConvertibleTo(getElementType()))
 309       return TI;
 310   return 0;
 311 }
 312
 313 Init *CodeRecTy::convertValue(TypedInit *TI) {
 314   if (TI->getType()->typeIsConvertibleTo(this))
 315     return TI;
 316   return 0;
 317 }
 318
 319 Init *DagRecTy::convertValue(TypedInit *TI) {
 320   if (TI->getType()->typeIsConvertibleTo(this))
 321     return TI;
 322   return 0;
 323 }
 324
 325 Init *DagRecTy::convertValue(UnOpInit *BO) {
 326   if (BO->getOpcode() == UnOpInit::CAST) {
 327     Init *L = BO->getOperand()->convertInitializerTo(this);
 328     if (L == 0) return 0;
 329     if (L != BO->getOperand())
 330       return new UnOpInit(UnOpInit::CAST, L, new DagRecTy);
 331     return BO;
 332   }
 333   return 0;
 334 }
 335
 336 Init *DagRecTy::convertValue(BinOpInit *BO) {
 337   if (BO->getOpcode() == BinOpInit::CONCAT) {
 338     Init *L = BO->getLHS()->convertInitializerTo(this);
 339     Init *R = BO->getRHS()->convertInitializerTo(this);
 340     if (L == 0 || R == 0) return 0;
 341     if (L != BO->getLHS() || R != BO->getRHS())
 342       return new BinOpInit(BinOpInit::CONCAT, L, R, new DagRecTy);
 343     return BO;
 344   }
 345   return 0;
 346 }
 347
 348 RecordRecTy *RecordRecTy::get(Record *R) {
 349   return &dynamic_cast<RecordRecTy&>(*R->getDefInit()->getType());
 350 }
 351
 352 std::string RecordRecTy::getAsString() const {
 353   return Rec->getName();
 354 }
 355
 356 Init *RecordRecTy::convertValue(DefInit *DI) {
 357   // Ensure that DI is a subclass of Rec.
 358   if (!DI->getDef()->isSubClassOf(Rec))
 359     return 0;
 360   return DI;
 361 }
 362
 363 Init *RecordRecTy::convertValue(TypedInit *TI) {
 364   // Ensure that TI is compatible with Rec.
 365   if (RecordRecTy *RRT = dynamic_cast<RecordRecTy*>(TI->getType()))
 366     if (RRT->getRecord()->isSubClassOf(getRecord()) ||
 367         RRT->getRecord() == getRecord())
 368       return TI;
 369   return 0;
 370 }
 371
 372 bool RecordRecTy::baseClassOf(const RecordRecTy *RHS) const {
 373   if (Rec == RHS->getRecord() || RHS->getRecord()->isSubClassOf(Rec))
 374     return true;
 375
 376   const std::vector<Record*> &SC = Rec->getSuperClasses();
 377   for (unsigned i = 0, e = SC.size(); i != e; ++i)
 378     if (RHS->getRecord()->isSubClassOf(SC[i]))
 379       return true;
 380
 381   return false;
 382 }
 383
 384
 385 /// resolveTypes - Find a common type that T1 and T2 convert to.
 386 /// Return 0 if no such type exists.
 387 ///
 388 RecTy *llvm::resolveTypes(RecTy *T1, RecTy *T2) {
 389   if (!T1->typeIsConvertibleTo(T2)) {
 390     if (!T2->typeIsConvertibleTo(T1)) {
 391       // If one is a Record type, check superclasses
 392       RecordRecTy *RecTy1 = dynamic_cast<RecordRecTy*>(T1);
 393       if (RecTy1) {
 394         // See if T2 inherits from a type T1 also inherits from
 395         const std::vector<Record *> &T1SuperClasses =
 396           RecTy1->getRecord()->getSuperClasses();
 397         for(std::vector<Record *>::const_iterator i = T1SuperClasses.begin(),
 398               iend = T1SuperClasses.end();
 399             i != iend;
 400             ++i) {
 401           RecordRecTy *SuperRecTy1 = RecordRecTy::get(*i);
 402           RecTy *NewType1 = resolveTypes(SuperRecTy1, T2);
 403           if (NewType1 != 0) {
 404             if (NewType1 != SuperRecTy1) {
 405               delete SuperRecTy1;
 406             }
 407             return NewType1;
 408           }
 409         }
 410       }
 411       RecordRecTy *RecTy2 = dynamic_cast<RecordRecTy*>(T2);
 412       if (RecTy2) {
 413         // See if T1 inherits from a type T2 also inherits from
 414         const std::vector<Record *> &T2SuperClasses =
 415           RecTy2->getRecord()->getSuperClasses();
 416         for (std::vector<Record *>::const_iterator i = T2SuperClasses.begin(),
 417               iend = T2SuperClasses.end();
 418             i != iend;
 419             ++i) {
 420           RecordRecTy *SuperRecTy2 = RecordRecTy::get(*i);
 421           RecTy *NewType2 = resolveTypes(T1, SuperRecTy2);
 422           if (NewType2 != 0) {
 423             if (NewType2 != SuperRecTy2) {
 424               delete SuperRecTy2;
 425             }
 426             return NewType2;
 427           }
 428         }
 429       }
 430       return 0;
 431     }
 432     return T2;
 433   }
 434   return T1;
 435 }
 436
 437
 438 //===----------------------------------------------------------------------===//
 439 //    Initializer implementations
 440 //===----------------------------------------------------------------------===//
 441
 442 void Init::dump() const { return print(errs()); }
 443
 444 Init *BitsInit::convertInitializerBitRange(const std::vector<unsigned> &Bits) {
 445   BitsInit *BI = new BitsInit(Bits.size());
 446   for (unsigned i = 0, e = Bits.size(); i != e; ++i) {
 447     if (Bits[i] >= getNumBits()) {
 448       delete BI;
 449       return 0;
 450     }
 451     BI->setBit(i, getBit(Bits[i]));
 452   }
 453   return BI;
 454 }
 455
 456 std::string BitsInit::getAsString() const {
 457   std::string Result = "{ ";
 458   for (unsigned i = 0, e = getNumBits(); i != e; ++i) {
 459     if (i) Result += ", ";
 460     if (Init *Bit = getBit(e-i-1))
 461       Result += Bit->getAsString();
 462     else
 463       Result += "*";
 464   }
 465   return Result + " }";
 466 }
 467
 468 // resolveReferences - If there are any field references that refer to fields
 469 // that have been filled in, we can propagate the values now.
 470 //
 471 Init *BitsInit::resolveReferences(Record &R, const RecordVal *RV) {
 472   bool Changed = false;
 473   BitsInit *New = new BitsInit(getNumBits());
 474
 475   for (unsigned i = 0, e = Bits.size(); i != e; ++i) {
 476     Init *B;
 477     Init *CurBit = getBit(i);
 478
 479     do {
 480       B = CurBit;
 481       CurBit = CurBit->resolveReferences(R, RV);
 482       Changed |= B != CurBit;
 483     } while (B != CurBit);
 484     New->setBit(i, CurBit);
 485   }
 486
 487   if (Changed)
 488     return New;
 489   delete New;
 490   return this;
 491 }
 492
 493 std::string IntInit::getAsString() const {
 494   return itostr(Value);
 495 }
 496
 497 Init *IntInit::convertInitializerBitRange(const std::vector<unsigned> &Bits) {
 498   BitsInit *BI = new BitsInit(Bits.size());
 499
 500   for (unsigned i = 0, e = Bits.size(); i != e; ++i) {
 501     if (Bits[i] >= 64) {
 502       delete BI;
 503       return 0;
 504     }
 505     BI->setBit(i, new BitInit(Value & (INT64_C(1) << Bits[i])));
 506   }
 507   return BI;
 508 }
 509
 510 Init *ListInit::convertInitListSlice(const std::vector<unsigned> &Elements) {
 511   std::vector<Init*> Vals;
 512   for (unsigned i = 0, e = Elements.size(); i != e; ++i) {
 513     if (Elements[i] >= getSize())
 514       return 0;
 515     Vals.push_back(getElement(Elements[i]));
 516   }
 517   return new ListInit(Vals, getType());
 518 }
 519
 520 Record *ListInit::getElementAsRecord(unsigned i) const {
 521   assert(i < Values.size() && "List element index out of range!");
 522   DefInit *DI = dynamic_cast<DefInit*>(Values[i]);
 523   if (DI == 0) throw "Expected record in list!";
 524   return DI->getDef();
 525 }
 526
 527 Init *ListInit::resolveReferences(Record &R, const RecordVal *RV) {
 528   std::vector<Init*> Resolved;
 529   Resolved.reserve(getSize());
 530   bool Changed = false;
 531
 532   for (unsigned i = 0, e = getSize(); i != e; ++i) {
 533     Init *E;
 534     Init *CurElt = getElement(i);
 535
 536     do {
 537       E = CurElt;
 538       CurElt = CurElt->resolveReferences(R, RV);
 539       Changed |= E != CurElt;
 540     } while (E != CurElt);
 541     Resolved.push_back(E);
 542   }
 543
 544   if (Changed)
 545     return new ListInit(Resolved, getType());
 546   return this;
 547 }
 548
 549 Init *ListInit::resolveListElementReference(Record &R, const RecordVal *IRV,
 550                                             unsigned Elt) {
 551   if (Elt >= getSize())
 552     return 0;  // Out of range reference.
 553   Init *E = getElement(Elt);
 554   // If the element is set to some value, or if we are resolving a reference
 555   // to a specific variable and that variable is explicitly unset, then
 556   // replace the VarListElementInit with it.
 557   if (IRV || !dynamic_cast<UnsetInit*>(E))
 558     return E;
 559   return 0;
 560 }
 561
 562 std::string ListInit::getAsString() const {
 563   std::string Result = "[";
 564   for (unsigned i = 0, e = Values.size(); i != e; ++i) {
 565     if (i) Result += ", ";
 566     Result += Values[i]->getAsString();
 567   }
 568   return Result + "]";
 569 }
 570
 571 Init *OpInit::resolveBitReference(Record &R, const RecordVal *IRV,
 572                                   unsigned Bit) {
 573   Init *Folded = Fold(&R, 0);
 574
 575   if (Folded != this) {
 576     TypedInit *Typed = dynamic_cast<TypedInit *>(Folded);
 577     if (Typed) {
 578       return Typed->resolveBitReference(R, IRV, Bit);
 579     }
 580   }
 581
 582   return 0;
 583 }
 584
 585 Init *OpInit::resolveListElementReference(Record &R, const RecordVal *IRV,
 586                                           unsigned Elt) {
 587   Init *Folded = Fold(&R, 0);
 588
 589   if (Folded != this) {
 590     TypedInit *Typed = dynamic_cast<TypedInit *>(Folded);
 591     if (Typed) {
 592       return Typed->resolveListElementReference(R, IRV, Elt);
 593     }
 594   }
 595
 596   return 0;
 597 }
 598
 599 Init *UnOpInit::Fold(Record *CurRec, MultiClass *CurMultiClass) {
 600   switch (getOpcode()) {
 601   default: assert(0 && "Unknown unop");
 602   case CAST: {
 603     if (getType()->getAsString() == "string") {
 604       StringInit *LHSs = dynamic_cast<StringInit*>(LHS);
 605       if (LHSs) {
 606         return LHSs;
 607       }
 608
 609       DefInit *LHSd = dynamic_cast<DefInit*>(LHS);
 610       if (LHSd) {
 611         return new StringInit(LHSd->getDef()->getName());
 612       }
 613     } else {
 614       StringInit *LHSs = dynamic_cast<StringInit*>(LHS);
 615       if (LHSs) {
 616         std::string Name = LHSs->getValue();
 617
 618         // From TGParser::ParseIDValue
 619         if (CurRec) {
 620           if (const RecordVal *RV = CurRec->getValue(Name)) {
 621             if (RV->getType() != getType())
 622               throw "type mismatch in cast";
 623             return new VarInit(Name, RV->getType());
 624           }
 625
 626           std::string TemplateArgName = CurRec->getName()+":"+Name;
 627           if (CurRec->isTemplateArg(TemplateArgName)) {
 628             const RecordVal *RV = CurRec->getValue(TemplateArgName);
 629             assert(RV && "Template arg doesn't exist??");
 630
 631             if (RV->getType() != getType())
 632               throw "type mismatch in cast";
 633
 634             return new VarInit(TemplateArgName, RV->getType());
 635           }
 636         }
 637
 638         if (CurMultiClass) {
 639           std::string MCName = CurMultiClass->Rec.getName()+"::"+Name;
 640           if (CurMultiClass->Rec.isTemplateArg(MCName)) {
 641             const RecordVal *RV = CurMultiClass->Rec.getValue(MCName);
 642             assert(RV && "Template arg doesn't exist??");
 643
 644             if (RV->getType() != getType())
 645               throw "type mismatch in cast";
 646
 647             return new VarInit(MCName, RV->getType());
 648           }
 649         }
 650
 651         if (Record *D = (CurRec->getRecords()).getDef(Name))
 652           return DefInit::get(D);
 653
 654         throw TGError(CurRec->getLoc(), "Undefined reference:'" + Name + "'\n");
 655       }
 656     }
 657     break;
 658   }
 659   case HEAD: {
 660     ListInit *LHSl = dynamic_cast<ListInit*>(LHS);
 661     if (LHSl) {
 662       if (LHSl->getSize() == 0) {
 663         assert(0 && "Empty list in car");
 664         return 0;
 665       }
 666       return LHSl->getElement(0);
 667     }
 668     break;
 669   }
 670   case TAIL: {
 671     ListInit *LHSl = dynamic_cast<ListInit*>(LHS);
 672     if (LHSl) {
 673       if (LHSl->getSize() == 0) {
 674         assert(0 && "Empty list in cdr");
 675         return 0;
 676       }
 677       ListInit *Result = new ListInit(LHSl->begin()+1, LHSl->end(),
 678                                       LHSl->getType());
 679       return Result;
 680     }
 681     break;
 682   }
 683   case EMPTY: {
 684     ListInit *LHSl = dynamic_cast<ListInit*>(LHS);
 685     if (LHSl) {
 686       if (LHSl->getSize() == 0) {
 687         return new IntInit(1);
 688       } else {
 689         return new IntInit(0);
 690       }
 691     }
 692     StringInit *LHSs = dynamic_cast<StringInit*>(LHS);
 693     if (LHSs) {
 694       if (LHSs->getValue().empty()) {
 695         return new IntInit(1);
 696       } else {
 697         return new IntInit(0);
 698       }
 699     }
 700
 701     break;
 702   }
 703   }
 704   return this;
 705 }
 706
 707 Init *UnOpInit::resolveReferences(Record &R, const RecordVal *RV) {
 708   Init *lhs = LHS->resolveReferences(R, RV);
 709
 710   if (LHS != lhs)
 711     return (new UnOpInit(getOpcode(), lhs, getType()))->Fold(&R, 0);
 712   return Fold(&R, 0);
 713 }
 714
 715 std::string UnOpInit::getAsString() const {
 716   std::string Result;
 717   switch (Opc) {
 718   case CAST: Result = "!cast<" + getType()->getAsString() + ">"; break;
 719   case HEAD: Result = "!head"; break;
 720   case TAIL: Result = "!tail"; break;
 721   case EMPTY: Result = "!empty"; break;
 722   }
 723   return Result + "(" + LHS->getAsString() + ")";
 724 }
 725
 726 Init *BinOpInit::Fold(Record *CurRec, MultiClass *CurMultiClass) {
 727   switch (getOpcode()) {
 728   default: assert(0 && "Unknown binop");
 729   case CONCAT: {
 730     DagInit *LHSs = dynamic_cast<DagInit*>(LHS);
 731     DagInit *RHSs = dynamic_cast<DagInit*>(RHS);
 732     if (LHSs && RHSs) {
 733       DefInit *LOp = dynamic_cast<DefInit*>(LHSs->getOperator());
 734       DefInit *ROp = dynamic_cast<DefInit*>(RHSs->getOperator());
 735       if (LOp == 0 || ROp == 0 || LOp->getDef() != ROp->getDef())
 736         throw "Concated Dag operators do not match!";
 737       std::vector<Init*> Args;
 738       std::vector<std::string> ArgNames;
 739       for (unsigned i = 0, e = LHSs->getNumArgs(); i != e; ++i) {
 740         Args.push_back(LHSs->getArg(i));
 741         ArgNames.push_back(LHSs->getArgName(i));
 742       }
 743       for (unsigned i = 0, e = RHSs->getNumArgs(); i != e; ++i) {
 744         Args.push_back(RHSs->getArg(i));
 745         ArgNames.push_back(RHSs->getArgName(i));
 746       }
 747       return new DagInit(LHSs->getOperator(), "", Args, ArgNames);
 748     }
 749     break;
 750   }
 751   case STRCONCAT: {
 752     StringInit *LHSs = dynamic_cast<StringInit*>(LHS);
 753     StringInit *RHSs = dynamic_cast<StringInit*>(RHS);
 754     if (LHSs && RHSs)
 755       return new StringInit(LHSs->getValue() + RHSs->getValue());
 756     break;
 757   }
 758   case EQ: {
 759     // try to fold eq comparison for 'bit' and 'int', otherwise fallback
 760     // to string objects.
 761     IntInit* L =
 762       dynamic_cast<IntInit*>(LHS->convertInitializerTo(IntRecTy::get()));
 763     IntInit* R =
 764       dynamic_cast<IntInit*>(RHS->convertInitializerTo(IntRecTy::get()));
 765
 766     if (L && R)
 767       return new IntInit(L->getValue() == R->getValue());
 768
 769     StringInit *LHSs = dynamic_cast<StringInit*>(LHS);
 770     StringInit *RHSs = dynamic_cast<StringInit*>(RHS);
 771
 772     // Make sure we've resolved
 773     if (LHSs && RHSs)
 774       return new IntInit(LHSs->getValue() == RHSs->getValue());
 775
 776     break;
 777   }
 778   case SHL:
 779   case SRA:
 780   case SRL: {
 781     IntInit *LHSi = dynamic_cast<IntInit*>(LHS);
 782     IntInit *RHSi = dynamic_cast<IntInit*>(RHS);
 783     if (LHSi && RHSi) {
 784       int64_t LHSv = LHSi->getValue(), RHSv = RHSi->getValue();
 785       int64_t Result;
 786       switch (getOpcode()) {
 787       default: assert(0 && "Bad opcode!");
 788       case SHL: Result = LHSv << RHSv; break;
 789       case SRA: Result = LHSv >> RHSv; break;
 790       case SRL: Result = (uint64_t)LHSv >> (uint64_t)RHSv; break;
 791       }
 792       return new IntInit(Result);
 793     }
 794     break;
 795   }
 796   }
 797   return this;
 798 }
 799
 800 Init *BinOpInit::resolveReferences(Record &R, const RecordVal *RV) {
 801   Init *lhs = LHS->resolveReferences(R, RV);
 802   Init *rhs = RHS->resolveReferences(R, RV);
 803
 804   if (LHS != lhs || RHS != rhs)
 805     return (new BinOpInit(getOpcode(), lhs, rhs, getType()))->Fold(&R, 0);
 806   return Fold(&R, 0);
 807 }
 808
 809 std::string BinOpInit::getAsString() const {
 810   std::string Result;
 811   switch (Opc) {
 812   case CONCAT: Result = "!con"; break;
 813   case SHL: Result = "!shl"; break;
 814   case SRA: Result = "!sra"; break;
 815   case SRL: Result = "!srl"; break;
 816   case EQ: Result = "!eq"; break;
 817   case STRCONCAT: Result = "!strconcat"; break;
 818   }
 819   return Result + "(" + LHS->getAsString() + ", " + RHS->getAsString() + ")";
 820 }
 821
 822 static Init *ForeachHelper(Init *LHS, Init *MHS, Init *RHS, RecTy *Type,
 823                            Record *CurRec, MultiClass *CurMultiClass);
 824
 825 static Init *EvaluateOperation(OpInit *RHSo, Init *LHS, Init *Arg,
 826                                RecTy *Type, Record *CurRec,
 827                                MultiClass *CurMultiClass) {
 828   std::vector<Init *> NewOperands;
 829
 830   TypedInit *TArg = dynamic_cast<TypedInit*>(Arg);
 831
 832   // If this is a dag, recurse
 833   if (TArg && TArg->getType()->getAsString() == "dag") {
 834     Init *Result = ForeachHelper(LHS, Arg, RHSo, Type,
 835                                  CurRec, CurMultiClass);
 836     if (Result != 0) {
 837       return Result;
 838     } else {
 839       return 0;
 840     }
 841   }
 842
 843   for (int i = 0; i < RHSo->getNumOperands(); ++i) {
 844     OpInit *RHSoo = dynamic_cast<OpInit*>(RHSo->getOperand(i));
 845
 846     if (RHSoo) {
 847       Init *Result = EvaluateOperation(RHSoo, LHS, Arg,
 848                                        Type, CurRec, CurMultiClass);
 849       if (Result != 0) {
 850         NewOperands.push_back(Result);
 851       } else {
 852         NewOperands.push_back(Arg);
 853       }
 854     } else if (LHS->getAsString() == RHSo->getOperand(i)->getAsString()) {
 855       NewOperands.push_back(Arg);
 856     } else {
 857       NewOperands.push_back(RHSo->getOperand(i));
 858     }
 859   }
 860
 861   // Now run the operator and use its result as the new leaf
 862   OpInit *NewOp = RHSo->clone(NewOperands);
 863   Init *NewVal = NewOp->Fold(CurRec, CurMultiClass);
 864   if (NewVal != NewOp) {
 865     delete NewOp;
 866     return NewVal;
 867   }
 868   return 0;
 869 }
 870
 871 static Init *ForeachHelper(Init *LHS, Init *MHS, Init *RHS, RecTy *Type,
 872                            Record *CurRec, MultiClass *CurMultiClass) {
 873   DagInit *MHSd = dynamic_cast<DagInit*>(MHS);
 874   ListInit *MHSl = dynamic_cast<ListInit*>(MHS);
 875
 876   DagRecTy *DagType = dynamic_cast<DagRecTy*>(Type);
 877   ListRecTy *ListType = dynamic_cast<ListRecTy*>(Type);
 878
 879   OpInit *RHSo = dynamic_cast<OpInit*>(RHS);
 880
 881   if (!RHSo) {
 882     throw TGError(CurRec->getLoc(), "!foreach requires an operator\n");
 883   }
 884
 885   TypedInit *LHSt = dynamic_cast<TypedInit*>(LHS);
 886
 887   if (!LHSt) {
 888     throw TGError(CurRec->getLoc(), "!foreach requires typed variable\n");
 889   }
 890
 891   if ((MHSd && DagType) || (MHSl && ListType)) {
 892     if (MHSd) {
 893       Init *Val = MHSd->getOperator();
 894       Init *Result = EvaluateOperation(RHSo, LHS, Val,
 895                                        Type, CurRec, CurMultiClass);
 896       if (Result != 0) {
 897         Val = Result;
 898       }
 899
 900       std::vector<std::pair<Init *, std::string> > args;
 901       for (unsigned int i = 0; i < MHSd->getNumArgs(); ++i) {
 902         Init *Arg;
 903         std::string ArgName;
 904         Arg = MHSd->getArg(i);
 905         ArgName = MHSd->getArgName(i);
 906
 907         // Process args
 908         Init *Result = EvaluateOperation(RHSo, LHS, Arg, Type,
 909                                          CurRec, CurMultiClass);
 910         if (Result != 0) {
 911           Arg = Result;
 912         }
 913
 914         // TODO: Process arg names
 915         args.push_back(std::make_pair(Arg, ArgName));
 916       }
 917
 918       return new DagInit(Val, "", args);
 919     }
 920     if (MHSl) {
 921       std::vector<Init *> NewOperands;
 922       std::vector<Init *> NewList(MHSl->begin(), MHSl->end());
 923
 924       for (ListInit::iterator li = NewList.begin(),
 925              liend = NewList.end();
 926            li != liend;
 927            ++li) {
 928         Init *Item = *li;
 929         NewOperands.clear();
 930         for(int i = 0; i < RHSo->getNumOperands(); ++i) {
 931           // First, replace the foreach variable with the list item
 932           if (LHS->getAsString() == RHSo->getOperand(i)->getAsString()) {
 933             NewOperands.push_back(Item);
 934           } else {
 935             NewOperands.push_back(RHSo->getOperand(i));
 936           }
 937         }
 938
 939         // Now run the operator and use its result as the new list item
 940         OpInit *NewOp = RHSo->clone(NewOperands);
 941         Init *NewItem = NewOp->Fold(CurRec, CurMultiClass);
 942         if (NewItem != NewOp) {
 943           *li = NewItem;
 944           delete NewOp;
 945         }
 946       }
 947       return new ListInit(NewList, MHSl->getType());
 948     }
 949   }
 950   return 0;
 951 }
 952
 953 Init *TernOpInit::Fold(Record *CurRec, MultiClass *CurMultiClass) {
 954   switch (getOpcode()) {
 955   default: assert(0 && "Unknown binop");
 956   case SUBST: {
 957     DefInit *LHSd = dynamic_cast<DefInit*>(LHS);
 958     VarInit *LHSv = dynamic_cast<VarInit*>(LHS);
 959     StringInit *LHSs = dynamic_cast<StringInit*>(LHS);
 960
 961     DefInit *MHSd = dynamic_cast<DefInit*>(MHS);
 962     VarInit *MHSv = dynamic_cast<VarInit*>(MHS);
 963     StringInit *MHSs = dynamic_cast<StringInit*>(MHS);
 964
 965     DefInit *RHSd = dynamic_cast<DefInit*>(RHS);
 966     VarInit *RHSv = dynamic_cast<VarInit*>(RHS);
 967     StringInit *RHSs = dynamic_cast<StringInit*>(RHS);
 968
 969     if ((LHSd && MHSd && RHSd)
 970         || (LHSv && MHSv && RHSv)
 971         || (LHSs && MHSs && RHSs)) {
 972       if (RHSd) {
 973         Record *Val = RHSd->getDef();
 974         if (LHSd->getAsString() == RHSd->getAsString()) {
 975           Val = MHSd->getDef();
 976         }
 977         return DefInit::get(Val);
 978       }
 979       if (RHSv) {
 980         std::string Val = RHSv->getName();
 981         if (LHSv->getAsString() == RHSv->getAsString()) {
 982           Val = MHSv->getName();
 983         }
 984         return new VarInit(Val, getType());
 985       }
 986       if (RHSs) {
 987         std::string Val = RHSs->getValue();
 988
 989         std::string::size_type found;
 990         std::string::size_type idx = 0;
 991         do {
 992           found = Val.find(LHSs->getValue(), idx);
 993           if (found != std::string::npos) {
 994             Val.replace(found, LHSs->getValue().size(), MHSs->getValue());
 995           }
 996           idx = found +  MHSs->getValue().size();
 997         } while (found != std::string::npos);
 998
 999         return new StringInit(Val);
1000       }
1001     }
1002     break;
1003   }
1004
1005   case FOREACH: {
1006     Init *Result = ForeachHelper(LHS, MHS, RHS, getType(),
1007                                  CurRec, CurMultiClass);
1008     if (Result != 0) {
1009       return Result;
1010     }
1011     break;
1012   }
1013
1014   case IF: {
1015     IntInit *LHSi = dynamic_cast<IntInit*>(LHS);
1016     if (Init *I = LHS->convertInitializerTo(IntRecTy::get()))
1017       LHSi = dynamic_cast<IntInit*>(I);
1018     if (LHSi) {
1019       if (LHSi->getValue()) {
1020         return MHS;
1021       } else {
1022         return RHS;
1023       }
1024     }
1025     break;
1026   }
1027   }
1028
1029   return this;
1030 }
1031
1032 Init *TernOpInit::resolveReferences(Record &R, const RecordVal *RV) {
1033   Init *lhs = LHS->resolveReferences(R, RV);
1034
1035   if (Opc == IF && lhs != LHS) {
1036     IntInit *Value = dynamic_cast<IntInit*>(lhs);
1037     if (Init *I = lhs->convertInitializerTo(IntRecTy::get()))
1038       Value = dynamic_cast<IntInit*>(I);
1039     if (Value != 0) {
1040       // Short-circuit
1041       if (Value->getValue()) {
1042         Init *mhs = MHS->resolveReferences(R, RV);
1043         return (new TernOpInit(getOpcode(), lhs, mhs,
1044                                RHS, getType()))->Fold(&R, 0);
1045       } else {
1046         Init *rhs = RHS->resolveReferences(R, RV);
1047         return (new TernOpInit(getOpcode(), lhs, MHS,
1048                                rhs, getType()))->Fold(&R, 0);
1049       }
1050     }
1051   }
1052
1053   Init *mhs = MHS->resolveReferences(R, RV);
1054   Init *rhs = RHS->resolveReferences(R, RV);
1055
1056   if (LHS != lhs || MHS != mhs || RHS != rhs)
1057     return (new TernOpInit(getOpcode(), lhs, mhs, rhs, getType()))->Fold(&R, 0);
1058   return Fold(&R, 0);
1059 }
1060
1061 std::string TernOpInit::getAsString() const {
1062   std::string Result;
1063   switch (Opc) {
1064   case SUBST: Result = "!subst"; break;
1065   case FOREACH: Result = "!foreach"; break;
1066   case IF: Result = "!if"; break;
1067  }
1068   return Result + "(" + LHS->getAsString() + ", " + MHS->getAsString() + ", "
1069     + RHS->getAsString() + ")";
1070 }
1071
1072 RecTy *TypedInit::getFieldType(const std::string &FieldName) const {
1073   RecordRecTy *RecordType = dynamic_cast<RecordRecTy *>(getType());
1074   if (RecordType) {
1075     RecordVal *Field = RecordType->getRecord()->getValue(FieldName);
1076     if (Field) {
1077       return Field->getType();
1078     }
1079   }
1080   return 0;
1081 }
1082
1083 Init *TypedInit::convertInitializerBitRange(const std::vector<unsigned> &Bits) {
1084   BitsRecTy *T = dynamic_cast<BitsRecTy*>(getType());
1085   if (T == 0) return 0;  // Cannot subscript a non-bits variable.
1086   unsigned NumBits = T->getNumBits();
1087
1088   BitsInit *BI = new BitsInit(Bits.size());
1089   for (unsigned i = 0, e = Bits.size(); i != e; ++i) {
1090     if (Bits[i] >= NumBits) {
1091       delete BI;
1092       return 0;
1093     }
1094     BI->setBit(i, new VarBitInit(this, Bits[i]));
1095   }
1096   return BI;
1097 }
1098
1099 Init *TypedInit::convertInitListSlice(const std::vector<unsigned> &Elements) {
1100   ListRecTy *T = dynamic_cast<ListRecTy*>(getType());
1101   if (T == 0) return 0;  // Cannot subscript a non-list variable.
1102
1103   if (Elements.size() == 1)
1104     return new VarListElementInit(this, Elements[0]);
1105
1106   std::vector<Init*> ListInits;
1107   ListInits.reserve(Elements.size());
1108   for (unsigned i = 0, e = Elements.size(); i != e; ++i)
1109     ListInits.push_back(new VarListElementInit(this, Elements[i]));
1110   return new ListInit(ListInits, T);
1111 }
1112
1113
1114 Init *VarInit::resolveBitReference(Record &R, const RecordVal *IRV,
1115                                    unsigned Bit) {
1116   if (R.isTemplateArg(getName())) return 0;
1117   if (IRV && IRV->getName() != getName()) return 0;
1118
1119   RecordVal *RV = R.getValue(getName());
1120   assert(RV && "Reference to a non-existent variable?");
1121   assert(dynamic_cast<BitsInit*>(RV->getValue()));
1122   BitsInit *BI = (BitsInit*)RV->getValue();
1123
1124   assert(Bit < BI->getNumBits() && "Bit reference out of range!");
1125   Init *B = BI->getBit(Bit);
1126
1127   // If the bit is set to some value, or if we are resolving a reference to a
1128   // specific variable and that variable is explicitly unset, then replace the
1129   // VarBitInit with it.
1130   if (IRV || !dynamic_cast<UnsetInit*>(B))
1131     return B;
1132   return 0;
1133 }
1134
1135 Init *VarInit::resolveListElementReference(Record &R, const RecordVal *IRV,
1136                                            unsigned Elt) {
1137   if (R.isTemplateArg(getName())) return 0;
1138   if (IRV && IRV->getName() != getName()) return 0;
1139
1140   RecordVal *RV = R.getValue(getName());
1141   assert(RV && "Reference to a non-existent variable?");
1142   ListInit *LI = dynamic_cast<ListInit*>(RV->getValue());
1143   if (!LI) {
1144     VarInit *VI = dynamic_cast<VarInit*>(RV->getValue());
1145     assert(VI && "Invalid list element!");
1146     return new VarListElementInit(VI, Elt);
1147   }
1148
1149   if (Elt >= LI->getSize())
1150     return 0;  // Out of range reference.
1151   Init *E = LI->getElement(Elt);
1152   // If the element is set to some value, or if we are resolving a reference
1153   // to a specific variable and that variable is explicitly unset, then
1154   // replace the VarListElementInit with it.
1155   if (IRV || !dynamic_cast<UnsetInit*>(E))
1156     return E;
1157   return 0;
1158 }
1159
1160
1161 RecTy *VarInit::getFieldType(const std::string &FieldName) const {
1162   if (RecordRecTy *RTy = dynamic_cast<RecordRecTy*>(getType()))
1163     if (const RecordVal *RV = RTy->getRecord()->getValue(FieldName))
1164       return RV->getType();
1165   return 0;
1166 }
1167
1168 Init *VarInit::getFieldInit(Record &R, const RecordVal *RV,
1169                             const std::string &FieldName) const {
1170   if (dynamic_cast<RecordRecTy*>(getType()))
1171     if (const RecordVal *Val = R.getValue(VarName)) {
1172       if (RV != Val && (RV || dynamic_cast<UnsetInit*>(Val->getValue())))
1173         return 0;
1174       Init *TheInit = Val->getValue();
1175       assert(TheInit != this && "Infinite loop detected!");
1176       if (Init *I = TheInit->getFieldInit(R, RV, FieldName))
1177         return I;
1178       else
1179         return 0;
1180     }
1181   return 0;
1182 }
1183
1184 /// resolveReferences - This method is used by classes that refer to other
1185 /// variables which may not be defined at the time the expression is formed.
1186 /// If a value is set for the variable later, this method will be called on
1187 /// users of the value to allow the value to propagate out.
1188 ///
1189 Init *VarInit::resolveReferences(Record &R, const RecordVal *RV) {
1190   if (RecordVal *Val = R.getValue(VarName))
1191     if (RV == Val || (RV == 0 && !dynamic_cast<UnsetInit*>(Val->getValue())))
1192       return Val->getValue();
1193   return this;
1194 }
1195
1196 std::string VarBitInit::getAsString() const {
1197    return TI->getAsString() + "{" + utostr(Bit) + "}";
1198 }
1199
1200 Init *VarBitInit::resolveReferences(Record &R, const RecordVal *RV) {
1201   if (Init *I = getVariable()->resolveBitReference(R, RV, getBitNum()))
1202     return I;
1203   return this;
1204 }
1205
1206 std::string VarListElementInit::getAsString() const {
1207   return TI->getAsString() + "[" + utostr(Element) + "]";
1208 }
1209
1210 Init *VarListElementInit::resolveReferences(Record &R, const RecordVal *RV) {
1211   if (Init *I = getVariable()->resolveListElementReference(R, RV,
1212                                                            getElementNum()))
1213     return I;
1214   return this;
1215 }
1216
1217 Init *VarListElementInit::resolveBitReference(Record &R, const RecordVal *RV,
1218                                               unsigned Bit) {
1219   // FIXME: This should be implemented, to support references like:
1220   // bit B = AA[0]{1};
1221   return 0;
1222 }
1223
1224 Init *VarListElementInit::
1225 resolveListElementReference(Record &R, const RecordVal *RV, unsigned Elt) {
1226   // FIXME: This should be implemented, to support references like:
1227   // int B = AA[0][1];
1228   return 0;
1229 }
1230
1231 DefInit *DefInit::get(Record *R) {
1232   return R->getDefInit();
1233 }
1234
1235 RecTy *DefInit::getFieldType(const std::string &FieldName) const {
1236   if (const RecordVal *RV = Def->getValue(FieldName))
1237     return RV->getType();
1238   return 0;
1239 }
1240
1241 Init *DefInit::getFieldInit(Record &R, const RecordVal *RV,
1242                             const std::string &FieldName) const {
1243   return Def->getValue(FieldName)->getValue();
1244 }
1245
1246
1247 std::string DefInit::getAsString() const {
1248   return Def->getName();
1249 }
1250
1251 Init *FieldInit::resolveBitReference(Record &R, const RecordVal *RV,
1252                                      unsigned Bit) {
1253   if (Init *BitsVal = Rec->getFieldInit(R, RV, FieldName))
1254     if (BitsInit *BI = dynamic_cast<BitsInit*>(BitsVal)) {
1255       assert(Bit < BI->getNumBits() && "Bit reference out of range!");
1256       Init *B = BI->getBit(Bit);
1257
1258       if (dynamic_cast<BitInit*>(B))  // If the bit is set.
1259         return B;                     // Replace the VarBitInit with it.
1260     }
1261   return 0;
1262 }
1263
1264 Init *FieldInit::resolveListElementReference(Record &R, const RecordVal *RV,
1265                                              unsigned Elt) {
1266   if (Init *ListVal = Rec->getFieldInit(R, RV, FieldName))
1267     if (ListInit *LI = dynamic_cast<ListInit*>(ListVal)) {
1268       if (Elt >= LI->getSize()) return 0;
1269       Init *E = LI->getElement(Elt);
1270
1271       // If the element is set to some value, or if we are resolving a
1272       // reference to a specific variable and that variable is explicitly
1273       // unset, then replace the VarListElementInit with it.
1274       if (RV || !dynamic_cast<UnsetInit*>(E))
1275         return E;
1276     }
1277   return 0;
1278 }
1279
1280 Init *FieldInit::resolveReferences(Record &R, const RecordVal *RV) {
1281   Init *NewRec = RV ? Rec->resolveReferences(R, RV) : Rec;
1282
1283   Init *BitsVal = NewRec->getFieldInit(R, RV, FieldName);
1284   if (BitsVal) {
1285     Init *BVR = BitsVal->resolveReferences(R, RV);
1286     return BVR->isComplete() ? BVR : this;
1287   }
1288
1289   if (NewRec != Rec) {
1290     return new FieldInit(NewRec, FieldName);
1291   }
1292   return this;
1293 }
1294
1295 Init *DagInit::resolveReferences(Record &R, const RecordVal *RV) {
1296   std::vector<Init*> NewArgs;
1297   for (unsigned i = 0, e = Args.size(); i != e; ++i)
1298     NewArgs.push_back(Args[i]->resolveReferences(R, RV));
1299
1300   Init *Op = Val->resolveReferences(R, RV);
1301
1302   if (Args != NewArgs || Op != Val)
1303     return new DagInit(Op, ValName, NewArgs, ArgNames);
1304
1305   return this;
1306 }
1307
1308
1309 std::string DagInit::getAsString() const {
1310   std::string Result = "(" + Val->getAsString();
1311   if (!ValName.empty())
1312     Result += ":" + ValName;
1313   if (Args.size()) {
1314     Result += " " + Args[0]->getAsString();
1315     if (!ArgNames[0].empty()) Result += ":$" + ArgNames[0];
1316     for (unsigned i = 1, e = Args.size(); i != e; ++i) {
1317       Result += ", " + Args[i]->getAsString();
1318       if (!ArgNames[i].empty()) Result += ":$" + ArgNames[i];
1319     }
1320   }
1321   return Result + ")";
1322 }
1323
1324
1325 //===----------------------------------------------------------------------===//
1326 //    Other implementations
1327 //===----------------------------------------------------------------------===//
1328
1329 RecordVal::RecordVal(const std::string &N, RecTy *T, unsigned P)
1330   : Name(N), Ty(T), Prefix(P) {
1331   Value = Ty->convertValue(new UnsetInit());
1332   assert(Value && "Cannot create unset value for current type!");
1333 }
1334
1335 void RecordVal::dump() const { errs() << *this; }
1336
1337 void RecordVal::print(raw_ostream &OS, bool PrintSem) const {
1338   if (getPrefix()) OS << "field ";
1339   OS << *getType() << " " << getName();
1340
1341   if (getValue())
1342     OS << " = " << *getValue();
1343
1344   if (PrintSem) OS << ";\n";
1345 }
1346
1347 unsigned Record::LastID = 0;
1348
1349 DefInit *Record::getDefInit() {
1350   if (!TheInit)
1351     TheInit = new DefInit(this, new RecordRecTy(this));
1352   return TheInit;
1353 }
1354
1355 void Record::setName(const std::string &Name) {
1356   if (TrackedRecords.getDef(getName()) == this) {
1357     TrackedRecords.removeDef(getName());
1358     this->Name = Name;
1359     TrackedRecords.addDef(this);
1360   } else {
1361     TrackedRecords.removeClass(getName());
1362     this->Name = Name;
1363     TrackedRecords.addClass(this);
1364   }
1365 }
1366
1367 /// resolveReferencesTo - If anything in this record refers to RV, replace the
1368 /// reference to RV with the RHS of RV.  If RV is null, we resolve all possible
1369 /// references.
1370 void Record::resolveReferencesTo(const RecordVal *RV) {
1371   for (unsigned i = 0, e = Values.size(); i != e; ++i) {
1372     if (Init *V = Values[i].getValue())
1373       Values[i].setValue(V->resolveReferences(*this, RV));
1374   }
1375 }
1376
1377 void Record::dump() const { errs() << *this; }
1378
1379 raw_ostream &llvm::operator<<(raw_ostream &OS, const Record &R) {
1380   OS << R.getName();
1381
1382   const std::vector<std::string> &TArgs = R.getTemplateArgs();
1383   if (!TArgs.empty()) {
1384     OS << "<";
1385     for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
1386       if (i) OS << ", ";
1387       const RecordVal *RV = R.getValue(TArgs[i]);
1388       assert(RV && "Template argument record not found??");
1389       RV->print(OS, false);
1390     }
1391     OS << ">";
1392   }
1393
1394   OS << " {";
1395   const std::vector<Record*> &SC = R.getSuperClasses();
1396   if (!SC.empty()) {
1397     OS << "\t//";
1398     for (unsigned i = 0, e = SC.size(); i != e; ++i)
1399       OS << " " << SC[i]->getName();
1400   }
1401   OS << "\n";
1402
1403   const std::vector<RecordVal> &Vals = R.getValues();
1404   for (unsigned i = 0, e = Vals.size(); i != e; ++i)
1405     if (Vals[i].getPrefix() && !R.isTemplateArg(Vals[i].getName()))
1406       OS << Vals[i];
1407   for (unsigned i = 0, e = Vals.size(); i != e; ++i)
1408     if (!Vals[i].getPrefix() && !R.isTemplateArg(Vals[i].getName()))
1409       OS << Vals[i];
1410
1411   return OS << "}\n";
1412 }
1413
1414 /// getValueInit - Return the initializer for a value with the specified name,
1415 /// or throw an exception if the field does not exist.
1416 ///
1417 Init *Record::getValueInit(StringRef FieldName) const {
1418   const RecordVal *R = getValue(FieldName);
1419   if (R == 0 || R->getValue() == 0)
1420     throw "Record `" + getName() + "' does not have a field named `" +
1421       FieldName.str() + "'!\n";
1422   return R->getValue();
1423 }
1424
1425
1426 /// getValueAsString - This method looks up the specified field and returns its
1427 /// value as a string, throwing an exception if the field does not exist or if
1428 /// the value is not a string.
1429 ///
1430 std::string Record::getValueAsString(StringRef FieldName) const {
1431   const RecordVal *R = getValue(FieldName);
1432   if (R == 0 || R->getValue() == 0)
1433     throw "Record `" + getName() + "' does not have a field named `" +
1434           FieldName.str() + "'!\n";
1435
1436   if (const StringInit *SI = dynamic_cast<const StringInit*>(R->getValue()))
1437     return SI->getValue();
1438   throw "Record `" + getName() + "', field `" + FieldName.str() +
1439         "' does not have a string initializer!";
1440 }
1441
1442 /// getValueAsBitsInit - This method looks up the specified field and returns
1443 /// its value as a BitsInit, throwing an exception if the field does not exist
1444 /// or if the value is not the right type.
1445 ///
1446 BitsInit *Record::getValueAsBitsInit(StringRef FieldName) const {
1447   const RecordVal *R = getValue(FieldName);
1448   if (R == 0 || R->getValue() == 0)
1449     throw "Record `" + getName() + "' does not have a field named `" +
1450           FieldName.str() + "'!\n";
1451
1452   if (BitsInit *BI = dynamic_cast<BitsInit*>(R->getValue()))
1453     return BI;
1454   throw "Record `" + getName() + "', field `" + FieldName.str() +
1455         "' does not have a BitsInit initializer!";
1456 }
1457
1458 /// getValueAsListInit - This method looks up the specified field and returns
1459 /// its value as a ListInit, throwing an exception if the field does not exist
1460 /// or if the value is not the right type.
1461 ///
1462 ListInit *Record::getValueAsListInit(StringRef FieldName) const {
1463   const RecordVal *R = getValue(FieldName);
1464   if (R == 0 || R->getValue() == 0)
1465     throw "Record `" + getName() + "' does not have a field named `" +
1466           FieldName.str() + "'!\n";
1467
1468   if (ListInit *LI = dynamic_cast<ListInit*>(R->getValue()))
1469     return LI;
1470   throw "Record `" + getName() + "', field `" + FieldName.str() +
1471         "' does not have a list initializer!";
1472 }
1473
1474 /// getValueAsListOfDefs - This method looks up the specified field and returns
1475 /// its value as a vector of records, throwing an exception if the field does
1476 /// not exist or if the value is not the right type.
1477 ///
1478 std::vector<Record*>
1479 Record::getValueAsListOfDefs(StringRef FieldName) const {
1480   ListInit *List = getValueAsListInit(FieldName);
1481   std::vector<Record*> Defs;
1482   for (unsigned i = 0; i < List->getSize(); i++) {
1483     if (DefInit *DI = dynamic_cast<DefInit*>(List->getElement(i))) {
1484       Defs.push_back(DI->getDef());
1485     } else {
1486       throw "Record `" + getName() + "', field `" + FieldName.str() +
1487             "' list is not entirely DefInit!";
1488     }
1489   }
1490   return Defs;
1491 }
1492
1493 /// getValueAsInt - This method looks up the specified field and returns its
1494 /// value as an int64_t, throwing an exception if the field does not exist or if
1495 /// the value is not the right type.
1496 ///
1497 int64_t Record::getValueAsInt(StringRef FieldName) const {
1498   const RecordVal *R = getValue(FieldName);
1499   if (R == 0 || R->getValue() == 0)
1500     throw "Record `" + getName() + "' does not have a field named `" +
1501           FieldName.str() + "'!\n";
1502
1503   if (IntInit *II = dynamic_cast<IntInit*>(R->getValue()))
1504     return II->getValue();
1505   throw "Record `" + getName() + "', field `" + FieldName.str() +
1506         "' does not have an int initializer!";
1507 }
1508
1509 /// getValueAsListOfInts - This method looks up the specified field and returns
1510 /// its value as a vector of integers, throwing an exception if the field does
1511 /// not exist or if the value is not the right type.
1512 ///
1513 std::vector<int64_t>
1514 Record::getValueAsListOfInts(StringRef FieldName) const {
1515   ListInit *List = getValueAsListInit(FieldName);
1516   std::vector<int64_t> Ints;
1517   for (unsigned i = 0; i < List->getSize(); i++) {
1518     if (IntInit *II = dynamic_cast<IntInit*>(List->getElement(i))) {
1519       Ints.push_back(II->getValue());
1520     } else {
1521       throw "Record `" + getName() + "', field `" + FieldName.str() +
1522             "' does not have a list of ints initializer!";
1523     }
1524   }
1525   return Ints;
1526 }
1527
1528 /// getValueAsListOfStrings - This method looks up the specified field and
1529 /// returns its value as a vector of strings, throwing an exception if the
1530 /// field does not exist or if the value is not the right type.
1531 ///
1532 std::vector<std::string>
1533 Record::getValueAsListOfStrings(StringRef FieldName) const {
1534   ListInit *List = getValueAsListInit(FieldName);
1535   std::vector<std::string> Strings;
1536   for (unsigned i = 0; i < List->getSize(); i++) {
1537     if (StringInit *II = dynamic_cast<StringInit*>(List->getElement(i))) {
1538       Strings.push_back(II->getValue());
1539     } else {
1540       throw "Record `" + getName() + "', field `" + FieldName.str() +
1541             "' does not have a list of strings initializer!";
1542     }
1543   }
1544   return Strings;
1545 }
1546
1547 /// getValueAsDef - This method looks up the specified field and returns its
1548 /// value as a Record, throwing an exception if the field does not exist or if
1549 /// the value is not the right type.
1550 ///
1551 Record *Record::getValueAsDef(StringRef FieldName) const {
1552   const RecordVal *R = getValue(FieldName);
1553   if (R == 0 || R->getValue() == 0)
1554     throw "Record `" + getName() + "' does not have a field named `" +
1555       FieldName.str() + "'!\n";
1556
1557   if (DefInit *DI = dynamic_cast<DefInit*>(R->getValue()))
1558     return DI->getDef();
1559   throw "Record `" + getName() + "', field `" + FieldName.str() +
1560         "' does not have a def initializer!";
1561 }
1562
1563 /// getValueAsBit - This method looks up the specified field and returns its
1564 /// value as a bit, throwing an exception if the field does not exist or if
1565 /// the value is not the right type.
1566 ///
1567 bool Record::getValueAsBit(StringRef FieldName) const {
1568   const RecordVal *R = getValue(FieldName);
1569   if (R == 0 || R->getValue() == 0)
1570     throw "Record `" + getName() + "' does not have a field named `" +
1571       FieldName.str() + "'!\n";
1572
1573   if (BitInit *BI = dynamic_cast<BitInit*>(R->getValue()))
1574     return BI->getValue();
1575   throw "Record `" + getName() + "', field `" + FieldName.str() +
1576         "' does not have a bit initializer!";
1577 }
1578
1579 /// getValueAsDag - This method looks up the specified field and returns its
1580 /// value as an Dag, throwing an exception if the field does not exist or if
1581 /// the value is not the right type.
1582 ///
1583 DagInit *Record::getValueAsDag(StringRef FieldName) const {
1584   const RecordVal *R = getValue(FieldName);
1585   if (R == 0 || R->getValue() == 0)
1586     throw "Record `" + getName() + "' does not have a field named `" +
1587       FieldName.str() + "'!\n";
1588
1589   if (DagInit *DI = dynamic_cast<DagInit*>(R->getValue()))
1590     return DI;
1591   throw "Record `" + getName() + "', field `" + FieldName.str() +
1592         "' does not have a dag initializer!";
1593 }
1594
1595 std::string Record::getValueAsCode(StringRef FieldName) const {
1596   const RecordVal *R = getValue(FieldName);
1597   if (R == 0 || R->getValue() == 0)
1598     throw "Record `" + getName() + "' does not have a field named `" +
1599       FieldName.str() + "'!\n";
1600
1601   if (const CodeInit *CI = dynamic_cast<const CodeInit*>(R->getValue()))
1602     return CI->getValue();
1603   throw "Record `" + getName() + "', field `" + FieldName.str() +
1604     "' does not have a code initializer!";
1605 }
1606
1607
1608 void MultiClass::dump() const {
1609   errs() << "Record:\n";
1610   Rec.dump();
1611
1612   errs() << "Defs:\n";
1613   for (RecordVector::const_iterator r = DefPrototypes.begin(),
1614          rend = DefPrototypes.end();
1615        r != rend;
1616        ++r) {
1617     (*r)->dump();
1618   }
1619 }
1620
1621
1622 void RecordKeeper::dump() const { errs() << *this; }
1623
1624 raw_ostream &llvm::operator<<(raw_ostream &OS, const RecordKeeper &RK) {
1625   OS << "------------- Classes -----------------\n";
1626   const std::map<std::string, Record*> &Classes = RK.getClasses();
1627   for (std::map<std::string, Record*>::const_iterator I = Classes.begin(),
1628          E = Classes.end(); I != E; ++I)
1629     OS << "class " << *I->second;
1630
1631   OS << "------------- Defs -----------------\n";
1632   const std::map<std::string, Record*> &Defs = RK.getDefs();
1633   for (std::map<std::string, Record*>::const_iterator I = Defs.begin(),
1634          E = Defs.end(); I != E; ++I)
1635     OS << "def " << *I->second;
1636   return OS;
1637 }
1638
1639
1640 /// getAllDerivedDefinitions - This method returns all concrete definitions
1641 /// that derive from the specified class name.  If a class with the specified
1642 /// name does not exist, an error is printed and true is returned.
1643 std::vector<Record*>
1644 RecordKeeper::getAllDerivedDefinitions(const std::string &ClassName) const {
1645   Record *Class = getClass(ClassName);
1646   if (!Class)
1647     throw "ERROR: Couldn't find the `" + ClassName + "' class!\n";
1648
1649   std::vector<Record*> Defs;
1650   for (std::map<std::string, Record*>::const_iterator I = getDefs().begin(),
1651          E = getDefs().end(); I != E; ++I)
1652     if (I->second->isSubClassOf(Class))
1653       Defs.push_back(I->second);
1654
1655   return Defs;
1656 }
1657