include/llvm/TableGen/Record.h

   1 //===- llvm/TableGen/Record.h - Classes for Table Records -------*- C++ -*-===//
   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 // This file defines the main TableGen data structures, including the TableGen
  11 // types, values, and high-level data structures.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_TABLEGEN_RECORD_H
  16 #define LLVM_TABLEGEN_RECORD_H
  17
  18 #include "llvm/ADT/ArrayRef.h"
  19 #include "llvm/ADT/FoldingSet.h"
  20 #include "llvm/Support/Allocator.h"
  21 #include "llvm/Support/Casting.h"
  22 #include "llvm/Support/DataTypes.h"
  23 #include "llvm/Support/ErrorHandling.h"
  24 #include "llvm/Support/SourceMgr.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 #include <map>
  27
  28 namespace llvm {
  29
  30 // RecTy subclasses.
  31 class BitRecTy;
  32 class BitsRecTy;
  33 class IntRecTy;
  34 class StringRecTy;
  35 class ListRecTy;
  36 class DagRecTy;
  37 class RecordRecTy;
  38
  39 // Init subclasses.
  40 class Init;
  41 class UnsetInit;
  42 class BitInit;
  43 class BitsInit;
  44 class IntInit;
  45 class StringInit;
  46 class ListInit;
  47 class UnOpInit;
  48 class BinOpInit;
  49 class TernOpInit;
  50 class DefInit;
  51 class DagInit;
  52 class TypedInit;
  53 class VarInit;
  54 class FieldInit;
  55 class VarBitInit;
  56 class VarListElementInit;
  57
  58 // Other classes.
  59 class Record;
  60 class RecordVal;
  61 struct MultiClass;
  62 class RecordKeeper;
  63
  64 //===----------------------------------------------------------------------===//
  65 //  Type Classes
  66 //===----------------------------------------------------------------------===//
  67
  68 class RecTy {
  69 public:
  70   /// \brief Subclass discriminator (for dyn_cast<> et al.)
  71   enum RecTyKind {
  72     BitRecTyKind,
  73     BitsRecTyKind,
  74     IntRecTyKind,
  75     StringRecTyKind,
  76     ListRecTyKind,
  77     DagRecTyKind,
  78     RecordRecTyKind
  79   };
  80
  81 private:
  82   RecTyKind Kind;
  83   std::unique_ptr<ListRecTy> ListTy;
  84   virtual void anchor();
  85
  86 public:
  87   RecTyKind getRecTyKind() const { return Kind; }
  88
  89   RecTy(RecTyKind K) : Kind(K), ListTy(nullptr) {}
  90   virtual ~RecTy() {}
  91
  92   virtual std::string getAsString() const = 0;
  93   void print(raw_ostream &OS) const { OS << getAsString(); }
  94   void dump() const;
  95
  96   /// typeIsConvertibleTo - Return true if all values of 'this' type can be
  97   /// converted to the specified type.
  98   virtual bool typeIsConvertibleTo(const RecTy *RHS) const = 0;
  99
 100   /// getListTy - Returns the type representing list<this>.
 101   ListRecTy *getListTy();
 102
 103 public:   // These methods should only be called from subclasses of Init
 104   virtual Init *convertValue( UnsetInit *UI) { return nullptr; }
 105   virtual Init *convertValue(   BitInit *BI) { return nullptr; }
 106   virtual Init *convertValue(  BitsInit *BI) { return nullptr; }
 107   virtual Init *convertValue(   IntInit *II) { return nullptr; }
 108   virtual Init *convertValue(StringInit *SI) { return nullptr; }
 109   virtual Init *convertValue(  ListInit *LI) { return nullptr; }
 110   virtual Init *convertValue(VarBitInit *VB) { return nullptr; }
 111   virtual Init *convertValue(   DefInit *DI) { return nullptr; }
 112   virtual Init *convertValue(   DagInit *DI) { return nullptr; }
 113   virtual Init *convertValue( TypedInit *TI) { return nullptr; }
 114   virtual Init *convertValue(   VarInit *VI) {
 115     return convertValue((TypedInit*)VI);
 116   }
 117   virtual Init *convertValue( FieldInit *FI) {
 118     return convertValue((TypedInit*)FI);
 119   }
 120
 121 public:
 122   virtual bool baseClassOf(const RecTy*) const;
 123 };
 124
 125 inline raw_ostream &operator<<(raw_ostream &OS, const RecTy &Ty) {
 126   Ty.print(OS);
 127   return OS;
 128 }
 129
 130 /// BitRecTy - 'bit' - Represent a single bit
 131 ///
 132 class BitRecTy : public RecTy {
 133   static BitRecTy Shared;
 134   BitRecTy() : RecTy(BitRecTyKind) {}
 135
 136 public:
 137   static bool classof(const RecTy *RT) {
 138     return RT->getRecTyKind() == BitRecTyKind;
 139   }
 140
 141   static BitRecTy *get() { return &Shared; }
 142
 143   using RecTy::convertValue;
 144   Init *convertValue( UnsetInit *UI) override { return (Init*)UI; }
 145   Init *convertValue(   BitInit *BI) override { return (Init*)BI; }
 146   Init *convertValue(  BitsInit *BI) override;
 147   Init *convertValue(   IntInit *II) override;
 148   Init *convertValue(VarBitInit *VB) override { return (Init*)VB; }
 149   Init *convertValue( TypedInit *TI) override;
 150
 151   std::string getAsString() const override { return "bit"; }
 152
 153   bool typeIsConvertibleTo(const RecTy *RHS) const override {
 154     return RHS->baseClassOf(this);
 155   }
 156   bool baseClassOf(const RecTy*) const override;
 157 };
 158
 159 /// BitsRecTy - 'bits<n>' - Represent a fixed number of bits
 160 ///
 161 class BitsRecTy : public RecTy {
 162   unsigned Size;
 163   explicit BitsRecTy(unsigned Sz) : RecTy(BitsRecTyKind), Size(Sz) {}
 164
 165 public:
 166   static bool classof(const RecTy *RT) {
 167     return RT->getRecTyKind() == BitsRecTyKind;
 168   }
 169
 170   static BitsRecTy *get(unsigned Sz);
 171
 172   unsigned getNumBits() const { return Size; }
 173
 174   using RecTy::convertValue;
 175   Init *convertValue( UnsetInit *UI) override;
 176   Init *convertValue(   BitInit *UI) override;
 177   Init *convertValue(  BitsInit *BI) override;
 178   Init *convertValue(   IntInit *II) override;
 179   Init *convertValue( TypedInit *TI) override;
 180
 181   std::string getAsString() const override;
 182
 183   bool typeIsConvertibleTo(const RecTy *RHS) const override {
 184     return RHS->baseClassOf(this);
 185   }
 186   bool baseClassOf(const RecTy*) const override;
 187 };
 188
 189 /// IntRecTy - 'int' - Represent an integer value of no particular size
 190 ///
 191 class IntRecTy : public RecTy {
 192   static IntRecTy Shared;
 193   IntRecTy() : RecTy(IntRecTyKind) {}
 194
 195 public:
 196   static bool classof(const RecTy *RT) {
 197     return RT->getRecTyKind() == IntRecTyKind;
 198   }
 199
 200   static IntRecTy *get() { return &Shared; }
 201
 202   using RecTy::convertValue;
 203   Init *convertValue( UnsetInit *UI) override { return (Init*)UI; }
 204   Init *convertValue(   BitInit *BI) override;
 205   Init *convertValue(  BitsInit *BI) override;
 206   Init *convertValue(   IntInit *II) override { return (Init*)II; }
 207   Init *convertValue( TypedInit *TI) override;
 208
 209   std::string getAsString() const override { return "int"; }
 210
 211   bool typeIsConvertibleTo(const RecTy *RHS) const override {
 212     return RHS->baseClassOf(this);
 213   }
 214
 215   bool baseClassOf(const RecTy*) const override;
 216 };
 217
 218 /// StringRecTy - 'string' - Represent an string value
 219 ///
 220 class StringRecTy : public RecTy {
 221   static StringRecTy Shared;
 222   StringRecTy() : RecTy(StringRecTyKind) {}
 223
 224 public:
 225   static bool classof(const RecTy *RT) {
 226     return RT->getRecTyKind() == StringRecTyKind;
 227   }
 228
 229   static StringRecTy *get() { return &Shared; }
 230
 231   using RecTy::convertValue;
 232   Init *convertValue( UnsetInit *UI) override { return (Init*)UI; }
 233   Init *convertValue(StringInit *SI) override { return (Init*)SI; }
 234   Init *convertValue( TypedInit *TI) override;
 235
 236   std::string getAsString() const override { return "string"; }
 237
 238   bool typeIsConvertibleTo(const RecTy *RHS) const override {
 239     return RHS->baseClassOf(this);
 240   }
 241 };
 242
 243 /// ListRecTy - 'list<Ty>' - Represent a list of values, all of which must be of
 244 /// the specified type.
 245 ///
 246 class ListRecTy : public RecTy {
 247   RecTy *Ty;
 248   explicit ListRecTy(RecTy *T) : RecTy(ListRecTyKind), Ty(T) {}
 249   friend ListRecTy *RecTy::getListTy();
 250
 251 public:
 252   static bool classof(const RecTy *RT) {
 253     return RT->getRecTyKind() == ListRecTyKind;
 254   }
 255
 256   static ListRecTy *get(RecTy *T) { return T->getListTy(); }
 257   RecTy *getElementType() const { return Ty; }
 258
 259   using RecTy::convertValue;
 260   Init *convertValue( UnsetInit *UI) override { return (Init*)UI; }
 261   Init *convertValue(  ListInit *LI) override;
 262   Init *convertValue( TypedInit *TI) override;
 263
 264   std::string getAsString() const override;
 265
 266   bool typeIsConvertibleTo(const RecTy *RHS) const override {
 267     return RHS->baseClassOf(this);
 268   }
 269
 270   bool baseClassOf(const RecTy*) const override;
 271 };
 272
 273 /// DagRecTy - 'dag' - Represent a dag fragment
 274 ///
 275 class DagRecTy : public RecTy {
 276   static DagRecTy Shared;
 277   DagRecTy() : RecTy(DagRecTyKind) {}
 278
 279 public:
 280   static bool classof(const RecTy *RT) {
 281     return RT->getRecTyKind() == DagRecTyKind;
 282   }
 283
 284   static DagRecTy *get() { return &Shared; }
 285
 286   using RecTy::convertValue;
 287   Init *convertValue( UnsetInit *UI) override { return (Init*)UI; }
 288   Init *convertValue(   DagInit *DI) override { return (Init*)DI; }
 289   Init *convertValue( TypedInit *TI) override;
 290
 291   std::string getAsString() const override { return "dag"; }
 292
 293   bool typeIsConvertibleTo(const RecTy *RHS) const override {
 294     return RHS->baseClassOf(this);
 295   }
 296 };
 297
 298 /// RecordRecTy - '[classname]' - Represent an instance of a class, such as:
 299 /// (R32 X = EAX).
 300 ///
 301 class RecordRecTy : public RecTy {
 302   Record *Rec;
 303   explicit RecordRecTy(Record *R) : RecTy(RecordRecTyKind), Rec(R) {}
 304   friend class Record;
 305
 306 public:
 307   static bool classof(const RecTy *RT) {
 308     return RT->getRecTyKind() == RecordRecTyKind;
 309   }
 310
 311   static RecordRecTy *get(Record *R);
 312
 313   Record *getRecord() const { return Rec; }
 314
 315   using RecTy::convertValue;
 316   Init *convertValue( UnsetInit *UI) override { return (Init*)UI; }
 317   Init *convertValue(   DefInit *DI) override;
 318   Init *convertValue( TypedInit *TI) override;
 319
 320   std::string getAsString() const override;
 321
 322   bool typeIsConvertibleTo(const RecTy *RHS) const override {
 323     return RHS->baseClassOf(this);
 324   }
 325   bool baseClassOf(const RecTy*) const override;
 326 };
 327
 328 /// resolveTypes - Find a common type that T1 and T2 convert to.
 329 /// Return 0 if no such type exists.
 330 ///
 331 RecTy *resolveTypes(RecTy *T1, RecTy *T2);
 332
 333 //===----------------------------------------------------------------------===//
 334 //  Initializer Classes
 335 //===----------------------------------------------------------------------===//
 336
 337 class Init {
 338 protected:
 339   /// \brief Discriminator enum (for isa<>, dyn_cast<>, et al.)
 340   ///
 341   /// This enum is laid out by a preorder traversal of the inheritance
 342   /// hierarchy, and does not contain an entry for abstract classes, as per
 343   /// the recommendation in docs/HowToSetUpLLVMStyleRTTI.rst.
 344   ///
 345   /// We also explicitly include "first" and "last" values for each
 346   /// interior node of the inheritance tree, to make it easier to read the
 347   /// corresponding classof().
 348   ///
 349   /// We could pack these a bit tighter by not having the IK_FirstXXXInit
 350   /// and IK_LastXXXInit be their own values, but that would degrade
 351   /// readability for really no benefit.
 352   enum InitKind {
 353     IK_BitInit,
 354     IK_FirstTypedInit,
 355     IK_BitsInit,
 356     IK_DagInit,
 357     IK_DefInit,
 358     IK_FieldInit,
 359     IK_IntInit,
 360     IK_ListInit,
 361     IK_FirstOpInit,
 362     IK_BinOpInit,
 363     IK_TernOpInit,
 364     IK_UnOpInit,
 365     IK_LastOpInit,
 366     IK_StringInit,
 367     IK_VarInit,
 368     IK_VarListElementInit,
 369     IK_LastTypedInit,
 370     IK_UnsetInit,
 371     IK_VarBitInit
 372   };
 373
 374 private:
 375   const InitKind Kind;
 376   Init(const Init &) = delete;
 377   Init &operator=(const Init &) = delete;
 378   virtual void anchor();
 379
 380 public:
 381   InitKind getKind() const { return Kind; }
 382
 383 protected:
 384   explicit Init(InitKind K) : Kind(K) {}
 385
 386 public:
 387   virtual ~Init() {}
 388
 389   /// isComplete - This virtual method should be overridden by values that may
 390   /// not be completely specified yet.
 391   virtual bool isComplete() const { return true; }
 392
 393   /// print - Print out this value.
 394   void print(raw_ostream &OS) const { OS << getAsString(); }
 395
 396   /// getAsString - Convert this value to a string form.
 397   virtual std::string getAsString() const = 0;
 398   /// getAsUnquotedString - Convert this value to a string form,
 399   /// without adding quote markers.  This primaruly affects
 400   /// StringInits where we will not surround the string value with
 401   /// quotes.
 402   virtual std::string getAsUnquotedString() const { return getAsString(); }
 403
 404   /// dump - Debugging method that may be called through a debugger, just
 405   /// invokes print on stderr.
 406   void dump() const;
 407
 408   /// convertInitializerTo - This virtual function is a simple call-back
 409   /// function that should be overridden to call the appropriate
 410   /// RecTy::convertValue method.
 411   ///
 412   virtual Init *convertInitializerTo(RecTy *Ty) const = 0;
 413
 414   /// convertInitializerBitRange - This method is used to implement the bitrange
 415   /// selection operator.  Given an initializer, it selects the specified bits
 416   /// out, returning them as a new init of bits type.  If it is not legal to use
 417   /// the bit subscript operator on this initializer, return null.
 418   ///
 419   virtual Init *
 420   convertInitializerBitRange(const std::vector<unsigned> &Bits) const {
 421     return nullptr;
 422   }
 423
 424   /// convertInitListSlice - This method is used to implement the list slice
 425   /// selection operator.  Given an initializer, it selects the specified list
 426   /// elements, returning them as a new init of list type.  If it is not legal
 427   /// to take a slice of this, return null.
 428   ///
 429   virtual Init *
 430   convertInitListSlice(const std::vector<unsigned> &Elements) const {
 431     return nullptr;
 432   }
 433
 434   /// getFieldType - This method is used to implement the FieldInit class.
 435   /// Implementors of this method should return the type of the named field if
 436   /// they are of record type.
 437   ///
 438   virtual RecTy *getFieldType(const std::string &FieldName) const {
 439     return nullptr;
 440   }
 441
 442   /// getFieldInit - This method complements getFieldType to return the
 443   /// initializer for the specified field.  If getFieldType returns non-null
 444   /// this method should return non-null, otherwise it returns null.
 445   ///
 446   virtual Init *getFieldInit(Record &R, const RecordVal *RV,
 447                              const std::string &FieldName) const {
 448     return nullptr;
 449   }
 450
 451   /// resolveReferences - This method is used by classes that refer to other
 452   /// variables which may not be defined at the time the expression is formed.
 453   /// If a value is set for the variable later, this method will be called on
 454   /// users of the value to allow the value to propagate out.
 455   ///
 456   virtual Init *resolveReferences(Record &R, const RecordVal *RV) const {
 457     return const_cast<Init *>(this);
 458   }
 459
 460   /// getBit - This method is used to return the initializer for the specified
 461   /// bit.
 462   virtual Init *getBit(unsigned Bit) const = 0;
 463
 464   /// getBitVar - This method is used to retrieve the initializer for bit
 465   /// reference. For non-VarBitInit, it simply returns itself.
 466   virtual Init *getBitVar() const { return const_cast<Init*>(this); }
 467
 468   /// getBitNum - This method is used to retrieve the bit number of a bit
 469   /// reference. For non-VarBitInit, it simply returns 0.
 470   virtual unsigned getBitNum() const { return 0; }
 471 };
 472
 473 inline raw_ostream &operator<<(raw_ostream &OS, const Init &I) {
 474   I.print(OS); return OS;
 475 }
 476
 477 /// TypedInit - This is the common super-class of types that have a specific,
 478 /// explicit, type.
 479 ///
 480 class TypedInit : public Init {
 481   RecTy *Ty;
 482
 483   TypedInit(const TypedInit &Other) = delete;
 484   TypedInit &operator=(const TypedInit &Other) = delete;
 485
 486 protected:
 487   explicit TypedInit(InitKind K, RecTy *T) : Init(K), Ty(T) {}
 488   ~TypedInit() {
 489     // If this is a DefInit we need to delete the RecordRecTy.
 490     if (getKind() == IK_DefInit)
 491       delete Ty;
 492   }
 493
 494 public:
 495   static bool classof(const Init *I) {
 496     return I->getKind() >= IK_FirstTypedInit &&
 497            I->getKind() <= IK_LastTypedInit;
 498   }
 499   RecTy *getType() const { return Ty; }
 500
 501   Init *
 502   convertInitializerBitRange(const std::vector<unsigned> &Bits) const override;
 503   Init *
 504   convertInitListSlice(const std::vector<unsigned> &Elements) const override;
 505
 506   /// getFieldType - This method is used to implement the FieldInit class.
 507   /// Implementors of this method should return the type of the named field if
 508   /// they are of record type.
 509   ///
 510   RecTy *getFieldType(const std::string &FieldName) const override;
 511
 512   /// resolveListElementReference - This method is used to implement
 513   /// VarListElementInit::resolveReferences.  If the list element is resolvable
 514   /// now, we return the resolved value, otherwise we return null.
 515   virtual Init *resolveListElementReference(Record &R, const RecordVal *RV,
 516                                             unsigned Elt) const = 0;
 517 };
 518
 519 /// UnsetInit - ? - Represents an uninitialized value
 520 ///
 521 class UnsetInit : public Init {
 522   UnsetInit() : Init(IK_UnsetInit) {}
 523   UnsetInit(const UnsetInit &) = delete;
 524   UnsetInit &operator=(const UnsetInit &Other) = delete;
 525   void anchor() override;
 526
 527 public:
 528   static bool classof(const Init *I) {
 529     return I->getKind() == IK_UnsetInit;
 530   }
 531   static UnsetInit *get();
 532
 533   Init *convertInitializerTo(RecTy *Ty) const override {
 534     return Ty->convertValue(const_cast<UnsetInit *>(this));
 535   }
 536
 537   Init *getBit(unsigned Bit) const override {
 538     return const_cast<UnsetInit*>(this);
 539   }
 540
 541   bool isComplete() const override { return false; }
 542   std::string getAsString() const override { return "?"; }
 543 };
 544
 545 /// BitInit - true/false - Represent a concrete initializer for a bit.
 546 ///
 547 class BitInit : public Init {
 548   bool Value;
 549
 550   explicit BitInit(bool V) : Init(IK_BitInit), Value(V) {}
 551   BitInit(const BitInit &Other) = delete;
 552   BitInit &operator=(BitInit &Other) = delete;
 553   void anchor() override;
 554
 555 public:
 556   static bool classof(const Init *I) {
 557     return I->getKind() == IK_BitInit;
 558   }
 559   static BitInit *get(bool V);
 560
 561   bool getValue() const { return Value; }
 562
 563   Init *convertInitializerTo(RecTy *Ty) const override {
 564     return Ty->convertValue(const_cast<BitInit *>(this));
 565   }
 566
 567   Init *getBit(unsigned Bit) const override {
 568     assert(Bit < 1 && "Bit index out of range!");
 569     return const_cast<BitInit*>(this);
 570   }
 571
 572   std::string getAsString() const override { return Value ? "1" : "0"; }
 573 };
 574
 575 /// BitsInit - { a, b, c } - Represents an initializer for a BitsRecTy value.
 576 /// It contains a vector of bits, whose size is determined by the type.
 577 ///
 578 class BitsInit : public TypedInit, public FoldingSetNode {
 579   std::vector<Init*> Bits;
 580
 581   BitsInit(ArrayRef<Init *> Range)
 582     : TypedInit(IK_BitsInit, BitsRecTy::get(Range.size())),
 583       Bits(Range.begin(), Range.end()) {}
 584
 585   BitsInit(const BitsInit &Other) = delete;
 586   BitsInit &operator=(const BitsInit &Other) = delete;
 587
 588 public:
 589   static bool classof(const Init *I) {
 590     return I->getKind() == IK_BitsInit;
 591   }
 592   static BitsInit *get(ArrayRef<Init *> Range);
 593
 594   void Profile(FoldingSetNodeID &ID) const;
 595
 596   unsigned getNumBits() const { return Bits.size(); }
 597
 598   Init *convertInitializerTo(RecTy *Ty) const override {
 599     return Ty->convertValue(const_cast<BitsInit *>(this));
 600   }
 601   Init *
 602   convertInitializerBitRange(const std::vector<unsigned> &Bits) const override;
 603
 604   bool isComplete() const override {
 605     for (unsigned i = 0; i != getNumBits(); ++i)
 606       if (!getBit(i)->isComplete()) return false;
 607     return true;
 608   }
 609   bool allInComplete() const {
 610     for (unsigned i = 0; i != getNumBits(); ++i)
 611       if (getBit(i)->isComplete()) return false;
 612     return true;
 613   }
 614   std::string getAsString() const override;
 615
 616   /// resolveListElementReference - This method is used to implement
 617   /// VarListElementInit::resolveReferences.  If the list element is resolvable
 618   /// now, we return the resolved value, otherwise we return null.
 619   Init *resolveListElementReference(Record &R, const RecordVal *RV,
 620                                     unsigned Elt) const override {
 621     llvm_unreachable("Illegal element reference off bits<n>");
 622   }
 623
 624   Init *resolveReferences(Record &R, const RecordVal *RV) const override;
 625
 626   Init *getBit(unsigned Bit) const override {
 627     assert(Bit < Bits.size() && "Bit index out of range!");
 628     return Bits[Bit];
 629   }
 630 };
 631
 632 /// IntInit - 7 - Represent an initialization by a literal integer value.
 633 ///
 634 class IntInit : public TypedInit {
 635   int64_t Value;
 636
 637   explicit IntInit(int64_t V)
 638     : TypedInit(IK_IntInit, IntRecTy::get()), Value(V) {}
 639
 640   IntInit(const IntInit &Other) = delete;
 641   IntInit &operator=(const IntInit &Other) = delete;
 642
 643 public:
 644   static bool classof(const Init *I) {
 645     return I->getKind() == IK_IntInit;
 646   }
 647   static IntInit *get(int64_t V);
 648
 649   int64_t getValue() const { return Value; }
 650
 651   Init *convertInitializerTo(RecTy *Ty) const override {
 652     return Ty->convertValue(const_cast<IntInit *>(this));
 653   }
 654   Init *
 655   convertInitializerBitRange(const std::vector<unsigned> &Bits) const override;
 656
 657   std::string getAsString() const override;
 658
 659   /// resolveListElementReference - This method is used to implement
 660   /// VarListElementInit::resolveReferences.  If the list element is resolvable
 661   /// now, we return the resolved value, otherwise we return null.
 662   Init *resolveListElementReference(Record &R, const RecordVal *RV,
 663                                     unsigned Elt) const override {
 664     llvm_unreachable("Illegal element reference off int");
 665   }
 666
 667   Init *getBit(unsigned Bit) const override {
 668     return BitInit::get((Value & (1ULL << Bit)) != 0);
 669   }
 670 };
 671
 672 /// StringInit - "foo" - Represent an initialization by a string value.
 673 ///
 674 class StringInit : public TypedInit {
 675   std::string Value;
 676
 677   explicit StringInit(const std::string &V)
 678     : TypedInit(IK_StringInit, StringRecTy::get()), Value(V) {}
 679
 680   StringInit(const StringInit &Other) = delete;
 681   StringInit &operator=(const StringInit &Other) = delete;
 682   void anchor() override;
 683
 684 public:
 685   static bool classof(const Init *I) {
 686     return I->getKind() == IK_StringInit;
 687   }
 688   static StringInit *get(StringRef);
 689
 690   const std::string &getValue() const { return Value; }
 691
 692   Init *convertInitializerTo(RecTy *Ty) const override {
 693     return Ty->convertValue(const_cast<StringInit *>(this));
 694   }
 695
 696   std::string getAsString() const override { return "\"" + Value + "\""; }
 697   std::string getAsUnquotedString() const override { return Value; }
 698
 699   /// resolveListElementReference - This method is used to implement
 700   /// VarListElementInit::resolveReferences.  If the list element is resolvable
 701   /// now, we return the resolved value, otherwise we return null.
 702   Init *resolveListElementReference(Record &R, const RecordVal *RV,
 703                                     unsigned Elt) const override {
 704     llvm_unreachable("Illegal element reference off string");
 705   }
 706
 707   Init *getBit(unsigned Bit) const override {
 708     llvm_unreachable("Illegal bit reference off string");
 709   }
 710 };
 711
 712 /// ListInit - [AL, AH, CL] - Represent a list of defs
 713 ///
 714 class ListInit : public TypedInit, public FoldingSetNode {
 715   std::vector<Init*> Values;
 716
 717 public:
 718   typedef std::vector<Init*>::const_iterator const_iterator;
 719
 720 private:
 721   explicit ListInit(ArrayRef<Init *> Range, RecTy *EltTy)
 722     : TypedInit(IK_ListInit, ListRecTy::get(EltTy)),
 723       Values(Range.begin(), Range.end()) {}
 724
 725   ListInit(const ListInit &Other) = delete;
 726   ListInit &operator=(const ListInit &Other) = delete;
 727
 728 public:
 729   static bool classof(const Init *I) {
 730     return I->getKind() == IK_ListInit;
 731   }
 732   static ListInit *get(ArrayRef<Init *> Range, RecTy *EltTy);
 733
 734   void Profile(FoldingSetNodeID &ID) const;
 735
 736   unsigned getSize() const { return Values.size(); }
 737   Init *getElement(unsigned i) const {
 738     assert(i < Values.size() && "List element index out of range!");
 739     return Values[i];
 740   }
 741
 742   Record *getElementAsRecord(unsigned i) const;
 743
 744   Init *
 745     convertInitListSlice(const std::vector<unsigned> &Elements) const override;
 746
 747   Init *convertInitializerTo(RecTy *Ty) const override {
 748     return Ty->convertValue(const_cast<ListInit *>(this));
 749   }
 750
 751   /// resolveReferences - This method is used by classes that refer to other
 752   /// variables which may not be defined at the time they expression is formed.
 753   /// If a value is set for the variable later, this method will be called on
 754   /// users of the value to allow the value to propagate out.
 755   ///
 756   Init *resolveReferences(Record &R, const RecordVal *RV) const override;
 757
 758   std::string getAsString() const override;
 759
 760   ArrayRef<Init*> getValues() const { return Values; }
 761
 762   inline const_iterator begin() const { return Values.begin(); }
 763   inline const_iterator end  () const { return Values.end();   }
 764
 765   inline bool           empty() const { return Values.empty(); }
 766
 767   /// resolveListElementReference - This method is used to implement
 768   /// VarListElementInit::resolveReferences.  If the list element is resolvable
 769   /// now, we return the resolved value, otherwise we return null.
 770   Init *resolveListElementReference(Record &R, const RecordVal *RV,
 771                                     unsigned Elt) const override;
 772
 773   Init *getBit(unsigned Bit) const override {
 774     llvm_unreachable("Illegal bit reference off list");
 775   }
 776 };
 777
 778 /// OpInit - Base class for operators
 779 ///
 780 class OpInit : public TypedInit {
 781   OpInit(const OpInit &Other) = delete;
 782   OpInit &operator=(OpInit &Other) = delete;
 783
 784 protected:
 785   explicit OpInit(InitKind K, RecTy *Type) : TypedInit(K, Type) {}
 786
 787 public:
 788   static bool classof(const Init *I) {
 789     return I->getKind() >= IK_FirstOpInit &&
 790            I->getKind() <= IK_LastOpInit;
 791   }
 792   // Clone - Clone this operator, replacing arguments with the new list
 793   virtual OpInit *clone(std::vector<Init *> &Operands) const = 0;
 794
 795   virtual int getNumOperands() const = 0;
 796   virtual Init *getOperand(int i) const = 0;
 797
 798   // Fold - If possible, fold this to a simpler init.  Return this if not
 799   // possible to fold.
 800   virtual Init *Fold(Record *CurRec, MultiClass *CurMultiClass) const = 0;
 801
 802   Init *convertInitializerTo(RecTy *Ty) const override {
 803     return Ty->convertValue(const_cast<OpInit *>(this));
 804   }
 805
 806   Init *resolveListElementReference(Record &R, const RecordVal *RV,
 807                                     unsigned Elt) const override;
 808
 809   Init *getBit(unsigned Bit) const override;
 810 };
 811
 812 /// UnOpInit - !op (X) - Transform an init.
 813 ///
 814 class UnOpInit : public OpInit {
 815 public:
 816   enum UnaryOp { CAST, HEAD, TAIL, EMPTY };
 817
 818 private:
 819   UnaryOp Opc;
 820   Init *LHS;
 821
 822   UnOpInit(UnaryOp opc, Init *lhs, RecTy *Type)
 823     : OpInit(IK_UnOpInit, Type), Opc(opc), LHS(lhs) {}
 824
 825   UnOpInit(const UnOpInit &Other) = delete;
 826   UnOpInit &operator=(const UnOpInit &Other) = delete;
 827
 828 public:
 829   static bool classof(const Init *I) {
 830     return I->getKind() == IK_UnOpInit;
 831   }
 832   static UnOpInit *get(UnaryOp opc, Init *lhs, RecTy *Type);
 833
 834   // Clone - Clone this operator, replacing arguments with the new list
 835   OpInit *clone(std::vector<Init *> &Operands) const override {
 836     assert(Operands.size() == 1 &&
 837            "Wrong number of operands for unary operation");
 838     return UnOpInit::get(getOpcode(), *Operands.begin(), getType());
 839   }
 840
 841   int getNumOperands() const override { return 1; }
 842   Init *getOperand(int i) const override {
 843     assert(i == 0 && "Invalid operand id for unary operator");
 844     return getOperand();
 845   }
 846
 847   UnaryOp getOpcode() const { return Opc; }
 848   Init *getOperand() const { return LHS; }
 849
 850   // Fold - If possible, fold this to a simpler init.  Return this if not
 851   // possible to fold.
 852   Init *Fold(Record *CurRec, MultiClass *CurMultiClass) const override;
 853
 854   Init *resolveReferences(Record &R, const RecordVal *RV) const override;
 855
 856   std::string getAsString() const override;
 857 };
 858
 859 /// BinOpInit - !op (X, Y) - Combine two inits.
 860 ///
 861 class BinOpInit : public OpInit {
 862 public:
 863   enum BinaryOp { ADD, AND, SHL, SRA, SRL, LISTCONCAT, STRCONCAT, CONCAT, EQ };
 864
 865 private:
 866   BinaryOp Opc;
 867   Init *LHS, *RHS;
 868
 869   BinOpInit(BinaryOp opc, Init *lhs, Init *rhs, RecTy *Type) :
 870       OpInit(IK_BinOpInit, Type), Opc(opc), LHS(lhs), RHS(rhs) {}
 871
 872   BinOpInit(const BinOpInit &Other) = delete;
 873   BinOpInit &operator=(const BinOpInit &Other) = delete;
 874
 875 public:
 876   static bool classof(const Init *I) {
 877     return I->getKind() == IK_BinOpInit;
 878   }
 879   static BinOpInit *get(BinaryOp opc, Init *lhs, Init *rhs,
 880                         RecTy *Type);
 881
 882   // Clone - Clone this operator, replacing arguments with the new list
 883   OpInit *clone(std::vector<Init *> &Operands) const override {
 884     assert(Operands.size() == 2 &&
 885            "Wrong number of operands for binary operation");
 886     return BinOpInit::get(getOpcode(), Operands[0], Operands[1], getType());
 887   }
 888
 889   int getNumOperands() const override { return 2; }
 890   Init *getOperand(int i) const override {
 891     assert((i == 0 || i == 1) && "Invalid operand id for binary operator");
 892     if (i == 0) {
 893       return getLHS();
 894     } else {
 895       return getRHS();
 896     }
 897   }
 898
 899   BinaryOp getOpcode() const { return Opc; }
 900   Init *getLHS() const { return LHS; }
 901   Init *getRHS() const { return RHS; }
 902
 903   // Fold - If possible, fold this to a simpler init.  Return this if not
 904   // possible to fold.
 905   Init *Fold(Record *CurRec, MultiClass *CurMultiClass) const override;
 906
 907   Init *resolveReferences(Record &R, const RecordVal *RV) const override;
 908
 909   std::string getAsString() const override;
 910 };
 911
 912 /// TernOpInit - !op (X, Y, Z) - Combine two inits.
 913 ///
 914 class TernOpInit : public OpInit {
 915 public:
 916   enum TernaryOp { SUBST, FOREACH, IF };
 917
 918 private:
 919   TernaryOp Opc;
 920   Init *LHS, *MHS, *RHS;
 921
 922   TernOpInit(TernaryOp opc, Init *lhs, Init *mhs, Init *rhs,
 923              RecTy *Type) :
 924       OpInit(IK_TernOpInit, Type), Opc(opc), LHS(lhs), MHS(mhs), RHS(rhs) {}
 925
 926   TernOpInit(const TernOpInit &Other) = delete;
 927   TernOpInit &operator=(const TernOpInit &Other) = delete;
 928
 929 public:
 930   static bool classof(const Init *I) {
 931     return I->getKind() == IK_TernOpInit;
 932   }
 933   static TernOpInit *get(TernaryOp opc, Init *lhs,
 934                          Init *mhs, Init *rhs,
 935                          RecTy *Type);
 936
 937   // Clone - Clone this operator, replacing arguments with the new list
 938   OpInit *clone(std::vector<Init *> &Operands) const override {
 939     assert(Operands.size() == 3 &&
 940            "Wrong number of operands for ternary operation");
 941     return TernOpInit::get(getOpcode(), Operands[0], Operands[1], Operands[2],
 942                            getType());
 943   }
 944
 945   int getNumOperands() const override { return 3; }
 946   Init *getOperand(int i) const override {
 947     assert((i == 0 || i == 1 || i == 2) &&
 948            "Invalid operand id for ternary operator");
 949     if (i == 0) {
 950       return getLHS();
 951     } else if (i == 1) {
 952       return getMHS();
 953     } else {
 954       return getRHS();
 955     }
 956   }
 957
 958   TernaryOp getOpcode() const { return Opc; }
 959   Init *getLHS() const { return LHS; }
 960   Init *getMHS() const { return MHS; }
 961   Init *getRHS() const { return RHS; }
 962
 963   // Fold - If possible, fold this to a simpler init.  Return this if not
 964   // possible to fold.
 965   Init *Fold(Record *CurRec, MultiClass *CurMultiClass) const override;
 966
 967   bool isComplete() const override { return false; }
 968
 969   Init *resolveReferences(Record &R, const RecordVal *RV) const override;
 970
 971   std::string getAsString() const override;
 972 };
 973
 974 /// VarInit - 'Opcode' - Represent a reference to an entire variable object.
 975 ///
 976 class VarInit : public TypedInit {
 977   Init *VarName;
 978
 979   explicit VarInit(const std::string &VN, RecTy *T)
 980       : TypedInit(IK_VarInit, T), VarName(StringInit::get(VN)) {}
 981   explicit VarInit(Init *VN, RecTy *T)
 982       : TypedInit(IK_VarInit, T), VarName(VN) {}
 983
 984   VarInit(const VarInit &Other) = delete;
 985   VarInit &operator=(const VarInit &Other) = delete;
 986
 987 public:
 988   static bool classof(const Init *I) {
 989     return I->getKind() == IK_VarInit;
 990   }
 991   static VarInit *get(const std::string &VN, RecTy *T);
 992   static VarInit *get(Init *VN, RecTy *T);
 993
 994   Init *convertInitializerTo(RecTy *Ty) const override {
 995     return Ty->convertValue(const_cast<VarInit *>(this));
 996   }
 997
 998   const std::string &getName() const;
 999   Init *getNameInit() const { return VarName; }
1000   std::string getNameInitAsString() const {
1001     return getNameInit()->getAsUnquotedString();
1002   }
1003
1004   Init *resolveListElementReference(Record &R, const RecordVal *RV,
1005                                     unsigned Elt) const override;
1006
1007   RecTy *getFieldType(const std::string &FieldName) const override;
1008   Init *getFieldInit(Record &R, const RecordVal *RV,
1009                      const std::string &FieldName) const override;
1010
1011   /// resolveReferences - This method is used by classes that refer to other
1012   /// variables which may not be defined at the time they expression is formed.
1013   /// If a value is set for the variable later, this method will be called on
1014   /// users of the value to allow the value to propagate out.
1015   ///
1016   Init *resolveReferences(Record &R, const RecordVal *RV) const override;
1017
1018   Init *getBit(unsigned Bit) const override;
1019
1020   std::string getAsString() const override { return getName(); }
1021 };
1022
1023 /// VarBitInit - Opcode{0} - Represent access to one bit of a variable or field.
1024 ///
1025 class VarBitInit : public Init {
1026   TypedInit *TI;
1027   unsigned Bit;
1028
1029   VarBitInit(TypedInit *T, unsigned B) : Init(IK_VarBitInit), TI(T), Bit(B) {
1030     assert(T->getType() &&
1031            (isa<IntRecTy>(T->getType()) ||
1032             (isa<BitsRecTy>(T->getType()) &&
1033              cast<BitsRecTy>(T->getType())->getNumBits() > B)) &&
1034            "Illegal VarBitInit expression!");
1035   }
1036
1037   VarBitInit(const VarBitInit &Other) = delete;
1038   VarBitInit &operator=(const VarBitInit &Other) = delete;
1039
1040 public:
1041   static bool classof(const Init *I) {
1042     return I->getKind() == IK_VarBitInit;
1043   }
1044   static VarBitInit *get(TypedInit *T, unsigned B);
1045
1046   Init *convertInitializerTo(RecTy *Ty) const override {
1047     return Ty->convertValue(const_cast<VarBitInit *>(this));
1048   }
1049
1050   Init *getBitVar() const override { return TI; }
1051   unsigned getBitNum() const override { return Bit; }
1052
1053   std::string getAsString() const override;
1054   Init *resolveReferences(Record &R, const RecordVal *RV) const override;
1055
1056   Init *getBit(unsigned B) const override {
1057     assert(B < 1 && "Bit index out of range!");
1058     return const_cast<VarBitInit*>(this);
1059   }
1060 };
1061
1062 /// VarListElementInit - List[4] - Represent access to one element of a var or
1063 /// field.
1064 class VarListElementInit : public TypedInit {
1065   TypedInit *TI;
1066   unsigned Element;
1067
1068   VarListElementInit(TypedInit *T, unsigned E)
1069       : TypedInit(IK_VarListElementInit,
1070                   cast<ListRecTy>(T->getType())->getElementType()),
1071         TI(T), Element(E) {
1072     assert(T->getType() && isa<ListRecTy>(T->getType()) &&
1073            "Illegal VarBitInit expression!");
1074   }
1075
1076   VarListElementInit(const VarListElementInit &Other) = delete;
1077   void operator=(const VarListElementInit &Other) = delete;
1078
1079 public:
1080   static bool classof(const Init *I) {
1081     return I->getKind() == IK_VarListElementInit;
1082   }
1083   static VarListElementInit *get(TypedInit *T, unsigned E);
1084
1085   Init *convertInitializerTo(RecTy *Ty) const override {
1086     return Ty->convertValue(const_cast<VarListElementInit *>(this));
1087   }
1088
1089   TypedInit *getVariable() const { return TI; }
1090   unsigned getElementNum() const { return Element; }
1091
1092   /// resolveListElementReference - This method is used to implement
1093   /// VarListElementInit::resolveReferences.  If the list element is resolvable
1094   /// now, we return the resolved value, otherwise we return null.
1095   Init *resolveListElementReference(Record &R, const RecordVal *RV,
1096                                     unsigned Elt) const override;
1097
1098   std::string getAsString() const override;
1099   Init *resolveReferences(Record &R, const RecordVal *RV) const override;
1100
1101   Init *getBit(unsigned Bit) const override;
1102 };
1103
1104 /// DefInit - AL - Represent a reference to a 'def' in the description
1105 ///
1106 class DefInit : public TypedInit {
1107   Record *Def;
1108
1109   DefInit(Record *D, RecordRecTy *T) : TypedInit(IK_DefInit, T), Def(D) {}
1110   friend class Record;
1111
1112   DefInit(const DefInit &Other) = delete;
1113   DefInit &operator=(const DefInit &Other) = delete;
1114
1115 public:
1116   static bool classof(const Init *I) {
1117     return I->getKind() == IK_DefInit;
1118   }
1119   static DefInit *get(Record*);
1120
1121   Init *convertInitializerTo(RecTy *Ty) const override {
1122     return Ty->convertValue(const_cast<DefInit *>(this));
1123   }
1124
1125   Record *getDef() const { return Def; }
1126
1127   //virtual Init *convertInitializerBitRange(const std::vector<unsigned> &Bits);
1128
1129   RecTy *getFieldType(const std::string &FieldName) const override;
1130   Init *getFieldInit(Record &R, const RecordVal *RV,
1131                      const std::string &FieldName) const override;
1132
1133   std::string getAsString() const override;
1134
1135   Init *getBit(unsigned Bit) const override {
1136     llvm_unreachable("Illegal bit reference off def");
1137   }
1138
1139   /// resolveListElementReference - This method is used to implement
1140   /// VarListElementInit::resolveReferences.  If the list element is resolvable
1141   /// now, we return the resolved value, otherwise we return null.
1142   Init *resolveListElementReference(Record &R, const RecordVal *RV,
1143                                     unsigned Elt) const override {
1144     llvm_unreachable("Illegal element reference off def");
1145   }
1146 };
1147
1148 /// FieldInit - X.Y - Represent a reference to a subfield of a variable
1149 ///
1150 class FieldInit : public TypedInit {
1151   Init *Rec;                // Record we are referring to
1152   std::string FieldName;    // Field we are accessing
1153
1154   FieldInit(Init *R, const std::string &FN)
1155       : TypedInit(IK_FieldInit, R->getFieldType(FN)), Rec(R), FieldName(FN) {
1156     assert(getType() && "FieldInit with non-record type!");
1157   }
1158
1159   FieldInit(const FieldInit &Other) = delete;
1160   FieldInit &operator=(const FieldInit &Other) = delete;
1161
1162 public:
1163   static bool classof(const Init *I) {
1164     return I->getKind() == IK_FieldInit;
1165   }
1166   static FieldInit *get(Init *R, const std::string &FN);
1167   static FieldInit *get(Init *R, const Init *FN);
1168
1169   Init *convertInitializerTo(RecTy *Ty) const override {
1170     return Ty->convertValue(const_cast<FieldInit *>(this));
1171   }
1172
1173   Init *getBit(unsigned Bit) const override;
1174
1175   Init *resolveListElementReference(Record &R, const RecordVal *RV,
1176                                     unsigned Elt) const override;
1177
1178   Init *resolveReferences(Record &R, const RecordVal *RV) const override;
1179
1180   std::string getAsString() const override {
1181     return Rec->getAsString() + "." + FieldName;
1182   }
1183 };
1184
1185 /// DagInit - (v a, b) - Represent a DAG tree value.  DAG inits are required
1186 /// to have at least one value then a (possibly empty) list of arguments.  Each
1187 /// argument can have a name associated with it.
1188 ///
1189 class DagInit : public TypedInit, public FoldingSetNode {
1190   Init *Val;
1191   std::string ValName;
1192   std::vector<Init*> Args;
1193   std::vector<std::string> ArgNames;
1194
1195   DagInit(Init *V, const std::string &VN,
1196           ArrayRef<Init *> ArgRange,
1197           ArrayRef<std::string> NameRange)
1198       : TypedInit(IK_DagInit, DagRecTy::get()), Val(V), ValName(VN),
1199           Args(ArgRange.begin(), ArgRange.end()),
1200           ArgNames(NameRange.begin(), NameRange.end()) {}
1201
1202   DagInit(const DagInit &Other) = delete;
1203   DagInit &operator=(const DagInit &Other) = delete;
1204
1205 public:
1206   static bool classof(const Init *I) {
1207     return I->getKind() == IK_DagInit;
1208   }
1209   static DagInit *get(Init *V, const std::string &VN,
1210                       ArrayRef<Init *> ArgRange,
1211                       ArrayRef<std::string> NameRange);
1212   static DagInit *get(Init *V, const std::string &VN,
1213                       const std::vector<
1214                         std::pair<Init*, std::string> > &args);
1215
1216   void Profile(FoldingSetNodeID &ID) const;
1217
1218   Init *convertInitializerTo(RecTy *Ty) const override {
1219     return Ty->convertValue(const_cast<DagInit *>(this));
1220   }
1221
1222   Init *getOperator() const { return Val; }
1223
1224   const std::string &getName() const { return ValName; }
1225
1226   unsigned getNumArgs() const { return Args.size(); }
1227   Init *getArg(unsigned Num) const {
1228     assert(Num < Args.size() && "Arg number out of range!");
1229     return Args[Num];
1230   }
1231   const std::string &getArgName(unsigned Num) const {
1232     assert(Num < ArgNames.size() && "Arg number out of range!");
1233     return ArgNames[Num];
1234   }
1235
1236   Init *resolveReferences(Record &R, const RecordVal *RV) const override;
1237
1238   std::string getAsString() const override;
1239
1240   typedef std::vector<Init*>::const_iterator       const_arg_iterator;
1241   typedef std::vector<std::string>::const_iterator const_name_iterator;
1242
1243   inline const_arg_iterator  arg_begin() const { return Args.begin(); }
1244   inline const_arg_iterator  arg_end  () const { return Args.end();   }
1245
1246   inline size_t              arg_size () const { return Args.size();  }
1247   inline bool                arg_empty() const { return Args.empty(); }
1248
1249   inline const_name_iterator name_begin() const { return ArgNames.begin(); }
1250   inline const_name_iterator name_end  () const { return ArgNames.end();   }
1251
1252   inline size_t              name_size () const { return ArgNames.size();  }
1253   inline bool                name_empty() const { return ArgNames.empty(); }
1254
1255   Init *getBit(unsigned Bit) const override {
1256     llvm_unreachable("Illegal bit reference off dag");
1257   }
1258
1259   Init *resolveListElementReference(Record &R, const RecordVal *RV,
1260                                     unsigned Elt) const override {
1261     llvm_unreachable("Illegal element reference off dag");
1262   }
1263 };
1264
1265 //===----------------------------------------------------------------------===//
1266 //  High-Level Classes
1267 //===----------------------------------------------------------------------===//
1268
1269 class RecordVal {
1270   Init *Name;
1271   RecTy *Ty;
1272   unsigned Prefix;
1273   Init *Value;
1274
1275 public:
1276   RecordVal(Init *N, RecTy *T, unsigned P);
1277   RecordVal(const std::string &N, RecTy *T, unsigned P);
1278
1279   const std::string &getName() const;
1280   const Init *getNameInit() const { return Name; }
1281   std::string getNameInitAsString() const {
1282     return getNameInit()->getAsUnquotedString();
1283   }
1284
1285   unsigned getPrefix() const { return Prefix; }
1286   RecTy *getType() const { return Ty; }
1287   Init *getValue() const { return Value; }
1288
1289   bool setValue(Init *V) {
1290     if (V) {
1291       Value = V->convertInitializerTo(Ty);
1292       return Value == nullptr;
1293     }
1294     Value = nullptr;
1295     return false;
1296   }
1297
1298   void dump() const;
1299   void print(raw_ostream &OS, bool PrintSem = true) const;
1300 };
1301
1302 inline raw_ostream &operator<<(raw_ostream &OS, const RecordVal &RV) {
1303   RV.print(OS << "  ");
1304   return OS;
1305 }
1306
1307 class Record {
1308   static unsigned LastID;
1309
1310   // Unique record ID.
1311   unsigned ID;
1312   Init *Name;
1313   // Location where record was instantiated, followed by the location of
1314   // multiclass prototypes used.
1315   SmallVector<SMLoc, 4> Locs;
1316   std::vector<Init *> TemplateArgs;
1317   std::vector<RecordVal> Values;
1318   std::vector<Record *> SuperClasses;
1319   std::vector<SMRange> SuperClassRanges;
1320
1321   // Tracks Record instances. Not owned by Record.
1322   RecordKeeper &TrackedRecords;
1323
1324   DefInit *TheInit;
1325   bool IsAnonymous;
1326
1327   // Class-instance values can be used by other defs.  For example, Struct<i>
1328   // is used here as a template argument to another class:
1329   //
1330   //   multiclass MultiClass<int i> {
1331   //     def Def : Class<Struct<i>>;
1332   //
1333   // These need to get fully resolved before instantiating any other
1334   // definitions that usie them (e.g. Def).  However, inside a multiclass they
1335   // can't be immediately resolved so we mark them ResolveFirst to fully
1336   // resolve them later as soon as the multiclass is instantiated.
1337   bool ResolveFirst;
1338
1339   void init();
1340   void checkName();
1341
1342 public:
1343   // Constructs a record.
1344   explicit Record(const std::string &N, ArrayRef<SMLoc> locs,
1345                   RecordKeeper &records, bool Anonymous = false) :
1346     ID(LastID++), Name(StringInit::get(N)), Locs(locs.begin(), locs.end()),
1347     TrackedRecords(records), TheInit(nullptr), IsAnonymous(Anonymous),
1348     ResolveFirst(false) {
1349     init();
1350   }
1351   explicit Record(Init *N, ArrayRef<SMLoc> locs, RecordKeeper &records,
1352                   bool Anonymous = false) :
1353     ID(LastID++), Name(N), Locs(locs.begin(), locs.end()),
1354     TrackedRecords(records), TheInit(nullptr), IsAnonymous(Anonymous),
1355     ResolveFirst(false) {
1356     init();
1357   }
1358
1359   // When copy-constructing a Record, we must still guarantee a globally unique
1360   // ID number.  All other fields can be copied normally.
1361   Record(const Record &O) :
1362     ID(LastID++), Name(O.Name), Locs(O.Locs), TemplateArgs(O.TemplateArgs),
1363     Values(O.Values), SuperClasses(O.SuperClasses),
1364     SuperClassRanges(O.SuperClassRanges), TrackedRecords(O.TrackedRecords),
1365     TheInit(O.TheInit), IsAnonymous(O.IsAnonymous),
1366     ResolveFirst(O.ResolveFirst) { }
1367
1368   static unsigned getNewUID() { return LastID++; }
1369
1370   unsigned getID() const { return ID; }
1371
1372   const std::string &getName() const;
1373   Init *getNameInit() const {
1374     return Name;
1375   }
1376   const std::string getNameInitAsString() const {
1377     return getNameInit()->getAsUnquotedString();
1378   }
1379
1380   void setName(Init *Name);               // Also updates RecordKeeper.
1381   void setName(const std::string &Name);  // Also updates RecordKeeper.
1382
1383   ArrayRef<SMLoc> getLoc() const { return Locs; }
1384
1385   /// get the corresponding DefInit.
1386   DefInit *getDefInit();
1387
1388   const std::vector<Init *> &getTemplateArgs() const {
1389     return TemplateArgs;
1390   }
1391   const std::vector<RecordVal> &getValues() const { return Values; }
1392   const std::vector<Record*>   &getSuperClasses() const { return SuperClasses; }
1393   ArrayRef<SMRange> getSuperClassRanges() const { return SuperClassRanges; }
1394
1395   bool isTemplateArg(Init *Name) const {
1396     for (unsigned i = 0, e = TemplateArgs.size(); i != e; ++i)
1397       if (TemplateArgs[i] == Name) return true;
1398     return false;
1399   }
1400   bool isTemplateArg(StringRef Name) const {
1401     return isTemplateArg(StringInit::get(Name));
1402   }
1403
1404   const RecordVal *getValue(const Init *Name) const {
1405     for (unsigned i = 0, e = Values.size(); i != e; ++i)
1406       if (Values[i].getNameInit() == Name) return &Values[i];
1407     return nullptr;
1408   }
1409   const RecordVal *getValue(StringRef Name) const {
1410     return getValue(StringInit::get(Name));
1411   }
1412   RecordVal *getValue(const Init *Name) {
1413     for (unsigned i = 0, e = Values.size(); i != e; ++i)
1414       if (Values[i].getNameInit() == Name) return &Values[i];
1415     return nullptr;
1416   }
1417   RecordVal *getValue(StringRef Name) {
1418     return getValue(StringInit::get(Name));
1419   }
1420
1421   void addTemplateArg(Init *Name) {
1422     assert(!isTemplateArg(Name) && "Template arg already defined!");
1423     TemplateArgs.push_back(Name);
1424   }
1425   void addTemplateArg(StringRef Name) {
1426     addTemplateArg(StringInit::get(Name));
1427   }
1428
1429   void addValue(const RecordVal &RV) {
1430     assert(getValue(RV.getNameInit()) == nullptr && "Value already added!");
1431     Values.push_back(RV);
1432     if (Values.size() > 1)
1433       // Keep NAME at the end of the list.  It makes record dumps a
1434       // bit prettier and allows TableGen tests to be written more
1435       // naturally.  Tests can use CHECK-NEXT to look for Record
1436       // fields they expect to see after a def.  They can't do that if
1437       // NAME is the first Record field.
1438       std::swap(Values[Values.size() - 2], Values[Values.size() - 1]);
1439   }
1440
1441   void removeValue(Init *Name) {
1442     for (unsigned i = 0, e = Values.size(); i != e; ++i)
1443       if (Values[i].getNameInit() == Name) {
1444         Values.erase(Values.begin()+i);
1445         return;
1446       }
1447     llvm_unreachable("Cannot remove an entry that does not exist!");
1448   }
1449
1450   void removeValue(StringRef Name) {
1451     removeValue(StringInit::get(Name));
1452   }
1453
1454   bool isSubClassOf(const Record *R) const {
1455     for (unsigned i = 0, e = SuperClasses.size(); i != e; ++i)
1456       if (SuperClasses[i] == R)
1457         return true;
1458     return false;
1459   }
1460
1461   bool isSubClassOf(StringRef Name) const {
1462     for (unsigned i = 0, e = SuperClasses.size(); i != e; ++i)
1463       if (SuperClasses[i]->getNameInitAsString() == Name)
1464         return true;
1465     return false;
1466   }
1467
1468   void addSuperClass(Record *R, SMRange Range) {
1469     assert(!isSubClassOf(R) && "Already subclassing record!");
1470     SuperClasses.push_back(R);
1471     SuperClassRanges.push_back(Range);
1472   }
1473
1474   /// resolveReferences - If there are any field references that refer to fields
1475   /// that have been filled in, we can propagate the values now.
1476   ///
1477   void resolveReferences() { resolveReferencesTo(nullptr); }
1478
1479   /// resolveReferencesTo - If anything in this record refers to RV, replace the
1480   /// reference to RV with the RHS of RV.  If RV is null, we resolve all
1481   /// possible references.
1482   void resolveReferencesTo(const RecordVal *RV);
1483
1484   RecordKeeper &getRecords() const {
1485     return TrackedRecords;
1486   }
1487
1488   bool isAnonymous() const {
1489     return IsAnonymous;
1490   }
1491
1492   bool isResolveFirst() const {
1493     return ResolveFirst;
1494   }
1495
1496   void setResolveFirst(bool b) {
1497     ResolveFirst = b;
1498   }
1499
1500   void dump() const;
1501
1502   //===--------------------------------------------------------------------===//
1503   // High-level methods useful to tablegen back-ends
1504   //
1505
1506   /// getValueInit - Return the initializer for a value with the specified name,
1507   /// or throw an exception if the field does not exist.
1508   ///
1509   Init *getValueInit(StringRef FieldName) const;
1510
1511   /// Return true if the named field is unset.
1512   bool isValueUnset(StringRef FieldName) const {
1513     return getValueInit(FieldName) == UnsetInit::get();
1514   }
1515
1516   /// getValueAsString - This method looks up the specified field and returns
1517   /// its value as a string, throwing an exception if the field does not exist
1518   /// or if the value is not a string.
1519   ///
1520   std::string getValueAsString(StringRef FieldName) const;
1521
1522   /// getValueAsBitsInit - This method looks up the specified field and returns
1523   /// its value as a BitsInit, throwing an exception if the field does not exist
1524   /// or if the value is not the right type.
1525   ///
1526   BitsInit *getValueAsBitsInit(StringRef FieldName) const;
1527
1528   /// getValueAsListInit - This method looks up the specified field and returns
1529   /// its value as a ListInit, throwing an exception if the field does not exist
1530   /// or if the value is not the right type.
1531   ///
1532   ListInit *getValueAsListInit(StringRef FieldName) const;
1533
1534   /// getValueAsListOfDefs - This method looks up the specified field and
1535   /// returns its value as a vector of records, throwing an exception if the
1536   /// field does not exist or if the value is not the right type.
1537   ///
1538   std::vector<Record*> getValueAsListOfDefs(StringRef FieldName) const;
1539
1540   /// getValueAsListOfInts - This method looks up the specified field and
1541   /// returns its value as a vector of integers, throwing an exception if the
1542   /// field does not exist or if the value is not the right type.
1543   ///
1544   std::vector<int64_t> getValueAsListOfInts(StringRef FieldName) const;
1545
1546   /// getValueAsListOfStrings - This method looks up the specified field and
1547   /// returns its value as a vector of strings, throwing an exception if the
1548   /// field does not exist or if the value is not the right type.
1549   ///
1550   std::vector<std::string> getValueAsListOfStrings(StringRef FieldName) const;
1551
1552   /// getValueAsDef - This method looks up the specified field and returns its
1553   /// value as a Record, throwing an exception if the field does not exist or if
1554   /// the value is not the right type.
1555   ///
1556   Record *getValueAsDef(StringRef FieldName) const;
1557
1558   /// getValueAsBit - This method looks up the specified field and returns its
1559   /// value as a bit, throwing an exception if the field does not exist or if
1560   /// the value is not the right type.
1561   ///
1562   bool getValueAsBit(StringRef FieldName) const;
1563
1564   /// getValueAsBitOrUnset - This method looks up the specified field and
1565   /// returns its value as a bit. If the field is unset, sets Unset to true and
1566   /// returns false.
1567   ///
1568   bool getValueAsBitOrUnset(StringRef FieldName, bool &Unset) const;
1569
1570   /// getValueAsInt - This method looks up the specified field and returns its
1571   /// value as an int64_t, throwing an exception if the field does not exist or
1572   /// if the value is not the right type.
1573   ///
1574   int64_t getValueAsInt(StringRef FieldName) const;
1575
1576   /// getValueAsDag - This method looks up the specified field and returns its
1577   /// value as an Dag, throwing an exception if the field does not exist or if
1578   /// the value is not the right type.
1579   ///
1580   DagInit *getValueAsDag(StringRef FieldName) const;
1581 };
1582
1583 raw_ostream &operator<<(raw_ostream &OS, const Record &R);
1584
1585 struct MultiClass {
1586   Record Rec;  // Placeholder for template args and Name.
1587   typedef std::vector<std::unique_ptr<Record>> RecordVector;
1588   RecordVector DefPrototypes;
1589
1590   void dump() const;
1591
1592   MultiClass(const std::string &Name, SMLoc Loc, RecordKeeper &Records) :
1593     Rec(Name, Loc, Records) {}
1594 };
1595
1596 class RecordKeeper {
1597   typedef std::map<std::string, std::unique_ptr<Record>> RecordMap;
1598   RecordMap Classes, Defs;
1599
1600 public:
1601   const RecordMap &getClasses() const { return Classes; }
1602   const RecordMap &getDefs() const { return Defs; }
1603
1604   Record *getClass(const std::string &Name) const {
1605     auto I = Classes.find(Name);
1606     return I == Classes.end() ? nullptr : I->second.get();
1607   }
1608   Record *getDef(const std::string &Name) const {
1609     auto I = Defs.find(Name);
1610     return I == Defs.end() ? nullptr : I->second.get();
1611   }
1612   void addClass(std::unique_ptr<Record> R) {
1613     bool Ins = Classes.insert(std::make_pair(R->getName(),
1614                                              std::move(R))).second;
1615     (void)Ins;
1616     assert(Ins && "Class already exists");
1617   }
1618   void addDef(std::unique_ptr<Record> R) {
1619     bool Ins = Defs.insert(std::make_pair(R->getName(),
1620                                           std::move(R))).second;
1621     (void)Ins;
1622     assert(Ins && "Record already exists");
1623   }
1624
1625   //===--------------------------------------------------------------------===//
1626   // High-level helper methods, useful for tablegen backends...
1627
1628   /// getAllDerivedDefinitions - This method returns all concrete definitions
1629   /// that derive from the specified class name.  If a class with the specified
1630   /// name does not exist, an exception is thrown.
1631   std::vector<Record*>
1632   getAllDerivedDefinitions(const std::string &ClassName) const;
1633
1634   void dump() const;
1635 };
1636
1637 /// LessRecord - Sorting predicate to sort record pointers by name.
1638 ///
1639 struct LessRecord {
1640   bool operator()(const Record *Rec1, const Record *Rec2) const {
1641     return StringRef(Rec1->getName()).compare_numeric(Rec2->getName()) < 0;
1642   }
1643 };
1644
1645 /// LessRecordByID - Sorting predicate to sort record pointers by their
1646 /// unique ID. If you just need a deterministic order, use this, since it
1647 /// just compares two `unsigned`; the other sorting predicates require
1648 /// string manipulation.
1649 struct LessRecordByID {
1650   bool operator()(const Record *LHS, const Record *RHS) const {
1651     return LHS->getID() < RHS->getID();
1652   }
1653 };
1654
1655 /// LessRecordFieldName - Sorting predicate to sort record pointers by their
1656 /// name field.
1657 ///
1658 struct LessRecordFieldName {
1659   bool operator()(const Record *Rec1, const Record *Rec2) const {
1660     return Rec1->getValueAsString("Name") < Rec2->getValueAsString("Name");
1661   }
1662 };
1663
1664 struct LessRecordRegister {
1665   static size_t min(size_t a, size_t b) { return a < b ? a : b; }
1666   static bool ascii_isdigit(char x) { return x >= '0' && x <= '9'; }
1667
1668   struct RecordParts {
1669     SmallVector<std::pair< bool, StringRef>, 4> Parts;
1670
1671     RecordParts(StringRef Rec) {
1672       if (Rec.empty())
1673         return;
1674
1675       size_t Len = 0;
1676       const char *Start = Rec.data();
1677       const char *Curr = Start;
1678       bool isDigitPart = ascii_isdigit(Curr[0]);
1679       for (size_t I = 0, E = Rec.size(); I != E; ++I, ++Len) {
1680         bool isDigit = ascii_isdigit(Curr[I]);
1681         if (isDigit != isDigitPart) {
1682           Parts.push_back(std::make_pair(isDigitPart, StringRef(Start, Len)));
1683           Len = 0;
1684           Start = &Curr[I];
1685           isDigitPart = ascii_isdigit(Curr[I]);
1686         }
1687       }
1688       // Push the last part.
1689       Parts.push_back(std::make_pair(isDigitPart, StringRef(Start, Len)));
1690     }
1691
1692     size_t size() { return Parts.size(); }
1693
1694     std::pair<bool, StringRef> getPart(size_t i) {
1695       assert (i < Parts.size() && "Invalid idx!");
1696       return Parts[i];
1697     }
1698   };
1699
1700   bool operator()(const Record *Rec1, const Record *Rec2) const {
1701     RecordParts LHSParts(StringRef(Rec1->getName()));
1702     RecordParts RHSParts(StringRef(Rec2->getName()));
1703
1704     size_t LHSNumParts = LHSParts.size();
1705     size_t RHSNumParts = RHSParts.size();
1706     assert (LHSNumParts && RHSNumParts && "Expected at least one part!");
1707
1708     if (LHSNumParts != RHSNumParts)
1709       return LHSNumParts < RHSNumParts;
1710
1711     // We expect the registers to be of the form [_a-zA-z]+([0-9]*[_a-zA-Z]*)*.
1712     for (size_t I = 0, E = LHSNumParts; I < E; I+=2) {
1713       std::pair<bool, StringRef> LHSPart = LHSParts.getPart(I);
1714       std::pair<bool, StringRef> RHSPart = RHSParts.getPart(I);
1715       // Expect even part to always be alpha.
1716       assert (LHSPart.first == false && RHSPart.first == false &&
1717               "Expected both parts to be alpha.");
1718       if (int Res = LHSPart.second.compare(RHSPart.second))
1719         return Res < 0;
1720     }
1721     for (size_t I = 1, E = LHSNumParts; I < E; I+=2) {
1722       std::pair<bool, StringRef> LHSPart = LHSParts.getPart(I);
1723       std::pair<bool, StringRef> RHSPart = RHSParts.getPart(I);
1724       // Expect odd part to always be numeric.
1725       assert (LHSPart.first == true && RHSPart.first == true &&
1726               "Expected both parts to be numeric.");
1727       if (LHSPart.second.size() != RHSPart.second.size())
1728         return LHSPart.second.size() < RHSPart.second.size();
1729
1730       unsigned LHSVal, RHSVal;
1731
1732       bool LHSFailed = LHSPart.second.getAsInteger(10, LHSVal); (void)LHSFailed;
1733       assert(!LHSFailed && "Unable to convert LHS to integer.");
1734       bool RHSFailed = RHSPart.second.getAsInteger(10, RHSVal); (void)RHSFailed;
1735       assert(!RHSFailed && "Unable to convert RHS to integer.");
1736
1737       if (LHSVal != RHSVal)
1738         return LHSVal < RHSVal;
1739     }
1740     return LHSNumParts < RHSNumParts;
1741   }
1742 };
1743
1744 raw_ostream &operator<<(raw_ostream &OS, const RecordKeeper &RK);
1745
1746 /// QualifyName - Return an Init with a qualifier prefix referring
1747 /// to CurRec's name.
1748 Init *QualifyName(Record &CurRec, MultiClass *CurMultiClass,
1749                   Init *Name, const std::string &Scoper);
1750
1751 /// QualifyName - Return an Init with a qualifier prefix referring
1752 /// to CurRec's name.
1753 Init *QualifyName(Record &CurRec, MultiClass *CurMultiClass,
1754                   const std::string &Name, const std::string &Scoper);
1755
1756 } // End llvm namespace
1757
1758 #endif