llvm/lib/TableGen/Record.cpp

   1 //===- Record.cpp - Record implementation ---------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Implement the tablegen record classes.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/TableGen/Record.h"
  14 #include "llvm/ADT/ArrayRef.h"
  15 #include "llvm/ADT/DenseMap.h"
  16 #include "llvm/ADT/FoldingSet.h"
  17 #include "llvm/ADT/SmallString.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/ADT/StringExtras.h"
  20 #include "llvm/ADT/StringMap.h"
  21 #include "llvm/ADT/StringRef.h"
  22 #include "llvm/Config/llvm-config.h"
  23 #include "llvm/Support/Allocator.h"
  24 #include "llvm/Support/Casting.h"
  25 #include "llvm/Support/Compiler.h"
  26 #include "llvm/Support/ErrorHandling.h"
  27 #include "llvm/Support/MathExtras.h"
  28 #include "llvm/Support/SMLoc.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 #include "llvm/TableGen/Error.h"
  31 #include "llvm/TableGen/TGTimer.h"
  32 #include <cassert>
  33 #include <cstdint>
  34 #include <map>
  35 #include <memory>
  36 #include <string>
  37 #include <utility>
  38 #include <vector>
  39
  40 using namespace llvm;
  41
  42 #define DEBUG_TYPE "tblgen-records"
  43
  44 //===----------------------------------------------------------------------===//
  45 //    Context
  46 //===----------------------------------------------------------------------===//
  47
  48 namespace llvm {
  49 namespace detail {
  50 /// This class represents the internal implementation of the RecordKeeper.
  51 /// It contains all of the contextual static state of the Record classes. It is
  52 /// kept out-of-line to simplify dependencies, and also make it easier for
  53 /// internal classes to access the uniquer state of the keeper.
  54 struct RecordKeeperImpl {
  55   RecordKeeperImpl(RecordKeeper &RK)
  56       : SharedBitRecTy(RK), SharedIntRecTy(RK), SharedStringRecTy(RK),
  57         SharedDagRecTy(RK), AnyRecord(RK, 0), TheUnsetInit(RK),
  58         TrueBitInit(true, &SharedBitRecTy),
  59         FalseBitInit(false, &SharedBitRecTy), StringInitStringPool(Allocator),
  60         StringInitCodePool(Allocator), AnonCounter(0), LastRecordID(0) {}
  61
  62   BumpPtrAllocator Allocator;
  63   std::vector<BitsRecTy *> SharedBitsRecTys;
  64   BitRecTy SharedBitRecTy;
  65   IntRecTy SharedIntRecTy;
  66   StringRecTy SharedStringRecTy;
  67   DagRecTy SharedDagRecTy;
  68
  69   RecordRecTy AnyRecord;
  70   UnsetInit TheUnsetInit;
  71   BitInit TrueBitInit;
  72   BitInit FalseBitInit;
  73
  74   FoldingSet<ArgumentInit> TheArgumentInitPool;
  75   FoldingSet<BitsInit> TheBitsInitPool;
  76   std::map<int64_t, IntInit *> TheIntInitPool;
  77   StringMap<const StringInit *, BumpPtrAllocator &> StringInitStringPool;
  78   StringMap<const StringInit *, BumpPtrAllocator &> StringInitCodePool;
  79   FoldingSet<ListInit> TheListInitPool;
  80   FoldingSet<UnOpInit> TheUnOpInitPool;
  81   FoldingSet<BinOpInit> TheBinOpInitPool;
  82   FoldingSet<TernOpInit> TheTernOpInitPool;
  83   FoldingSet<FoldOpInit> TheFoldOpInitPool;
  84   FoldingSet<IsAOpInit> TheIsAOpInitPool;
  85   FoldingSet<ExistsOpInit> TheExistsOpInitPool;
  86   DenseMap<std::pair<const RecTy *, const Init *>, VarInit *> TheVarInitPool;
  87   DenseMap<std::pair<const TypedInit *, unsigned>, VarBitInit *>
  88       TheVarBitInitPool;
  89   FoldingSet<VarDefInit> TheVarDefInitPool;
  90   DenseMap<std::pair<const Init *, const StringInit *>, FieldInit *>
  91       TheFieldInitPool;
  92   FoldingSet<CondOpInit> TheCondOpInitPool;
  93   FoldingSet<DagInit> TheDagInitPool;
  94   FoldingSet<RecordRecTy> RecordTypePool;
  95
  96   unsigned AnonCounter;
  97   unsigned LastRecordID;
  98
  99   void dumpAllocationStats(raw_ostream &OS) const;
 100 };
 101 } // namespace detail
 102 } // namespace llvm
 103
 104 void detail::RecordKeeperImpl::dumpAllocationStats(raw_ostream &OS) const {
 105   // Dump memory allocation related stats.
 106   OS << "TheArgumentInitPool size = " << TheArgumentInitPool.size() << '\n';
 107   OS << "TheBitsInitPool size = " << TheBitsInitPool.size() << '\n';
 108   OS << "TheIntInitPool size = " << TheIntInitPool.size() << '\n';
 109   OS << "TheBitsInitPool size = " << TheBitsInitPool.size() << '\n';
 110   OS << "TheListInitPool size = " << TheListInitPool.size() << '\n';
 111   OS << "TheUnOpInitPool size = " << TheUnOpInitPool.size() << '\n';
 112   OS << "TheBinOpInitPool size = " << TheBinOpInitPool.size() << '\n';
 113   OS << "TheTernOpInitPool size = " << TheTernOpInitPool.size() << '\n';
 114   OS << "TheFoldOpInitPool size = " << TheFoldOpInitPool.size() << '\n';
 115   OS << "TheIsAOpInitPool size = " << TheIsAOpInitPool.size() << '\n';
 116   OS << "TheExistsOpInitPool size = " << TheExistsOpInitPool.size() << '\n';
 117   OS << "TheCondOpInitPool size = " << TheCondOpInitPool.size() << '\n';
 118   OS << "TheDagInitPool size = " << TheDagInitPool.size() << '\n';
 119   OS << "RecordTypePool size = " << RecordTypePool.size() << '\n';
 120   OS << "TheVarInitPool size = " << TheVarInitPool.size() << '\n';
 121   OS << "TheVarBitInitPool size = " << TheVarBitInitPool.size() << '\n';
 122   OS << "TheVarDefInitPool size = " << TheVarDefInitPool.size() << '\n';
 123   OS << "TheFieldInitPool size = " << TheFieldInitPool.size() << '\n';
 124   OS << "Bytes allocated = " << Allocator.getBytesAllocated() << '\n';
 125   OS << "Total allocator memory = " << Allocator.getTotalMemory() << "\n\n";
 126
 127   OS << "Number of records instantiated = " << LastRecordID << '\n';
 128   OS << "Number of anonymous records = " << AnonCounter << '\n';
 129 }
 130
 131 //===----------------------------------------------------------------------===//
 132 //    Type implementations
 133 //===----------------------------------------------------------------------===//
 134
 135 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 136 LLVM_DUMP_METHOD void RecTy::dump() const { print(errs()); }
 137 #endif
 138
 139 const ListRecTy *RecTy::getListTy() const {
 140   if (!ListTy)
 141     ListTy = new (RK.getImpl().Allocator) ListRecTy(this);
 142   return ListTy;
 143 }
 144
 145 bool RecTy::typeIsConvertibleTo(const RecTy *RHS) const {
 146   assert(RHS && "NULL pointer");
 147   return Kind == RHS->getRecTyKind();
 148 }
 149
 150 bool RecTy::typeIsA(const RecTy *RHS) const { return this == RHS; }
 151
 152 const BitRecTy *BitRecTy::get(RecordKeeper &RK) {
 153   return &RK.getImpl().SharedBitRecTy;
 154 }
 155
 156 bool BitRecTy::typeIsConvertibleTo(const RecTy *RHS) const{
 157   if (RecTy::typeIsConvertibleTo(RHS) || RHS->getRecTyKind() == IntRecTyKind)
 158     return true;
 159   if (const auto *BitsTy = dyn_cast<BitsRecTy>(RHS))
 160     return BitsTy->getNumBits() == 1;
 161   return false;
 162 }
 163
 164 const BitsRecTy *BitsRecTy::get(RecordKeeper &RK, unsigned Sz) {
 165   detail::RecordKeeperImpl &RKImpl = RK.getImpl();
 166   if (Sz >= RKImpl.SharedBitsRecTys.size())
 167     RKImpl.SharedBitsRecTys.resize(Sz + 1);
 168   BitsRecTy *&Ty = RKImpl.SharedBitsRecTys[Sz];
 169   if (!Ty)
 170     Ty = new (RKImpl.Allocator) BitsRecTy(RK, Sz);
 171   return Ty;
 172 }
 173
 174 std::string BitsRecTy::getAsString() const {
 175   return "bits<" + utostr(Size) + ">";
 176 }
 177
 178 bool BitsRecTy::typeIsConvertibleTo(const RecTy *RHS) const {
 179   if (RecTy::typeIsConvertibleTo(RHS)) //argument and the sender are same type
 180     return cast<BitsRecTy>(RHS)->Size == Size;
 181   RecTyKind kind = RHS->getRecTyKind();
 182   return (kind == BitRecTyKind && Size == 1) || (kind == IntRecTyKind);
 183 }
 184
 185 const IntRecTy *IntRecTy::get(RecordKeeper &RK) {
 186   return &RK.getImpl().SharedIntRecTy;
 187 }
 188
 189 bool IntRecTy::typeIsConvertibleTo(const RecTy *RHS) const {
 190   RecTyKind kind = RHS->getRecTyKind();
 191   return kind==BitRecTyKind || kind==BitsRecTyKind || kind==IntRecTyKind;
 192 }
 193
 194 const StringRecTy *StringRecTy::get(RecordKeeper &RK) {
 195   return &RK.getImpl().SharedStringRecTy;
 196 }
 197
 198 std::string StringRecTy::getAsString() const {
 199   return "string";
 200 }
 201
 202 bool StringRecTy::typeIsConvertibleTo(const RecTy *RHS) const {
 203   RecTyKind Kind = RHS->getRecTyKind();
 204   return Kind == StringRecTyKind;
 205 }
 206
 207 std::string ListRecTy::getAsString() const {
 208   return "list<" + ElementTy->getAsString() + ">";
 209 }
 210
 211 bool ListRecTy::typeIsConvertibleTo(const RecTy *RHS) const {
 212   if (const auto *ListTy = dyn_cast<ListRecTy>(RHS))
 213     return ElementTy->typeIsConvertibleTo(ListTy->getElementType());
 214   return false;
 215 }
 216
 217 bool ListRecTy::typeIsA(const RecTy *RHS) const {
 218   if (const auto *RHSl = dyn_cast<ListRecTy>(RHS))
 219     return getElementType()->typeIsA(RHSl->getElementType());
 220   return false;
 221 }
 222
 223 const DagRecTy *DagRecTy::get(RecordKeeper &RK) {
 224   return &RK.getImpl().SharedDagRecTy;
 225 }
 226
 227 std::string DagRecTy::getAsString() const {
 228   return "dag";
 229 }
 230
 231 static void ProfileRecordRecTy(FoldingSetNodeID &ID,
 232                                ArrayRef<const Record *> Classes) {
 233   ID.AddInteger(Classes.size());
 234   for (const Record *R : Classes)
 235     ID.AddPointer(R);
 236 }
 237
 238 const RecordRecTy *RecordRecTy::get(RecordKeeper &RK,
 239                                     ArrayRef<const Record *> UnsortedClasses) {
 240   detail::RecordKeeperImpl &RKImpl = RK.getImpl();
 241   if (UnsortedClasses.empty())
 242     return &RKImpl.AnyRecord;
 243
 244   FoldingSet<RecordRecTy> &ThePool = RKImpl.RecordTypePool;
 245
 246   SmallVector<const Record *, 4> Classes(UnsortedClasses);
 247   llvm::sort(Classes, [](const Record *LHS, const Record *RHS) {
 248     return LHS->getNameInitAsString() < RHS->getNameInitAsString();
 249   });
 250
 251   FoldingSetNodeID ID;
 252   ProfileRecordRecTy(ID, Classes);
 253
 254   void *IP = nullptr;
 255   if (RecordRecTy *Ty = ThePool.FindNodeOrInsertPos(ID, IP))
 256     return Ty;
 257
 258 #ifndef NDEBUG
 259   // Check for redundancy.
 260   for (unsigned i = 0; i < Classes.size(); ++i) {
 261     for (unsigned j = 0; j < Classes.size(); ++j) {
 262       assert(i == j || !Classes[i]->isSubClassOf(Classes[j]));
 263     }
 264     assert(&Classes[0]->getRecords() == &Classes[i]->getRecords());
 265   }
 266 #endif
 267
 268   void *Mem = RKImpl.Allocator.Allocate(
 269       totalSizeToAlloc<const Record *>(Classes.size()), alignof(RecordRecTy));
 270   RecordRecTy *Ty = new (Mem) RecordRecTy(RK, Classes.size());
 271   std::uninitialized_copy(Classes.begin(), Classes.end(),
 272                           Ty->getTrailingObjects<const Record *>());
 273   ThePool.InsertNode(Ty, IP);
 274   return Ty;
 275 }
 276
 277 const RecordRecTy *RecordRecTy::get(const Record *Class) {
 278   assert(Class && "unexpected null class");
 279   return get(Class->getRecords(), {Class});
 280 }
 281
 282 void RecordRecTy::Profile(FoldingSetNodeID &ID) const {
 283   ProfileRecordRecTy(ID, getClasses());
 284 }
 285
 286 std::string RecordRecTy::getAsString() const {
 287   if (NumClasses == 1)
 288     return getClasses()[0]->getNameInitAsString();
 289
 290   std::string Str = "{";
 291   bool First = true;
 292   for (const Record *R : getClasses()) {
 293     if (!First)
 294       Str += ", ";
 295     First = false;
 296     Str += R->getNameInitAsString();
 297   }
 298   Str += "}";
 299   return Str;
 300 }
 301
 302 bool RecordRecTy::isSubClassOf(const Record *Class) const {
 303   return llvm::any_of(getClasses(), [Class](const Record *MySuperClass) {
 304     return MySuperClass == Class || MySuperClass->isSubClassOf(Class);
 305   });
 306 }
 307
 308 bool RecordRecTy::typeIsConvertibleTo(const RecTy *RHS) const {
 309   if (this == RHS)
 310     return true;
 311
 312   const auto *RTy = dyn_cast<RecordRecTy>(RHS);
 313   if (!RTy)
 314     return false;
 315
 316   return llvm::all_of(RTy->getClasses(), [this](const Record *TargetClass) {
 317     return isSubClassOf(TargetClass);
 318   });
 319 }
 320
 321 bool RecordRecTy::typeIsA(const RecTy *RHS) const {
 322   return typeIsConvertibleTo(RHS);
 323 }
 324
 325 static const RecordRecTy *resolveRecordTypes(const RecordRecTy *T1,
 326                                              const RecordRecTy *T2) {
 327   SmallVector<const Record *, 4> CommonSuperClasses;
 328   SmallVector<const Record *, 4> Stack(T1->getClasses());
 329
 330   while (!Stack.empty()) {
 331     const Record *R = Stack.pop_back_val();
 332
 333     if (T2->isSubClassOf(R)) {
 334       CommonSuperClasses.push_back(R);
 335     } else {
 336       R->getDirectSuperClasses(Stack);
 337     }
 338   }
 339
 340   return RecordRecTy::get(T1->getRecordKeeper(), CommonSuperClasses);
 341 }
 342
 343 const RecTy *llvm::resolveTypes(const RecTy *T1, const RecTy *T2) {
 344   if (T1 == T2)
 345     return T1;
 346
 347   if (const auto *RecTy1 = dyn_cast<RecordRecTy>(T1)) {
 348     if (const auto *RecTy2 = dyn_cast<RecordRecTy>(T2))
 349       return resolveRecordTypes(RecTy1, RecTy2);
 350   }
 351
 352   assert(T1 != nullptr && "Invalid record type");
 353   if (T1->typeIsConvertibleTo(T2))
 354     return T2;
 355
 356   assert(T2 != nullptr && "Invalid record type");
 357   if (T2->typeIsConvertibleTo(T1))
 358     return T1;
 359
 360   if (const auto *ListTy1 = dyn_cast<ListRecTy>(T1)) {
 361     if (const auto *ListTy2 = dyn_cast<ListRecTy>(T2)) {
 362       const RecTy *NewType =
 363           resolveTypes(ListTy1->getElementType(), ListTy2->getElementType());
 364       if (NewType)
 365         return NewType->getListTy();
 366     }
 367   }
 368
 369   return nullptr;
 370 }
 371
 372 //===----------------------------------------------------------------------===//
 373 //    Initializer implementations
 374 //===----------------------------------------------------------------------===//
 375
 376 void Init::anchor() {}
 377
 378 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 379 LLVM_DUMP_METHOD void Init::dump() const { return print(errs()); }
 380 #endif
 381
 382 RecordKeeper &Init::getRecordKeeper() const {
 383   if (auto *TyInit = dyn_cast<TypedInit>(this))
 384     return TyInit->getType()->getRecordKeeper();
 385   if (auto *ArgInit = dyn_cast<ArgumentInit>(this))
 386     return ArgInit->getRecordKeeper();
 387   return cast<UnsetInit>(this)->getRecordKeeper();
 388 }
 389
 390 UnsetInit *UnsetInit::get(RecordKeeper &RK) {
 391   return &RK.getImpl().TheUnsetInit;
 392 }
 393
 394 const Init *UnsetInit::getCastTo(const RecTy *Ty) const { return this; }
 395
 396 const Init *UnsetInit::convertInitializerTo(const RecTy *Ty) const {
 397   return this;
 398 }
 399
 400 static void ProfileArgumentInit(FoldingSetNodeID &ID, const Init *Value,
 401                                 ArgAuxType Aux) {
 402   auto I = Aux.index();
 403   ID.AddInteger(I);
 404   if (I == ArgumentInit::Positional)
 405     ID.AddInteger(std::get<ArgumentInit::Positional>(Aux));
 406   if (I == ArgumentInit::Named)
 407     ID.AddPointer(std::get<ArgumentInit::Named>(Aux));
 408   ID.AddPointer(Value);
 409 }
 410
 411 void ArgumentInit::Profile(FoldingSetNodeID &ID) const {
 412   ProfileArgumentInit(ID, Value, Aux);
 413 }
 414
 415 const ArgumentInit *ArgumentInit::get(const Init *Value, ArgAuxType Aux) {
 416   FoldingSetNodeID ID;
 417   ProfileArgumentInit(ID, Value, Aux);
 418
 419   RecordKeeper &RK = Value->getRecordKeeper();
 420   detail::RecordKeeperImpl &RKImpl = RK.getImpl();
 421   void *IP = nullptr;
 422   if (const ArgumentInit *I =
 423           RKImpl.TheArgumentInitPool.FindNodeOrInsertPos(ID, IP))
 424     return I;
 425
 426   ArgumentInit *I = new (RKImpl.Allocator) ArgumentInit(Value, Aux);
 427   RKImpl.TheArgumentInitPool.InsertNode(I, IP);
 428   return I;
 429 }
 430
 431 const Init *ArgumentInit::resolveReferences(Resolver &R) const {
 432   const Init *NewValue = Value->resolveReferences(R);
 433   if (NewValue != Value)
 434     return cloneWithValue(NewValue);
 435
 436   return this;
 437 }
 438
 439 BitInit *BitInit::get(RecordKeeper &RK, bool V) {
 440   return V ? &RK.getImpl().TrueBitInit : &RK.getImpl().FalseBitInit;
 441 }
 442
 443 const Init *BitInit::convertInitializerTo(const RecTy *Ty) const {
 444   if (isa<BitRecTy>(Ty))
 445     return this;
 446
 447   if (isa<IntRecTy>(Ty))
 448     return IntInit::get(getRecordKeeper(), getValue());
 449
 450   if (auto *BRT = dyn_cast<BitsRecTy>(Ty)) {
 451     // Can only convert single bit.
 452     if (BRT->getNumBits() == 1)
 453       return BitsInit::get(getRecordKeeper(), this);
 454   }
 455
 456   return nullptr;
 457 }
 458
 459 static void ProfileBitsInit(FoldingSetNodeID &ID,
 460                             ArrayRef<const Init *> Range) {
 461   ID.AddInteger(Range.size());
 462
 463   for (const Init *I : Range)
 464     ID.AddPointer(I);
 465 }
 466
 467 BitsInit *BitsInit::get(RecordKeeper &RK, ArrayRef<const Init *> Range) {
 468   FoldingSetNodeID ID;
 469   ProfileBitsInit(ID, Range);
 470
 471   detail::RecordKeeperImpl &RKImpl = RK.getImpl();
 472   void *IP = nullptr;
 473   if (BitsInit *I = RKImpl.TheBitsInitPool.FindNodeOrInsertPos(ID, IP))
 474     return I;
 475
 476   void *Mem = RKImpl.Allocator.Allocate(
 477       totalSizeToAlloc<const Init *>(Range.size()), alignof(BitsInit));
 478   BitsInit *I = new (Mem) BitsInit(RK, Range.size());
 479   std::uninitialized_copy(Range.begin(), Range.end(),
 480                           I->getTrailingObjects<const Init *>());
 481   RKImpl.TheBitsInitPool.InsertNode(I, IP);
 482   return I;
 483 }
 484
 485 void BitsInit::Profile(FoldingSetNodeID &ID) const {
 486   ProfileBitsInit(ID, ArrayRef(getTrailingObjects<const Init *>(), NumBits));
 487 }
 488
 489 const Init *BitsInit::convertInitializerTo(const RecTy *Ty) const {
 490   if (isa<BitRecTy>(Ty)) {
 491     if (getNumBits() != 1) return nullptr; // Only accept if just one bit!
 492     return getBit(0);
 493   }
 494
 495   if (auto *BRT = dyn_cast<BitsRecTy>(Ty)) {
 496     // If the number of bits is right, return it.  Otherwise we need to expand
 497     // or truncate.
 498     if (getNumBits() != BRT->getNumBits()) return nullptr;
 499     return this;
 500   }
 501
 502   if (isa<IntRecTy>(Ty)) {
 503     std::optional<int64_t> Result = convertInitializerToInt();
 504     if (Result)
 505       return IntInit::get(getRecordKeeper(), *Result);
 506   }
 507
 508   return nullptr;
 509 }
 510
 511 std::optional<int64_t> BitsInit::convertInitializerToInt() const {
 512   int64_t Result = 0;
 513   for (unsigned i = 0, e = getNumBits(); i != e; ++i)
 514     if (auto *Bit = dyn_cast<BitInit>(getBit(i)))
 515       Result |= static_cast<int64_t>(Bit->getValue()) << i;
 516     else
 517       return std::nullopt;
 518   return Result;
 519 }
 520
 521 const Init *
 522 BitsInit::convertInitializerBitRange(ArrayRef<unsigned> Bits) const {
 523   SmallVector<const Init *, 16> NewBits(Bits.size());
 524
 525   for (unsigned i = 0, e = Bits.size(); i != e; ++i) {
 526     if (Bits[i] >= getNumBits())
 527       return nullptr;
 528     NewBits[i] = getBit(Bits[i]);
 529   }
 530   return BitsInit::get(getRecordKeeper(), NewBits);
 531 }
 532
 533 bool BitsInit::isConcrete() const {
 534   for (unsigned i = 0, e = getNumBits(); i != e; ++i) {
 535     if (!getBit(i)->isConcrete())
 536       return false;
 537   }
 538   return true;
 539 }
 540
 541 std::string BitsInit::getAsString() const {
 542   std::string Result = "{ ";
 543   for (unsigned i = 0, e = getNumBits(); i != e; ++i) {
 544     if (i) Result += ", ";
 545     if (const Init *Bit = getBit(e - i - 1))
 546       Result += Bit->getAsString();
 547     else
 548       Result += "*";
 549   }
 550   return Result + " }";
 551 }
 552
 553 // resolveReferences - If there are any field references that refer to fields
 554 // that have been filled in, we can propagate the values now.
 555 const Init *BitsInit::resolveReferences(Resolver &R) const {
 556   bool Changed = false;
 557   SmallVector<const Init *, 16> NewBits(getNumBits());
 558
 559   const Init *CachedBitVarRef = nullptr;
 560   const Init *CachedBitVarResolved = nullptr;
 561
 562   for (unsigned i = 0, e = getNumBits(); i != e; ++i) {
 563     const Init *CurBit = getBit(i);
 564     const Init *NewBit = CurBit;
 565
 566     if (const auto *CurBitVar = dyn_cast<VarBitInit>(CurBit)) {
 567       if (CurBitVar->getBitVar() != CachedBitVarRef) {
 568         CachedBitVarRef = CurBitVar->getBitVar();
 569         CachedBitVarResolved = CachedBitVarRef->resolveReferences(R);
 570       }
 571       assert(CachedBitVarResolved && "Unresolved bitvar reference");
 572       NewBit = CachedBitVarResolved->getBit(CurBitVar->getBitNum());
 573     } else {
 574       // getBit(0) implicitly converts int and bits<1> values to bit.
 575       NewBit = CurBit->resolveReferences(R)->getBit(0);
 576     }
 577
 578     if (isa<UnsetInit>(NewBit) && R.keepUnsetBits())
 579       NewBit = CurBit;
 580     NewBits[i] = NewBit;
 581     Changed |= CurBit != NewBit;
 582   }
 583
 584   if (Changed)
 585     return BitsInit::get(getRecordKeeper(), NewBits);
 586
 587   return this;
 588 }
 589
 590 IntInit *IntInit::get(RecordKeeper &RK, int64_t V) {
 591   IntInit *&I = RK.getImpl().TheIntInitPool[V];
 592   if (!I)
 593     I = new (RK.getImpl().Allocator) IntInit(RK, V);
 594   return I;
 595 }
 596
 597 std::string IntInit::getAsString() const {
 598   return itostr(Value);
 599 }
 600
 601 static bool canFitInBitfield(int64_t Value, unsigned NumBits) {
 602   // For example, with NumBits == 4, we permit Values from [-7 .. 15].
 603   return (NumBits >= sizeof(Value) * 8) ||
 604          (Value >> NumBits == 0) || (Value >> (NumBits-1) == -1);
 605 }
 606
 607 const Init *IntInit::convertInitializerTo(const RecTy *Ty) const {
 608   if (isa<IntRecTy>(Ty))
 609     return this;
 610
 611   if (isa<BitRecTy>(Ty)) {
 612     int64_t Val = getValue();
 613     if (Val != 0 && Val != 1) return nullptr;  // Only accept 0 or 1 for a bit!
 614     return BitInit::get(getRecordKeeper(), Val != 0);
 615   }
 616
 617   if (const auto *BRT = dyn_cast<BitsRecTy>(Ty)) {
 618     int64_t Value = getValue();
 619     // Make sure this bitfield is large enough to hold the integer value.
 620     if (!canFitInBitfield(Value, BRT->getNumBits()))
 621       return nullptr;
 622
 623     SmallVector<const Init *, 16> NewBits(BRT->getNumBits());
 624     for (unsigned i = 0; i != BRT->getNumBits(); ++i)
 625       NewBits[i] =
 626           BitInit::get(getRecordKeeper(), Value & ((i < 64) ? (1LL << i) : 0));
 627
 628     return BitsInit::get(getRecordKeeper(), NewBits);
 629   }
 630
 631   return nullptr;
 632 }
 633
 634 const Init *IntInit::convertInitializerBitRange(ArrayRef<unsigned> Bits) const {
 635   SmallVector<const Init *, 16> NewBits(Bits.size());
 636
 637   for (unsigned i = 0, e = Bits.size(); i != e; ++i) {
 638     if (Bits[i] >= 64)
 639       return nullptr;
 640
 641     NewBits[i] =
 642         BitInit::get(getRecordKeeper(), Value & (INT64_C(1) << Bits[i]));
 643   }
 644   return BitsInit::get(getRecordKeeper(), NewBits);
 645 }
 646
 647 AnonymousNameInit *AnonymousNameInit::get(RecordKeeper &RK, unsigned V) {
 648   return new (RK.getImpl().Allocator) AnonymousNameInit(RK, V);
 649 }
 650
 651 const StringInit *AnonymousNameInit::getNameInit() const {
 652   return StringInit::get(getRecordKeeper(), getAsString());
 653 }
 654
 655 std::string AnonymousNameInit::getAsString() const {
 656   return "anonymous_" + utostr(Value);
 657 }
 658
 659 const Init *AnonymousNameInit::resolveReferences(Resolver &R) const {
 660   auto *Old = this;
 661   auto *New = R.resolve(Old);
 662   New = New ? New : Old;
 663   if (R.isFinal())
 664     if (const auto *Anonymous = dyn_cast<AnonymousNameInit>(New))
 665       return Anonymous->getNameInit();
 666   return New;
 667 }
 668
 669 const StringInit *StringInit::get(RecordKeeper &RK, StringRef V,
 670                                   StringFormat Fmt) {
 671   detail::RecordKeeperImpl &RKImpl = RK.getImpl();
 672   auto &InitMap = Fmt == SF_String ? RKImpl.StringInitStringPool
 673                                    : RKImpl.StringInitCodePool;
 674   auto &Entry = *InitMap.insert(std::make_pair(V, nullptr)).first;
 675   if (!Entry.second)
 676     Entry.second = new (RKImpl.Allocator) StringInit(RK, Entry.getKey(), Fmt);
 677   return Entry.second;
 678 }
 679
 680 const Init *StringInit::convertInitializerTo(const RecTy *Ty) const {
 681   if (isa<StringRecTy>(Ty))
 682     return this;
 683
 684   return nullptr;
 685 }
 686
 687 static void ProfileListInit(FoldingSetNodeID &ID, ArrayRef<const Init *> Range,
 688                             const RecTy *EltTy) {
 689   ID.AddInteger(Range.size());
 690   ID.AddPointer(EltTy);
 691
 692   for (const Init *I : Range)
 693     ID.AddPointer(I);
 694 }
 695
 696 const ListInit *ListInit::get(ArrayRef<const Init *> Range,
 697                               const RecTy *EltTy) {
 698   FoldingSetNodeID ID;
 699   ProfileListInit(ID, Range, EltTy);
 700
 701   detail::RecordKeeperImpl &RK = EltTy->getRecordKeeper().getImpl();
 702   void *IP = nullptr;
 703   if (const ListInit *I = RK.TheListInitPool.FindNodeOrInsertPos(ID, IP))
 704     return I;
 705
 706   assert(Range.empty() || !isa<TypedInit>(Range[0]) ||
 707          cast<TypedInit>(Range[0])->getType()->typeIsConvertibleTo(EltTy));
 708
 709   void *Mem = RK.Allocator.Allocate(
 710       totalSizeToAlloc<const Init *>(Range.size()), alignof(ListInit));
 711   ListInit *I = new (Mem) ListInit(Range.size(), EltTy);
 712   std::uninitialized_copy(Range.begin(), Range.end(),
 713                           I->getTrailingObjects<const Init *>());
 714   RK.TheListInitPool.InsertNode(I, IP);
 715   return I;
 716 }
 717
 718 void ListInit::Profile(FoldingSetNodeID &ID) const {
 719   const RecTy *EltTy = cast<ListRecTy>(getType())->getElementType();
 720
 721   ProfileListInit(ID, getValues(), EltTy);
 722 }
 723
 724 const Init *ListInit::convertInitializerTo(const RecTy *Ty) const {
 725   if (getType() == Ty)
 726     return this;
 727
 728   if (const auto *LRT = dyn_cast<ListRecTy>(Ty)) {
 729     SmallVector<const Init *, 8> Elements;
 730     Elements.reserve(getValues().size());
 731
 732     // Verify that all of the elements of the list are subclasses of the
 733     // appropriate class!
 734     bool Changed = false;
 735     const RecTy *ElementType = LRT->getElementType();
 736     for (const Init *I : getValues())
 737       if (const Init *CI = I->convertInitializerTo(ElementType)) {
 738         Elements.push_back(CI);
 739         if (CI != I)
 740           Changed = true;
 741       } else
 742         return nullptr;
 743
 744     if (!Changed)
 745       return this;
 746     return ListInit::get(Elements, ElementType);
 747   }
 748
 749   return nullptr;
 750 }
 751
 752 const Record *ListInit::getElementAsRecord(unsigned i) const {
 753   assert(i < NumValues && "List element index out of range!");
 754   const auto *DI = dyn_cast<DefInit>(getElement(i));
 755   if (!DI)
 756     PrintFatalError("Expected record in list!");
 757   return DI->getDef();
 758 }
 759
 760 const Init *ListInit::resolveReferences(Resolver &R) const {
 761   SmallVector<const Init *, 8> Resolved;
 762   Resolved.reserve(size());
 763   bool Changed = false;
 764
 765   for (const Init *CurElt : getValues()) {
 766     const Init *E = CurElt->resolveReferences(R);
 767     Changed |= E != CurElt;
 768     Resolved.push_back(E);
 769   }
 770
 771   if (Changed)
 772     return ListInit::get(Resolved, getElementType());
 773   return this;
 774 }
 775
 776 bool ListInit::isComplete() const {
 777   for (const Init *Element : *this) {
 778     if (!Element->isComplete())
 779       return false;
 780   }
 781   return true;
 782 }
 783
 784 bool ListInit::isConcrete() const {
 785   for (const Init *Element : *this) {
 786     if (!Element->isConcrete())
 787       return false;
 788   }
 789   return true;
 790 }
 791
 792 std::string ListInit::getAsString() const {
 793   std::string Result = "[";
 794   const char *sep = "";
 795   for (const Init *Element : *this) {
 796     Result += sep;
 797     sep = ", ";
 798     Result += Element->getAsString();
 799   }
 800   return Result + "]";
 801 }
 802
 803 const Init *OpInit::getBit(unsigned Bit) const {
 804   if (getType() == BitRecTy::get(getRecordKeeper()))
 805     return this;
 806   return VarBitInit::get(this, Bit);
 807 }
 808
 809 static void ProfileUnOpInit(FoldingSetNodeID &ID, unsigned Opcode,
 810                             const Init *Op, const RecTy *Type) {
 811   ID.AddInteger(Opcode);
 812   ID.AddPointer(Op);
 813   ID.AddPointer(Type);
 814 }
 815
 816 const UnOpInit *UnOpInit::get(UnaryOp Opc, const Init *LHS, const RecTy *Type) {
 817   FoldingSetNodeID ID;
 818   ProfileUnOpInit(ID, Opc, LHS, Type);
 819
 820   detail::RecordKeeperImpl &RK = Type->getRecordKeeper().getImpl();
 821   void *IP = nullptr;
 822   if (const UnOpInit *I = RK.TheUnOpInitPool.FindNodeOrInsertPos(ID, IP))
 823     return I;
 824
 825   UnOpInit *I = new (RK.Allocator) UnOpInit(Opc, LHS, Type);
 826   RK.TheUnOpInitPool.InsertNode(I, IP);
 827   return I;
 828 }
 829
 830 void UnOpInit::Profile(FoldingSetNodeID &ID) const {
 831   ProfileUnOpInit(ID, getOpcode(), getOperand(), getType());
 832 }
 833
 834 const Init *UnOpInit::Fold(const Record *CurRec, bool IsFinal) const {
 835   RecordKeeper &RK = getRecordKeeper();
 836   switch (getOpcode()) {
 837   case REPR:
 838     if (LHS->isConcrete()) {
 839       // If it is a Record, print the full content.
 840       if (const auto *Def = dyn_cast<DefInit>(LHS)) {
 841         std::string S;
 842         raw_string_ostream OS(S);
 843         OS << *Def->getDef();
 844         return StringInit::get(RK, S);
 845       } else {
 846         // Otherwise, print the value of the variable.
 847         //
 848         // NOTE: we could recursively !repr the elements of a list,
 849         // but that could produce a lot of output when printing a
 850         // defset.
 851         return StringInit::get(RK, LHS->getAsString());
 852       }
 853     }
 854     break;
 855   case TOLOWER:
 856     if (const auto *LHSs = dyn_cast<StringInit>(LHS))
 857       return StringInit::get(RK, LHSs->getValue().lower());
 858     break;
 859   case TOUPPER:
 860     if (const auto *LHSs = dyn_cast<StringInit>(LHS))
 861       return StringInit::get(RK, LHSs->getValue().upper());
 862     break;
 863   case CAST:
 864     if (isa<StringRecTy>(getType())) {
 865       if (const auto *LHSs = dyn_cast<StringInit>(LHS))
 866         return LHSs;
 867
 868       if (const auto *LHSd = dyn_cast<DefInit>(LHS))
 869         return StringInit::get(RK, LHSd->getAsString());
 870
 871       if (const auto *LHSi = dyn_cast_or_null<IntInit>(
 872               LHS->convertInitializerTo(IntRecTy::get(RK))))
 873         return StringInit::get(RK, LHSi->getAsString());
 874
 875     } else if (isa<RecordRecTy>(getType())) {
 876       if (const auto *Name = dyn_cast<StringInit>(LHS)) {
 877         const Record *D = RK.getDef(Name->getValue());
 878         if (!D && CurRec) {
 879           // Self-references are allowed, but their resolution is delayed until
 880           // the final resolve to ensure that we get the correct type for them.
 881           auto *Anonymous = dyn_cast<AnonymousNameInit>(CurRec->getNameInit());
 882           if (Name == CurRec->getNameInit() ||
 883               (Anonymous && Name == Anonymous->getNameInit())) {
 884             if (!IsFinal)
 885               break;
 886             D = CurRec;
 887           }
 888         }
 889
 890         auto PrintFatalErrorHelper = [CurRec](const Twine &T) {
 891           if (CurRec)
 892             PrintFatalError(CurRec->getLoc(), T);
 893           else
 894             PrintFatalError(T);
 895         };
 896
 897         if (!D) {
 898           if (IsFinal) {
 899             PrintFatalErrorHelper(Twine("Undefined reference to record: '") +
 900                                   Name->getValue() + "'\n");
 901           }
 902           break;
 903         }
 904
 905         DefInit *DI = D->getDefInit();
 906         if (!DI->getType()->typeIsA(getType())) {
 907           PrintFatalErrorHelper(Twine("Expected type '") +
 908                                 getType()->getAsString() + "', got '" +
 909                                 DI->getType()->getAsString() + "' in: " +
 910                                 getAsString() + "\n");
 911         }
 912         return DI;
 913       }
 914     }
 915
 916     if (const Init *NewInit = LHS->convertInitializerTo(getType()))
 917       return NewInit;
 918     break;
 919
 920   case INITIALIZED:
 921     if (isa<UnsetInit>(LHS))
 922       return IntInit::get(RK, 0);
 923     if (LHS->isConcrete())
 924       return IntInit::get(RK, 1);
 925     break;
 926
 927   case NOT:
 928     if (const auto *LHSi = dyn_cast_or_null<IntInit>(
 929             LHS->convertInitializerTo(IntRecTy::get(RK))))
 930       return IntInit::get(RK, LHSi->getValue() ? 0 : 1);
 931     break;
 932
 933   case HEAD:
 934     if (const auto *LHSl = dyn_cast<ListInit>(LHS)) {
 935       assert(!LHSl->empty() && "Empty list in head");
 936       return LHSl->getElement(0);
 937     }
 938     break;
 939
 940   case TAIL:
 941     if (const auto *LHSl = dyn_cast<ListInit>(LHS)) {
 942       assert(!LHSl->empty() && "Empty list in tail");
 943       // Note the +1.  We can't just pass the result of getValues()
 944       // directly.
 945       return ListInit::get(LHSl->getValues().slice(1), LHSl->getElementType());
 946     }
 947     break;
 948
 949   case SIZE:
 950     if (const auto *LHSl = dyn_cast<ListInit>(LHS))
 951       return IntInit::get(RK, LHSl->size());
 952     if (const auto *LHSd = dyn_cast<DagInit>(LHS))
 953       return IntInit::get(RK, LHSd->arg_size());
 954     if (const auto *LHSs = dyn_cast<StringInit>(LHS))
 955       return IntInit::get(RK, LHSs->getValue().size());
 956     break;
 957
 958   case EMPTY:
 959     if (const auto *LHSl = dyn_cast<ListInit>(LHS))
 960       return IntInit::get(RK, LHSl->empty());
 961     if (const auto *LHSd = dyn_cast<DagInit>(LHS))
 962       return IntInit::get(RK, LHSd->arg_empty());
 963     if (const auto *LHSs = dyn_cast<StringInit>(LHS))
 964       return IntInit::get(RK, LHSs->getValue().empty());
 965     break;
 966
 967   case GETDAGOP:
 968     if (const auto *Dag = dyn_cast<DagInit>(LHS)) {
 969       // TI is not necessarily a def due to the late resolution in multiclasses,
 970       // but has to be a TypedInit.
 971       auto *TI = cast<TypedInit>(Dag->getOperator());
 972       if (!TI->getType()->typeIsA(getType())) {
 973         PrintFatalError(CurRec->getLoc(),
 974                         Twine("Expected type '") + getType()->getAsString() +
 975                             "', got '" + TI->getType()->getAsString() +
 976                             "' in: " + getAsString() + "\n");
 977       } else {
 978         return Dag->getOperator();
 979       }
 980     }
 981     break;
 982
 983   case LOG2:
 984     if (const auto *LHSi = dyn_cast_or_null<IntInit>(
 985             LHS->convertInitializerTo(IntRecTy::get(RK)))) {
 986       int64_t LHSv = LHSi->getValue();
 987       if (LHSv <= 0) {
 988         PrintFatalError(CurRec->getLoc(),
 989                         "Illegal operation: logtwo is undefined "
 990                         "on arguments less than or equal to 0");
 991       } else {
 992         uint64_t Log = Log2_64(LHSv);
 993         assert(Log <= INT64_MAX &&
 994                "Log of an int64_t must be smaller than INT64_MAX");
 995         return IntInit::get(RK, static_cast<int64_t>(Log));
 996       }
 997     }
 998     break;
 999
1000   case LISTFLATTEN:
1001     if (const auto *LHSList = dyn_cast<ListInit>(LHS)) {
1002       const auto *InnerListTy = dyn_cast<ListRecTy>(LHSList->getElementType());
1003       // list of non-lists, !listflatten() is a NOP.
1004       if (!InnerListTy)
1005         return LHS;
1006
1007       auto Flatten =
1008           [](const ListInit *List) -> std::optional<std::vector<const Init *>> {
1009         std::vector<const Init *> Flattened;
1010         // Concatenate elements of all the inner lists.
1011         for (const Init *InnerInit : List->getValues()) {
1012           const auto *InnerList = dyn_cast<ListInit>(InnerInit);
1013           if (!InnerList)
1014             return std::nullopt;
1015           for (const Init *InnerElem : InnerList->getValues())
1016             Flattened.push_back(InnerElem);
1017         };
1018         return Flattened;
1019       };
1020
1021       auto Flattened = Flatten(LHSList);
1022       if (Flattened)
1023         return ListInit::get(*Flattened, InnerListTy->getElementType());
1024     }
1025     break;
1026   }
1027   return this;
1028 }
1029
1030 const Init *UnOpInit::resolveReferences(Resolver &R) const {
1031   const Init *lhs = LHS->resolveReferences(R);
1032
1033   if (LHS != lhs || (R.isFinal() && getOpcode() == CAST))
1034     return (UnOpInit::get(getOpcode(), lhs, getType()))
1035         ->Fold(R.getCurrentRecord(), R.isFinal());
1036   return this;
1037 }
1038
1039 std::string UnOpInit::getAsString() const {
1040   std::string Result;
1041   switch (getOpcode()) {
1042   case CAST: Result = "!cast<" + getType()->getAsString() + ">"; break;
1043   case NOT: Result = "!not"; break;
1044   case HEAD: Result = "!head"; break;
1045   case TAIL: Result = "!tail"; break;
1046   case SIZE: Result = "!size"; break;
1047   case EMPTY: Result = "!empty"; break;
1048   case GETDAGOP: Result = "!getdagop"; break;
1049   case LOG2 : Result = "!logtwo"; break;
1050   case LISTFLATTEN:
1051     Result = "!listflatten";
1052     break;
1053   case REPR:
1054     Result = "!repr";
1055     break;
1056   case TOLOWER:
1057     Result = "!tolower";
1058     break;
1059   case TOUPPER:
1060     Result = "!toupper";
1061     break;
1062   case INITIALIZED:
1063     Result = "!initialized";
1064     break;
1065   }
1066   return Result + "(" + LHS->getAsString() + ")";
1067 }
1068
1069 static void ProfileBinOpInit(FoldingSetNodeID &ID, unsigned Opcode,
1070                              const Init *LHS, const Init *RHS,
1071                              const RecTy *Type) {
1072   ID.AddInteger(Opcode);
1073   ID.AddPointer(LHS);
1074   ID.AddPointer(RHS);
1075   ID.AddPointer(Type);
1076 }
1077
1078 const BinOpInit *BinOpInit::get(BinaryOp Opc, const Init *LHS, const Init *RHS,
1079                                 const RecTy *Type) {
1080   FoldingSetNodeID ID;
1081   ProfileBinOpInit(ID, Opc, LHS, RHS, Type);
1082
1083   detail::RecordKeeperImpl &RK = LHS->getRecordKeeper().getImpl();
1084   void *IP = nullptr;
1085   if (const BinOpInit *I = RK.TheBinOpInitPool.FindNodeOrInsertPos(ID, IP))
1086     return I;
1087
1088   BinOpInit *I = new (RK.Allocator) BinOpInit(Opc, LHS, RHS, Type);
1089   RK.TheBinOpInitPool.InsertNode(I, IP);
1090   return I;
1091 }
1092
1093 void BinOpInit::Profile(FoldingSetNodeID &ID) const {
1094   ProfileBinOpInit(ID, getOpcode(), getLHS(), getRHS(), getType());
1095 }
1096
1097 static const StringInit *ConcatStringInits(const StringInit *I0,
1098                                            const StringInit *I1) {
1099   SmallString<80> Concat(I0->getValue());
1100   Concat.append(I1->getValue());
1101   return StringInit::get(
1102       I0->getRecordKeeper(), Concat,
1103       StringInit::determineFormat(I0->getFormat(), I1->getFormat()));
1104 }
1105
1106 static const StringInit *interleaveStringList(const ListInit *List,
1107                                               const StringInit *Delim) {
1108   if (List->size() == 0)
1109     return StringInit::get(List->getRecordKeeper(), "");
1110   const auto *Element = dyn_cast<StringInit>(List->getElement(0));
1111   if (!Element)
1112     return nullptr;
1113   SmallString<80> Result(Element->getValue());
1114   StringInit::StringFormat Fmt = StringInit::SF_String;
1115
1116   for (unsigned I = 1, E = List->size(); I < E; ++I) {
1117     Result.append(Delim->getValue());
1118     const auto *Element = dyn_cast<StringInit>(List->getElement(I));
1119     if (!Element)
1120       return nullptr;
1121     Result.append(Element->getValue());
1122     Fmt = StringInit::determineFormat(Fmt, Element->getFormat());
1123   }
1124   return StringInit::get(List->getRecordKeeper(), Result, Fmt);
1125 }
1126
1127 static const StringInit *interleaveIntList(const ListInit *List,
1128                                            const StringInit *Delim) {
1129   RecordKeeper &RK = List->getRecordKeeper();
1130   if (List->size() == 0)
1131     return StringInit::get(RK, "");
1132   const auto *Element = dyn_cast_or_null<IntInit>(
1133       List->getElement(0)->convertInitializerTo(IntRecTy::get(RK)));
1134   if (!Element)
1135     return nullptr;
1136   SmallString<80> Result(Element->getAsString());
1137
1138   for (unsigned I = 1, E = List->size(); I < E; ++I) {
1139     Result.append(Delim->getValue());
1140     const auto *Element = dyn_cast_or_null<IntInit>(
1141         List->getElement(I)->convertInitializerTo(IntRecTy::get(RK)));
1142     if (!Element)
1143       return nullptr;
1144     Result.append(Element->getAsString());
1145   }
1146   return StringInit::get(RK, Result);
1147 }
1148
1149 const Init *BinOpInit::getStrConcat(const Init *I0, const Init *I1) {
1150   // Shortcut for the common case of concatenating two strings.
1151   if (const auto *I0s = dyn_cast<StringInit>(I0))
1152     if (const auto *I1s = dyn_cast<StringInit>(I1))
1153       return ConcatStringInits(I0s, I1s);
1154   return BinOpInit::get(BinOpInit::STRCONCAT, I0, I1,
1155                         StringRecTy::get(I0->getRecordKeeper()));
1156 }
1157
1158 static const ListInit *ConcatListInits(const ListInit *LHS,
1159                                        const ListInit *RHS) {
1160   SmallVector<const Init *, 8> Args;
1161   llvm::append_range(Args, *LHS);
1162   llvm::append_range(Args, *RHS);
1163   return ListInit::get(Args, LHS->getElementType());
1164 }
1165
1166 const Init *BinOpInit::getListConcat(const TypedInit *LHS, const Init *RHS) {
1167   assert(isa<ListRecTy>(LHS->getType()) && "First arg must be a list");
1168
1169   // Shortcut for the common case of concatenating two lists.
1170   if (const auto *LHSList = dyn_cast<ListInit>(LHS))
1171     if (const auto *RHSList = dyn_cast<ListInit>(RHS))
1172       return ConcatListInits(LHSList, RHSList);
1173   return BinOpInit::get(BinOpInit::LISTCONCAT, LHS, RHS, LHS->getType());
1174 }
1175
1176 std::optional<bool> BinOpInit::CompareInit(unsigned Opc, const Init *LHS,
1177                                            const Init *RHS) const {
1178   // First see if we have two bit, bits, or int.
1179   const auto *LHSi = dyn_cast_or_null<IntInit>(
1180       LHS->convertInitializerTo(IntRecTy::get(getRecordKeeper())));
1181   const auto *RHSi = dyn_cast_or_null<IntInit>(
1182       RHS->convertInitializerTo(IntRecTy::get(getRecordKeeper())));
1183
1184   if (LHSi && RHSi) {
1185     bool Result;
1186     switch (Opc) {
1187     case EQ:
1188       Result = LHSi->getValue() == RHSi->getValue();
1189       break;
1190     case NE:
1191       Result = LHSi->getValue() != RHSi->getValue();
1192       break;
1193     case LE:
1194       Result = LHSi->getValue() <= RHSi->getValue();
1195       break;
1196     case LT:
1197       Result = LHSi->getValue() < RHSi->getValue();
1198       break;
1199     case GE:
1200       Result = LHSi->getValue() >= RHSi->getValue();
1201       break;
1202     case GT:
1203       Result = LHSi->getValue() > RHSi->getValue();
1204       break;
1205     default:
1206       llvm_unreachable("unhandled comparison");
1207     }
1208     return Result;
1209   }
1210
1211   // Next try strings.
1212   const auto *LHSs = dyn_cast<StringInit>(LHS);
1213   const auto *RHSs = dyn_cast<StringInit>(RHS);
1214
1215   if (LHSs && RHSs) {
1216     bool Result;
1217     switch (Opc) {
1218     case EQ:
1219       Result = LHSs->getValue() == RHSs->getValue();
1220       break;
1221     case NE:
1222       Result = LHSs->getValue() != RHSs->getValue();
1223       break;
1224     case LE:
1225       Result = LHSs->getValue() <= RHSs->getValue();
1226       break;
1227     case LT:
1228       Result = LHSs->getValue() < RHSs->getValue();
1229       break;
1230     case GE:
1231       Result = LHSs->getValue() >= RHSs->getValue();
1232       break;
1233     case GT:
1234       Result = LHSs->getValue() > RHSs->getValue();
1235       break;
1236     default:
1237       llvm_unreachable("unhandled comparison");
1238     }
1239     return Result;
1240   }
1241
1242   // Finally, !eq and !ne can be used with records.
1243   if (Opc == EQ || Opc == NE) {
1244     const auto *LHSd = dyn_cast<DefInit>(LHS);
1245     const auto *RHSd = dyn_cast<DefInit>(RHS);
1246     if (LHSd && RHSd)
1247       return (Opc == EQ) ? LHSd == RHSd : LHSd != RHSd;
1248   }
1249
1250   return std::nullopt;
1251 }
1252
1253 static std::optional<unsigned>
1254 getDagArgNoByKey(const DagInit *Dag, const Init *Key, std::string &Error) {
1255   // Accessor by index
1256   if (const auto *Idx = dyn_cast<IntInit>(Key)) {
1257     int64_t Pos = Idx->getValue();
1258     if (Pos < 0) {
1259       // The index is negative.
1260       Error =
1261           (Twine("index ") + std::to_string(Pos) + Twine(" is negative")).str();
1262       return std::nullopt;
1263     }
1264     if (Pos >= Dag->getNumArgs()) {
1265       // The index is out-of-range.
1266       Error = (Twine("index ") + std::to_string(Pos) +
1267                " is out of range (dag has " +
1268                std::to_string(Dag->getNumArgs()) + " arguments)")
1269                   .str();
1270       return std::nullopt;
1271     }
1272     return Pos;
1273   }
1274   assert(isa<StringInit>(Key));
1275   // Accessor by name
1276   const auto *Name = dyn_cast<StringInit>(Key);
1277   auto ArgNo = Dag->getArgNo(Name->getValue());
1278   if (!ArgNo) {
1279     // The key is not found.
1280     Error = (Twine("key '") + Name->getValue() + Twine("' is not found")).str();
1281     return std::nullopt;
1282   }
1283   return *ArgNo;
1284 }
1285
1286 const Init *BinOpInit::Fold(const Record *CurRec) const {
1287   switch (getOpcode()) {
1288   case CONCAT: {
1289     const auto *LHSs = dyn_cast<DagInit>(LHS);
1290     const auto *RHSs = dyn_cast<DagInit>(RHS);
1291     if (LHSs && RHSs) {
1292       const auto *LOp = dyn_cast<DefInit>(LHSs->getOperator());
1293       const auto *ROp = dyn_cast<DefInit>(RHSs->getOperator());
1294       if ((!LOp && !isa<UnsetInit>(LHSs->getOperator())) ||
1295           (!ROp && !isa<UnsetInit>(RHSs->getOperator())))
1296         break;
1297       if (LOp && ROp && LOp->getDef() != ROp->getDef()) {
1298         PrintFatalError(Twine("Concatenated Dag operators do not match: '") +
1299                         LHSs->getAsString() + "' vs. '" + RHSs->getAsString() +
1300                         "'");
1301       }
1302       const Init *Op = LOp ? LOp : ROp;
1303       if (!Op)
1304         Op = UnsetInit::get(getRecordKeeper());
1305
1306       SmallVector<const Init *, 8> Args;
1307       SmallVector<const StringInit *, 8> ArgNames;
1308       for (unsigned i = 0, e = LHSs->getNumArgs(); i != e; ++i) {
1309         Args.push_back(LHSs->getArg(i));
1310         ArgNames.push_back(LHSs->getArgName(i));
1311       }
1312       for (unsigned i = 0, e = RHSs->getNumArgs(); i != e; ++i) {
1313         Args.push_back(RHSs->getArg(i));
1314         ArgNames.push_back(RHSs->getArgName(i));
1315       }
1316       return DagInit::get(Op, nullptr, Args, ArgNames);
1317     }
1318     break;
1319   }
1320   case LISTCONCAT: {
1321     const auto *LHSs = dyn_cast<ListInit>(LHS);
1322     const auto *RHSs = dyn_cast<ListInit>(RHS);
1323     if (LHSs && RHSs) {
1324       SmallVector<const Init *, 8> Args;
1325       llvm::append_range(Args, *LHSs);
1326       llvm::append_range(Args, *RHSs);
1327       return ListInit::get(Args, LHSs->getElementType());
1328     }
1329     break;
1330   }
1331   case LISTSPLAT: {
1332     const auto *Value = dyn_cast<TypedInit>(LHS);
1333     const auto *Size = dyn_cast<IntInit>(RHS);
1334     if (Value && Size) {
1335       SmallVector<const Init *, 8> Args(Size->getValue(), Value);
1336       return ListInit::get(Args, Value->getType());
1337     }
1338     break;
1339   }
1340   case LISTREMOVE: {
1341     const auto *LHSs = dyn_cast<ListInit>(LHS);
1342     const auto *RHSs = dyn_cast<ListInit>(RHS);
1343     if (LHSs && RHSs) {
1344       SmallVector<const Init *, 8> Args;
1345       for (const Init *EltLHS : *LHSs) {
1346         bool Found = false;
1347         for (const Init *EltRHS : *RHSs) {
1348           if (std::optional<bool> Result = CompareInit(EQ, EltLHS, EltRHS)) {
1349             if (*Result) {
1350               Found = true;
1351               break;
1352             }
1353           }
1354         }
1355         if (!Found)
1356           Args.push_back(EltLHS);
1357       }
1358       return ListInit::get(Args, LHSs->getElementType());
1359     }
1360     break;
1361   }
1362   case LISTELEM: {
1363     const auto *TheList = dyn_cast<ListInit>(LHS);
1364     const auto *Idx = dyn_cast<IntInit>(RHS);
1365     if (!TheList || !Idx)
1366       break;
1367     auto i = Idx->getValue();
1368     if (i < 0 || i >= (ssize_t)TheList->size())
1369       break;
1370     return TheList->getElement(i);
1371   }
1372   case LISTSLICE: {
1373     const auto *TheList = dyn_cast<ListInit>(LHS);
1374     const auto *SliceIdxs = dyn_cast<ListInit>(RHS);
1375     if (!TheList || !SliceIdxs)
1376       break;
1377     SmallVector<const Init *, 8> Args;
1378     Args.reserve(SliceIdxs->size());
1379     for (auto *I : *SliceIdxs) {
1380       auto *II = dyn_cast<IntInit>(I);
1381       if (!II)
1382         goto unresolved;
1383       auto i = II->getValue();
1384       if (i < 0 || i >= (ssize_t)TheList->size())
1385         goto unresolved;
1386       Args.push_back(TheList->getElement(i));
1387     }
1388     return ListInit::get(Args, TheList->getElementType());
1389   }
1390   case RANGEC: {
1391     const auto *LHSi = dyn_cast<IntInit>(LHS);
1392     const auto *RHSi = dyn_cast<IntInit>(RHS);
1393     if (!LHSi || !RHSi)
1394       break;
1395
1396     auto Start = LHSi->getValue();
1397     auto End = RHSi->getValue();
1398     SmallVector<const Init *, 8> Args;
1399     if (getOpcode() == RANGEC) {
1400       // Closed interval
1401       if (Start <= End) {
1402         // Ascending order
1403         Args.reserve(End - Start + 1);
1404         for (auto i = Start; i <= End; ++i)
1405           Args.push_back(IntInit::get(getRecordKeeper(), i));
1406       } else {
1407         // Descending order
1408         Args.reserve(Start - End + 1);
1409         for (auto i = Start; i >= End; --i)
1410           Args.push_back(IntInit::get(getRecordKeeper(), i));
1411       }
1412     } else if (Start < End) {
1413       // Half-open interval (excludes `End`)
1414       Args.reserve(End - Start);
1415       for (auto i = Start; i < End; ++i)
1416         Args.push_back(IntInit::get(getRecordKeeper(), i));
1417     } else {
1418       // Empty set
1419     }
1420     return ListInit::get(Args, LHSi->getType());
1421   }
1422   case STRCONCAT: {
1423     const auto *LHSs = dyn_cast<StringInit>(LHS);
1424     const auto *RHSs = dyn_cast<StringInit>(RHS);
1425     if (LHSs && RHSs)
1426       return ConcatStringInits(LHSs, RHSs);
1427     break;
1428   }
1429   case INTERLEAVE: {
1430     const auto *List = dyn_cast<ListInit>(LHS);
1431     const auto *Delim = dyn_cast<StringInit>(RHS);
1432     if (List && Delim) {
1433       const StringInit *Result;
1434       if (isa<StringRecTy>(List->getElementType()))
1435         Result = interleaveStringList(List, Delim);
1436       else
1437         Result = interleaveIntList(List, Delim);
1438       if (Result)
1439         return Result;
1440     }
1441     break;
1442   }
1443   case EQ:
1444   case NE:
1445   case LE:
1446   case LT:
1447   case GE:
1448   case GT: {
1449     if (std::optional<bool> Result = CompareInit(getOpcode(), LHS, RHS))
1450       return BitInit::get(getRecordKeeper(), *Result);
1451     break;
1452   }
1453   case GETDAGARG: {
1454     const auto *Dag = dyn_cast<DagInit>(LHS);
1455     if (Dag && isa<IntInit, StringInit>(RHS)) {
1456       std::string Error;
1457       auto ArgNo = getDagArgNoByKey(Dag, RHS, Error);
1458       if (!ArgNo)
1459         PrintFatalError(CurRec->getLoc(), "!getdagarg " + Error);
1460
1461       assert(*ArgNo < Dag->getNumArgs());
1462
1463       const Init *Arg = Dag->getArg(*ArgNo);
1464       if (const auto *TI = dyn_cast<TypedInit>(Arg))
1465         if (!TI->getType()->typeIsConvertibleTo(getType()))
1466           return UnsetInit::get(Dag->getRecordKeeper());
1467       return Arg;
1468     }
1469     break;
1470   }
1471   case GETDAGNAME: {
1472     const auto *Dag = dyn_cast<DagInit>(LHS);
1473     const auto *Idx = dyn_cast<IntInit>(RHS);
1474     if (Dag && Idx) {
1475       int64_t Pos = Idx->getValue();
1476       if (Pos < 0 || Pos >= Dag->getNumArgs()) {
1477         // The index is out-of-range.
1478         PrintError(CurRec->getLoc(),
1479                    Twine("!getdagname index is out of range 0...") +
1480                        std::to_string(Dag->getNumArgs() - 1) + ": " +
1481                        std::to_string(Pos));
1482       }
1483       const Init *ArgName = Dag->getArgName(Pos);
1484       if (!ArgName)
1485         return UnsetInit::get(getRecordKeeper());
1486       return ArgName;
1487     }
1488     break;
1489   }
1490   case SETDAGOP: {
1491     const auto *Dag = dyn_cast<DagInit>(LHS);
1492     const auto *Op = dyn_cast<DefInit>(RHS);
1493     if (Dag && Op) {
1494       SmallVector<const Init *, 8> Args;
1495       SmallVector<const StringInit *, 8> ArgNames;
1496       for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) {
1497         Args.push_back(Dag->getArg(i));
1498         ArgNames.push_back(Dag->getArgName(i));
1499       }
1500       return DagInit::get(Op, nullptr, Args, ArgNames);
1501     }
1502     break;
1503   }
1504   case ADD:
1505   case SUB:
1506   case MUL:
1507   case DIV:
1508   case AND:
1509   case OR:
1510   case XOR:
1511   case SHL:
1512   case SRA:
1513   case SRL: {
1514     const auto *LHSi = dyn_cast_or_null<IntInit>(
1515         LHS->convertInitializerTo(IntRecTy::get(getRecordKeeper())));
1516     const auto *RHSi = dyn_cast_or_null<IntInit>(
1517         RHS->convertInitializerTo(IntRecTy::get(getRecordKeeper())));
1518     if (LHSi && RHSi) {
1519       int64_t LHSv = LHSi->getValue(), RHSv = RHSi->getValue();
1520       int64_t Result;
1521       switch (getOpcode()) {
1522       default: llvm_unreachable("Bad opcode!");
1523       case ADD: Result = LHSv + RHSv; break;
1524       case SUB: Result = LHSv - RHSv; break;
1525       case MUL: Result = LHSv * RHSv; break;
1526       case DIV:
1527         if (RHSv == 0)
1528           PrintFatalError(CurRec->getLoc(),
1529                           "Illegal operation: division by zero");
1530         else if (LHSv == INT64_MIN && RHSv == -1)
1531           PrintFatalError(CurRec->getLoc(),
1532                           "Illegal operation: INT64_MIN / -1");
1533         else
1534           Result = LHSv / RHSv;
1535         break;
1536       case AND: Result = LHSv & RHSv; break;
1537       case OR:  Result = LHSv | RHSv; break;
1538       case XOR: Result = LHSv ^ RHSv; break;
1539       case SHL: Result = (uint64_t)LHSv << (uint64_t)RHSv; break;
1540       case SRA: Result = LHSv >> RHSv; break;
1541       case SRL: Result = (uint64_t)LHSv >> (uint64_t)RHSv; break;
1542       }
1543       return IntInit::get(getRecordKeeper(), Result);
1544     }
1545     break;
1546   }
1547   }
1548 unresolved:
1549   return this;
1550 }
1551
1552 const Init *BinOpInit::resolveReferences(Resolver &R) const {
1553   const Init *lhs = LHS->resolveReferences(R);
1554   const Init *rhs = RHS->resolveReferences(R);
1555
1556   unsigned Opc = getOpcode();
1557   if (Opc == AND || Opc == OR) {
1558     // Short-circuit. Regardless whether this is a logical or bitwise
1559     // AND/OR.
1560     // Ideally we could also short-circuit `!or(true, ...)`, but it's
1561     // difficult to do it right without knowing if rest of the operands
1562     // are all `bit` or not. Therefore, we're only implementing a relatively
1563     // limited version of short-circuit against all ones (`true` is casted
1564     // to 1 rather than all ones before we evaluate `!or`).
1565     if (const auto *LHSi = dyn_cast_or_null<IntInit>(
1566             lhs->convertInitializerTo(IntRecTy::get(getRecordKeeper())))) {
1567       if ((Opc == AND && !LHSi->getValue()) ||
1568           (Opc == OR && LHSi->getValue() == -1))
1569         return LHSi;
1570     }
1571   }
1572
1573   if (LHS != lhs || RHS != rhs)
1574     return (BinOpInit::get(getOpcode(), lhs, rhs, getType()))
1575         ->Fold(R.getCurrentRecord());
1576   return this;
1577 }
1578
1579 std::string BinOpInit::getAsString() const {
1580   std::string Result;
1581   switch (getOpcode()) {
1582   case LISTELEM:
1583   case LISTSLICE:
1584     return LHS->getAsString() + "[" + RHS->getAsString() + "]";
1585   case RANGEC:
1586     return LHS->getAsString() + "..." + RHS->getAsString();
1587   case CONCAT: Result = "!con"; break;
1588   case ADD: Result = "!add"; break;
1589   case SUB: Result = "!sub"; break;
1590   case MUL: Result = "!mul"; break;
1591   case DIV: Result = "!div"; break;
1592   case AND: Result = "!and"; break;
1593   case OR: Result = "!or"; break;
1594   case XOR: Result = "!xor"; break;
1595   case SHL: Result = "!shl"; break;
1596   case SRA: Result = "!sra"; break;
1597   case SRL: Result = "!srl"; break;
1598   case EQ: Result = "!eq"; break;
1599   case NE: Result = "!ne"; break;
1600   case LE: Result = "!le"; break;
1601   case LT: Result = "!lt"; break;
1602   case GE: Result = "!ge"; break;
1603   case GT: Result = "!gt"; break;
1604   case LISTCONCAT: Result = "!listconcat"; break;
1605   case LISTSPLAT: Result = "!listsplat"; break;
1606   case LISTREMOVE:
1607     Result = "!listremove";
1608     break;
1609   case STRCONCAT: Result = "!strconcat"; break;
1610   case INTERLEAVE: Result = "!interleave"; break;
1611   case SETDAGOP: Result = "!setdagop"; break;
1612   case GETDAGARG:
1613     Result = "!getdagarg<" + getType()->getAsString() + ">";
1614     break;
1615   case GETDAGNAME:
1616     Result = "!getdagname";
1617     break;
1618   }
1619   return Result + "(" + LHS->getAsString() + ", " + RHS->getAsString() + ")";
1620 }
1621
1622 static void ProfileTernOpInit(FoldingSetNodeID &ID, unsigned Opcode,
1623                               const Init *LHS, const Init *MHS, const Init *RHS,
1624                               const RecTy *Type) {
1625   ID.AddInteger(Opcode);
1626   ID.AddPointer(LHS);
1627   ID.AddPointer(MHS);
1628   ID.AddPointer(RHS);
1629   ID.AddPointer(Type);
1630 }
1631
1632 const TernOpInit *TernOpInit::get(TernaryOp Opc, const Init *LHS,
1633                                   const Init *MHS, const Init *RHS,
1634                                   const RecTy *Type) {
1635   FoldingSetNodeID ID;
1636   ProfileTernOpInit(ID, Opc, LHS, MHS, RHS, Type);
1637
1638   detail::RecordKeeperImpl &RK = LHS->getRecordKeeper().getImpl();
1639   void *IP = nullptr;
1640   if (TernOpInit *I = RK.TheTernOpInitPool.FindNodeOrInsertPos(ID, IP))
1641     return I;
1642
1643   TernOpInit *I = new (RK.Allocator) TernOpInit(Opc, LHS, MHS, RHS, Type);
1644   RK.TheTernOpInitPool.InsertNode(I, IP);
1645   return I;
1646 }
1647
1648 void TernOpInit::Profile(FoldingSetNodeID &ID) const {
1649   ProfileTernOpInit(ID, getOpcode(), getLHS(), getMHS(), getRHS(), getType());
1650 }
1651
1652 static const Init *ItemApply(const Init *LHS, const Init *MHSe, const Init *RHS,
1653                              const Record *CurRec) {
1654   MapResolver R(CurRec);
1655   R.set(LHS, MHSe);
1656   return RHS->resolveReferences(R);
1657 }
1658
1659 static const Init *ForeachDagApply(const Init *LHS, const DagInit *MHSd,
1660                                    const Init *RHS, const Record *CurRec) {
1661   bool Change = false;
1662   const Init *Val = ItemApply(LHS, MHSd->getOperator(), RHS, CurRec);
1663   if (Val != MHSd->getOperator())
1664     Change = true;
1665
1666   SmallVector<std::pair<const Init *, const StringInit *>, 8> NewArgs;
1667   for (unsigned int i = 0; i < MHSd->getNumArgs(); ++i) {
1668     const Init *Arg = MHSd->getArg(i);
1669     const Init *NewArg;
1670     const StringInit *ArgName = MHSd->getArgName(i);
1671
1672     if (const auto *Argd = dyn_cast<DagInit>(Arg))
1673       NewArg = ForeachDagApply(LHS, Argd, RHS, CurRec);
1674     else
1675       NewArg = ItemApply(LHS, Arg, RHS, CurRec);
1676
1677     NewArgs.push_back(std::make_pair(NewArg, ArgName));
1678     if (Arg != NewArg)
1679       Change = true;
1680   }
1681
1682   if (Change)
1683     return DagInit::get(Val, nullptr, NewArgs);
1684   return MHSd;
1685 }
1686
1687 // Applies RHS to all elements of MHS, using LHS as a temp variable.
1688 static const Init *ForeachHelper(const Init *LHS, const Init *MHS,
1689                                  const Init *RHS, const RecTy *Type,
1690                                  const Record *CurRec) {
1691   if (const auto *MHSd = dyn_cast<DagInit>(MHS))
1692     return ForeachDagApply(LHS, MHSd, RHS, CurRec);
1693
1694   if (const auto *MHSl = dyn_cast<ListInit>(MHS)) {
1695     SmallVector<const Init *, 8> NewList(MHSl->begin(), MHSl->end());
1696
1697     for (const Init *&Item : NewList) {
1698       const Init *NewItem = ItemApply(LHS, Item, RHS, CurRec);
1699       if (NewItem != Item)
1700         Item = NewItem;
1701     }
1702     return ListInit::get(NewList, cast<ListRecTy>(Type)->getElementType());
1703   }
1704
1705   return nullptr;
1706 }
1707
1708 // Evaluates RHS for all elements of MHS, using LHS as a temp variable.
1709 // Creates a new list with the elements that evaluated to true.
1710 static const Init *FilterHelper(const Init *LHS, const Init *MHS,
1711                                 const Init *RHS, const RecTy *Type,
1712                                 const Record *CurRec) {
1713   if (const auto *MHSl = dyn_cast<ListInit>(MHS)) {
1714     SmallVector<const Init *, 8> NewList;
1715
1716     for (const Init *Item : MHSl->getValues()) {
1717       const Init *Include = ItemApply(LHS, Item, RHS, CurRec);
1718       if (!Include)
1719         return nullptr;
1720       if (const auto *IncludeInt =
1721               dyn_cast_or_null<IntInit>(Include->convertInitializerTo(
1722                   IntRecTy::get(LHS->getRecordKeeper())))) {
1723         if (IncludeInt->getValue())
1724           NewList.push_back(Item);
1725       } else {
1726         return nullptr;
1727       }
1728     }
1729     return ListInit::get(NewList, cast<ListRecTy>(Type)->getElementType());
1730   }
1731
1732   return nullptr;
1733 }
1734
1735 const Init *TernOpInit::Fold(const Record *CurRec) const {
1736   RecordKeeper &RK = getRecordKeeper();
1737   switch (getOpcode()) {
1738   case SUBST: {
1739     const auto *LHSd = dyn_cast<DefInit>(LHS);
1740     const auto *LHSv = dyn_cast<VarInit>(LHS);
1741     const auto *LHSs = dyn_cast<StringInit>(LHS);
1742
1743     const auto *MHSd = dyn_cast<DefInit>(MHS);
1744     const auto *MHSv = dyn_cast<VarInit>(MHS);
1745     const auto *MHSs = dyn_cast<StringInit>(MHS);
1746
1747     const auto *RHSd = dyn_cast<DefInit>(RHS);
1748     const auto *RHSv = dyn_cast<VarInit>(RHS);
1749     const auto *RHSs = dyn_cast<StringInit>(RHS);
1750
1751     if (LHSd && MHSd && RHSd) {
1752       const Record *Val = RHSd->getDef();
1753       if (LHSd->getAsString() == RHSd->getAsString())
1754         Val = MHSd->getDef();
1755       return Val->getDefInit();
1756     }
1757     if (LHSv && MHSv && RHSv) {
1758       std::string Val = std::string(RHSv->getName());
1759       if (LHSv->getAsString() == RHSv->getAsString())
1760         Val = std::string(MHSv->getName());
1761       return VarInit::get(Val, getType());
1762     }
1763     if (LHSs && MHSs && RHSs) {
1764       std::string Val = std::string(RHSs->getValue());
1765
1766       std::string::size_type found;
1767       std::string::size_type idx = 0;
1768       while (true) {
1769         found = Val.find(std::string(LHSs->getValue()), idx);
1770         if (found == std::string::npos)
1771           break;
1772         Val.replace(found, LHSs->getValue().size(),
1773                     std::string(MHSs->getValue()));
1774         idx = found + MHSs->getValue().size();
1775       }
1776
1777       return StringInit::get(RK, Val);
1778     }
1779     break;
1780   }
1781
1782   case FOREACH: {
1783     if (const Init *Result = ForeachHelper(LHS, MHS, RHS, getType(), CurRec))
1784       return Result;
1785     break;
1786   }
1787
1788   case FILTER: {
1789     if (const Init *Result = FilterHelper(LHS, MHS, RHS, getType(), CurRec))
1790       return Result;
1791     break;
1792   }
1793
1794   case IF: {
1795     if (const auto *LHSi = dyn_cast_or_null<IntInit>(
1796             LHS->convertInitializerTo(IntRecTy::get(RK)))) {
1797       if (LHSi->getValue())
1798         return MHS;
1799       return RHS;
1800     }
1801     break;
1802   }
1803
1804   case DAG: {
1805     const auto *MHSl = dyn_cast<ListInit>(MHS);
1806     const auto *RHSl = dyn_cast<ListInit>(RHS);
1807     bool MHSok = MHSl || isa<UnsetInit>(MHS);
1808     bool RHSok = RHSl || isa<UnsetInit>(RHS);
1809
1810     if (isa<UnsetInit>(MHS) && isa<UnsetInit>(RHS))
1811       break; // Typically prevented by the parser, but might happen with template args
1812
1813     if (MHSok && RHSok && (!MHSl || !RHSl || MHSl->size() == RHSl->size())) {
1814       SmallVector<std::pair<const Init *, const StringInit *>, 8> Children;
1815       unsigned Size = MHSl ? MHSl->size() : RHSl->size();
1816       for (unsigned i = 0; i != Size; ++i) {
1817         const Init *Node = MHSl ? MHSl->getElement(i) : UnsetInit::get(RK);
1818         const Init *Name = RHSl ? RHSl->getElement(i) : UnsetInit::get(RK);
1819         if (!isa<StringInit>(Name) && !isa<UnsetInit>(Name))
1820           return this;
1821         Children.emplace_back(Node, dyn_cast<StringInit>(Name));
1822       }
1823       return DagInit::get(LHS, nullptr, Children);
1824     }
1825     break;
1826   }
1827
1828   case RANGE: {
1829     const auto *LHSi = dyn_cast<IntInit>(LHS);
1830     const auto *MHSi = dyn_cast<IntInit>(MHS);
1831     const auto *RHSi = dyn_cast<IntInit>(RHS);
1832     if (!LHSi || !MHSi || !RHSi)
1833       break;
1834
1835     auto Start = LHSi->getValue();
1836     auto End = MHSi->getValue();
1837     auto Step = RHSi->getValue();
1838     if (Step == 0)
1839       PrintError(CurRec->getLoc(), "Step of !range can't be 0");
1840
1841     SmallVector<const Init *, 8> Args;
1842     if (Start < End && Step > 0) {
1843       Args.reserve((End - Start) / Step);
1844       for (auto I = Start; I < End; I += Step)
1845         Args.push_back(IntInit::get(getRecordKeeper(), I));
1846     } else if (Start > End && Step < 0) {
1847       Args.reserve((Start - End) / -Step);
1848       for (auto I = Start; I > End; I += Step)
1849         Args.push_back(IntInit::get(getRecordKeeper(), I));
1850     } else {
1851       // Empty set
1852     }
1853     return ListInit::get(Args, LHSi->getType());
1854   }
1855
1856   case SUBSTR: {
1857     const auto *LHSs = dyn_cast<StringInit>(LHS);
1858     const auto *MHSi = dyn_cast<IntInit>(MHS);
1859     const auto *RHSi = dyn_cast<IntInit>(RHS);
1860     if (LHSs && MHSi && RHSi) {
1861       int64_t StringSize = LHSs->getValue().size();
1862       int64_t Start = MHSi->getValue();
1863       int64_t Length = RHSi->getValue();
1864       if (Start < 0 || Start > StringSize)
1865         PrintError(CurRec->getLoc(),
1866                    Twine("!substr start position is out of range 0...") +
1867                        std::to_string(StringSize) + ": " +
1868                        std::to_string(Start));
1869       if (Length < 0)
1870         PrintError(CurRec->getLoc(), "!substr length must be nonnegative");
1871       return StringInit::get(RK, LHSs->getValue().substr(Start, Length),
1872                              LHSs->getFormat());
1873     }
1874     break;
1875   }
1876
1877   case FIND: {
1878     const auto *LHSs = dyn_cast<StringInit>(LHS);
1879     const auto *MHSs = dyn_cast<StringInit>(MHS);
1880     const auto *RHSi = dyn_cast<IntInit>(RHS);
1881     if (LHSs && MHSs && RHSi) {
1882       int64_t SourceSize = LHSs->getValue().size();
1883       int64_t Start = RHSi->getValue();
1884       if (Start < 0 || Start > SourceSize)
1885         PrintError(CurRec->getLoc(),
1886                    Twine("!find start position is out of range 0...") +
1887                        std::to_string(SourceSize) + ": " +
1888                        std::to_string(Start));
1889       auto I = LHSs->getValue().find(MHSs->getValue(), Start);
1890       if (I == std::string::npos)
1891         return IntInit::get(RK, -1);
1892       return IntInit::get(RK, I);
1893     }
1894     break;
1895   }
1896
1897   case SETDAGARG: {
1898     const auto *Dag = dyn_cast<DagInit>(LHS);
1899     if (Dag && isa<IntInit, StringInit>(MHS)) {
1900       std::string Error;
1901       auto ArgNo = getDagArgNoByKey(Dag, MHS, Error);
1902       if (!ArgNo)
1903         PrintFatalError(CurRec->getLoc(), "!setdagarg " + Error);
1904
1905       assert(*ArgNo < Dag->getNumArgs());
1906
1907       SmallVector<const Init *, 8> Args(Dag->getArgs());
1908       SmallVector<const StringInit *, 8> Names(Dag->getArgNames());
1909       Args[*ArgNo] = RHS;
1910       return DagInit::get(Dag->getOperator(), Dag->getName(), Args, Names);
1911     }
1912     break;
1913   }
1914
1915   case SETDAGNAME: {
1916     const auto *Dag = dyn_cast<DagInit>(LHS);
1917     if (Dag && isa<IntInit, StringInit>(MHS)) {
1918       std::string Error;
1919       auto ArgNo = getDagArgNoByKey(Dag, MHS, Error);
1920       if (!ArgNo)
1921         PrintFatalError(CurRec->getLoc(), "!setdagname " + Error);
1922
1923       assert(*ArgNo < Dag->getNumArgs());
1924
1925       SmallVector<const Init *, 8> Args(Dag->getArgs());
1926       SmallVector<const StringInit *, 8> Names(Dag->getArgNames());
1927       Names[*ArgNo] = dyn_cast<StringInit>(RHS);
1928       return DagInit::get(Dag->getOperator(), Dag->getName(), Args, Names);
1929     }
1930     break;
1931   }
1932   }
1933
1934   return this;
1935 }
1936
1937 const Init *TernOpInit::resolveReferences(Resolver &R) const {
1938   const Init *lhs = LHS->resolveReferences(R);
1939
1940   if (getOpcode() == IF && lhs != LHS) {
1941     if (const auto *Value = dyn_cast_or_null<IntInit>(
1942             lhs->convertInitializerTo(IntRecTy::get(getRecordKeeper())))) {
1943       // Short-circuit
1944       if (Value->getValue())
1945         return MHS->resolveReferences(R);
1946       return RHS->resolveReferences(R);
1947     }
1948   }
1949
1950   const Init *mhs = MHS->resolveReferences(R);
1951   const Init *rhs;
1952
1953   if (getOpcode() == FOREACH || getOpcode() == FILTER) {
1954     ShadowResolver SR(R);
1955     SR.addShadow(lhs);
1956     rhs = RHS->resolveReferences(SR);
1957   } else {
1958     rhs = RHS->resolveReferences(R);
1959   }
1960
1961   if (LHS != lhs || MHS != mhs || RHS != rhs)
1962     return (TernOpInit::get(getOpcode(), lhs, mhs, rhs, getType()))
1963         ->Fold(R.getCurrentRecord());
1964   return this;
1965 }
1966
1967 std::string TernOpInit::getAsString() const {
1968   std::string Result;
1969   bool UnquotedLHS = false;
1970   switch (getOpcode()) {
1971   case DAG: Result = "!dag"; break;
1972   case FILTER: Result = "!filter"; UnquotedLHS = true; break;
1973   case FOREACH: Result = "!foreach"; UnquotedLHS = true; break;
1974   case IF: Result = "!if"; break;
1975   case RANGE:
1976     Result = "!range";
1977     break;
1978   case SUBST: Result = "!subst"; break;
1979   case SUBSTR: Result = "!substr"; break;
1980   case FIND: Result = "!find"; break;
1981   case SETDAGARG:
1982     Result = "!setdagarg";
1983     break;
1984   case SETDAGNAME:
1985     Result = "!setdagname";
1986     break;
1987   }
1988   return (Result + "(" +
1989           (UnquotedLHS ? LHS->getAsUnquotedString() : LHS->getAsString()) +
1990           ", " + MHS->getAsString() + ", " + RHS->getAsString() + ")");
1991 }
1992
1993 static void ProfileFoldOpInit(FoldingSetNodeID &ID, const Init *Start,
1994                               const Init *List, const Init *A, const Init *B,
1995                               const Init *Expr, const RecTy *Type) {
1996   ID.AddPointer(Start);
1997   ID.AddPointer(List);
1998   ID.AddPointer(A);
1999   ID.AddPointer(B);
2000   ID.AddPointer(Expr);
2001   ID.AddPointer(Type);
2002 }
2003
2004 const FoldOpInit *FoldOpInit::get(const Init *Start, const Init *List,
2005                                   const Init *A, const Init *B,
2006                                   const Init *Expr, const RecTy *Type) {
2007   FoldingSetNodeID ID;
2008   ProfileFoldOpInit(ID, Start, List, A, B, Expr, Type);
2009
2010   detail::RecordKeeperImpl &RK = Start->getRecordKeeper().getImpl();
2011   void *IP = nullptr;
2012   if (const FoldOpInit *I = RK.TheFoldOpInitPool.FindNodeOrInsertPos(ID, IP))
2013     return I;
2014
2015   FoldOpInit *I = new (RK.Allocator) FoldOpInit(Start, List, A, B, Expr, Type);
2016   RK.TheFoldOpInitPool.InsertNode(I, IP);
2017   return I;
2018 }
2019
2020 void FoldOpInit::Profile(FoldingSetNodeID &ID) const {
2021   ProfileFoldOpInit(ID, Start, List, A, B, Expr, getType());
2022 }
2023
2024 const Init *FoldOpInit::Fold(const Record *CurRec) const {
2025   if (const auto *LI = dyn_cast<ListInit>(List)) {
2026     const Init *Accum = Start;
2027     for (const Init *Elt : *LI) {
2028       MapResolver R(CurRec);
2029       R.set(A, Accum);
2030       R.set(B, Elt);
2031       Accum = Expr->resolveReferences(R);
2032     }
2033     return Accum;
2034   }
2035   return this;
2036 }
2037
2038 const Init *FoldOpInit::resolveReferences(Resolver &R) const {
2039   const Init *NewStart = Start->resolveReferences(R);
2040   const Init *NewList = List->resolveReferences(R);
2041   ShadowResolver SR(R);
2042   SR.addShadow(A);
2043   SR.addShadow(B);
2044   const Init *NewExpr = Expr->resolveReferences(SR);
2045
2046   if (Start == NewStart && List == NewList && Expr == NewExpr)
2047     return this;
2048
2049   return get(NewStart, NewList, A, B, NewExpr, getType())
2050       ->Fold(R.getCurrentRecord());
2051 }
2052
2053 const Init *FoldOpInit::getBit(unsigned Bit) const {
2054   return VarBitInit::get(this, Bit);
2055 }
2056
2057 std::string FoldOpInit::getAsString() const {
2058   return (Twine("!foldl(") + Start->getAsString() + ", " + List->getAsString() +
2059           ", " + A->getAsUnquotedString() + ", " + B->getAsUnquotedString() +
2060           ", " + Expr->getAsString() + ")")
2061       .str();
2062 }
2063
2064 static void ProfileIsAOpInit(FoldingSetNodeID &ID, const RecTy *CheckType,
2065                              const Init *Expr) {
2066   ID.AddPointer(CheckType);
2067   ID.AddPointer(Expr);
2068 }
2069
2070 const IsAOpInit *IsAOpInit::get(const RecTy *CheckType, const Init *Expr) {
2071
2072   FoldingSetNodeID ID;
2073   ProfileIsAOpInit(ID, CheckType, Expr);
2074
2075   detail::RecordKeeperImpl &RK = Expr->getRecordKeeper().getImpl();
2076   void *IP = nullptr;
2077   if (const IsAOpInit *I = RK.TheIsAOpInitPool.FindNodeOrInsertPos(ID, IP))
2078     return I;
2079
2080   IsAOpInit *I = new (RK.Allocator) IsAOpInit(CheckType, Expr);
2081   RK.TheIsAOpInitPool.InsertNode(I, IP);
2082   return I;
2083 }
2084
2085 void IsAOpInit::Profile(FoldingSetNodeID &ID) const {
2086   ProfileIsAOpInit(ID, CheckType, Expr);
2087 }
2088
2089 const Init *IsAOpInit::Fold() const {
2090   if (const auto *TI = dyn_cast<TypedInit>(Expr)) {
2091     // Is the expression type known to be (a subclass of) the desired type?
2092     if (TI->getType()->typeIsConvertibleTo(CheckType))
2093       return IntInit::get(getRecordKeeper(), 1);
2094
2095     if (isa<RecordRecTy>(CheckType)) {
2096       // If the target type is not a subclass of the expression type, or if
2097       // the expression has fully resolved to a record, we know that it can't
2098       // be of the required type.
2099       if (!CheckType->typeIsConvertibleTo(TI->getType()) || isa<DefInit>(Expr))
2100         return IntInit::get(getRecordKeeper(), 0);
2101     } else {
2102       // We treat non-record types as not castable.
2103       return IntInit::get(getRecordKeeper(), 0);
2104     }
2105   }
2106   return this;
2107 }
2108
2109 const Init *IsAOpInit::resolveReferences(Resolver &R) const {
2110   const Init *NewExpr = Expr->resolveReferences(R);
2111   if (Expr != NewExpr)
2112     return get(CheckType, NewExpr)->Fold();
2113   return this;
2114 }
2115
2116 const Init *IsAOpInit::getBit(unsigned Bit) const {
2117   return VarBitInit::get(this, Bit);
2118 }
2119
2120 std::string IsAOpInit::getAsString() const {
2121   return (Twine("!isa<") + CheckType->getAsString() + ">(" +
2122           Expr->getAsString() + ")")
2123       .str();
2124 }
2125
2126 static void ProfileExistsOpInit(FoldingSetNodeID &ID, const RecTy *CheckType,
2127                                 const Init *Expr) {
2128   ID.AddPointer(CheckType);
2129   ID.AddPointer(Expr);
2130 }
2131
2132 const ExistsOpInit *ExistsOpInit::get(const RecTy *CheckType,
2133                                       const Init *Expr) {
2134   FoldingSetNodeID ID;
2135   ProfileExistsOpInit(ID, CheckType, Expr);
2136
2137   detail::RecordKeeperImpl &RK = Expr->getRecordKeeper().getImpl();
2138   void *IP = nullptr;
2139   if (const ExistsOpInit *I =
2140           RK.TheExistsOpInitPool.FindNodeOrInsertPos(ID, IP))
2141     return I;
2142
2143   ExistsOpInit *I = new (RK.Allocator) ExistsOpInit(CheckType, Expr);
2144   RK.TheExistsOpInitPool.InsertNode(I, IP);
2145   return I;
2146 }
2147
2148 void ExistsOpInit::Profile(FoldingSetNodeID &ID) const {
2149   ProfileExistsOpInit(ID, CheckType, Expr);
2150 }
2151
2152 const Init *ExistsOpInit::Fold(const Record *CurRec, bool IsFinal) const {
2153   if (const auto *Name = dyn_cast<StringInit>(Expr)) {
2154     // Look up all defined records to see if we can find one.
2155     const Record *D = CheckType->getRecordKeeper().getDef(Name->getValue());
2156     if (D) {
2157       // Check if types are compatible.
2158       return IntInit::get(getRecordKeeper(),
2159                           D->getDefInit()->getType()->typeIsA(CheckType));
2160     }
2161
2162     if (CurRec) {
2163       // Self-references are allowed, but their resolution is delayed until
2164       // the final resolve to ensure that we get the correct type for them.
2165       auto *Anonymous = dyn_cast<AnonymousNameInit>(CurRec->getNameInit());
2166       if (Name == CurRec->getNameInit() ||
2167           (Anonymous && Name == Anonymous->getNameInit())) {
2168         if (!IsFinal)
2169           return this;
2170
2171         // No doubt that there exists a record, so we should check if types are
2172         // compatible.
2173         return IntInit::get(getRecordKeeper(),
2174                             CurRec->getType()->typeIsA(CheckType));
2175       }
2176     }
2177
2178     if (IsFinal)
2179       return IntInit::get(getRecordKeeper(), 0);
2180   }
2181   return this;
2182 }
2183
2184 const Init *ExistsOpInit::resolveReferences(Resolver &R) const {
2185   const Init *NewExpr = Expr->resolveReferences(R);
2186   if (Expr != NewExpr || R.isFinal())
2187     return get(CheckType, NewExpr)->Fold(R.getCurrentRecord(), R.isFinal());
2188   return this;
2189 }
2190
2191 const Init *ExistsOpInit::getBit(unsigned Bit) const {
2192   return VarBitInit::get(this, Bit);
2193 }
2194
2195 std::string ExistsOpInit::getAsString() const {
2196   return (Twine("!exists<") + CheckType->getAsString() + ">(" +
2197           Expr->getAsString() + ")")
2198       .str();
2199 }
2200
2201 const RecTy *TypedInit::getFieldType(const StringInit *FieldName) const {
2202   if (const auto *RecordType = dyn_cast<RecordRecTy>(getType())) {
2203     for (const Record *Rec : RecordType->getClasses()) {
2204       if (const RecordVal *Field = Rec->getValue(FieldName))
2205         return Field->getType();
2206     }
2207   }
2208   return nullptr;
2209 }
2210
2211 const Init *TypedInit::convertInitializerTo(const RecTy *Ty) const {
2212   if (getType() == Ty || getType()->typeIsA(Ty))
2213     return this;
2214
2215   if (isa<BitRecTy>(getType()) && isa<BitsRecTy>(Ty) &&
2216       cast<BitsRecTy>(Ty)->getNumBits() == 1)
2217     return BitsInit::get(getRecordKeeper(), {this});
2218
2219   return nullptr;
2220 }
2221
2222 const Init *
2223 TypedInit::convertInitializerBitRange(ArrayRef<unsigned> Bits) const {
2224   const auto *T = dyn_cast<BitsRecTy>(getType());
2225   if (!T) return nullptr;  // Cannot subscript a non-bits variable.
2226   unsigned NumBits = T->getNumBits();
2227
2228   SmallVector<const Init *, 16> NewBits;
2229   NewBits.reserve(Bits.size());
2230   for (unsigned Bit : Bits) {
2231     if (Bit >= NumBits)
2232       return nullptr;
2233
2234     NewBits.push_back(VarBitInit::get(this, Bit));
2235   }
2236   return BitsInit::get(getRecordKeeper(), NewBits);
2237 }
2238
2239 const Init *TypedInit::getCastTo(const RecTy *Ty) const {
2240   // Handle the common case quickly
2241   if (getType() == Ty || getType()->typeIsA(Ty))
2242     return this;
2243
2244   if (const Init *Converted = convertInitializerTo(Ty)) {
2245     assert(!isa<TypedInit>(Converted) ||
2246            cast<TypedInit>(Converted)->getType()->typeIsA(Ty));
2247     return Converted;
2248   }
2249
2250   if (!getType()->typeIsConvertibleTo(Ty))
2251     return nullptr;
2252
2253   return UnOpInit::get(UnOpInit::CAST, this, Ty)->Fold(nullptr);
2254 }
2255
2256 const VarInit *VarInit::get(StringRef VN, const RecTy *T) {
2257   const Init *Value = StringInit::get(T->getRecordKeeper(), VN);
2258   return VarInit::get(Value, T);
2259 }
2260
2261 const VarInit *VarInit::get(const Init *VN, const RecTy *T) {
2262   detail::RecordKeeperImpl &RK = T->getRecordKeeper().getImpl();
2263   VarInit *&I = RK.TheVarInitPool[std::make_pair(T, VN)];
2264   if (!I)
2265     I = new (RK.Allocator) VarInit(VN, T);
2266   return I;
2267 }
2268
2269 StringRef VarInit::getName() const {
2270   const auto *NameString = cast<StringInit>(getNameInit());
2271   return NameString->getValue();
2272 }
2273
2274 const Init *VarInit::getBit(unsigned Bit) const {
2275   if (getType() == BitRecTy::get(getRecordKeeper()))
2276     return this;
2277   return VarBitInit::get(this, Bit);
2278 }
2279
2280 const Init *VarInit::resolveReferences(Resolver &R) const {
2281   if (const Init *Val = R.resolve(VarName))
2282     return Val;
2283   return this;
2284 }
2285
2286 const VarBitInit *VarBitInit::get(const TypedInit *T, unsigned B) {
2287   detail::RecordKeeperImpl &RK = T->getRecordKeeper().getImpl();
2288   VarBitInit *&I = RK.TheVarBitInitPool[std::make_pair(T, B)];
2289   if (!I)
2290     I = new (RK.Allocator) VarBitInit(T, B);
2291   return I;
2292 }
2293
2294 std::string VarBitInit::getAsString() const {
2295   return TI->getAsString() + "{" + utostr(Bit) + "}";
2296 }
2297
2298 const Init *VarBitInit::resolveReferences(Resolver &R) const {
2299   const Init *I = TI->resolveReferences(R);
2300   if (TI != I)
2301     return I->getBit(getBitNum());
2302
2303   return this;
2304 }
2305
2306 DefInit::DefInit(const Record *D)
2307     : TypedInit(IK_DefInit, D->getType()), Def(D) {}
2308
2309 const Init *DefInit::convertInitializerTo(const RecTy *Ty) const {
2310   if (auto *RRT = dyn_cast<RecordRecTy>(Ty))
2311     if (getType()->typeIsConvertibleTo(RRT))
2312       return this;
2313   return nullptr;
2314 }
2315
2316 const RecTy *DefInit::getFieldType(const StringInit *FieldName) const {
2317   if (const RecordVal *RV = Def->getValue(FieldName))
2318     return RV->getType();
2319   return nullptr;
2320 }
2321
2322 std::string DefInit::getAsString() const { return std::string(Def->getName()); }
2323
2324 static void ProfileVarDefInit(FoldingSetNodeID &ID, const Record *Class,
2325                               ArrayRef<const ArgumentInit *> Args) {
2326   ID.AddInteger(Args.size());
2327   ID.AddPointer(Class);
2328
2329   for (const Init *I : Args)
2330     ID.AddPointer(I);
2331 }
2332
2333 VarDefInit::VarDefInit(SMLoc Loc, const Record *Class, unsigned N)
2334     : TypedInit(IK_VarDefInit, RecordRecTy::get(Class)), Loc(Loc), Class(Class),
2335       NumArgs(N) {}
2336
2337 const VarDefInit *VarDefInit::get(SMLoc Loc, const Record *Class,
2338                                   ArrayRef<const ArgumentInit *> Args) {
2339   FoldingSetNodeID ID;
2340   ProfileVarDefInit(ID, Class, Args);
2341
2342   detail::RecordKeeperImpl &RK = Class->getRecords().getImpl();
2343   void *IP = nullptr;
2344   if (const VarDefInit *I = RK.TheVarDefInitPool.FindNodeOrInsertPos(ID, IP))
2345     return I;
2346
2347   void *Mem = RK.Allocator.Allocate(
2348       totalSizeToAlloc<const ArgumentInit *>(Args.size()), alignof(VarDefInit));
2349   VarDefInit *I = new (Mem) VarDefInit(Loc, Class, Args.size());
2350   std::uninitialized_copy(Args.begin(), Args.end(),
2351                           I->getTrailingObjects<const ArgumentInit *>());
2352   RK.TheVarDefInitPool.InsertNode(I, IP);
2353   return I;
2354 }
2355
2356 void VarDefInit::Profile(FoldingSetNodeID &ID) const {
2357   ProfileVarDefInit(ID, Class, args());
2358 }
2359
2360 const DefInit *VarDefInit::instantiate() {
2361   if (Def)
2362     return Def;
2363
2364   RecordKeeper &Records = Class->getRecords();
2365   auto NewRecOwner = std::make_unique<Record>(
2366       Records.getNewAnonymousName(), Loc, Records, Record::RK_AnonymousDef);
2367   Record *NewRec = NewRecOwner.get();
2368
2369   // Copy values from class to instance
2370   for (const RecordVal &Val : Class->getValues())
2371     NewRec->addValue(Val);
2372
2373   // Copy assertions from class to instance.
2374   NewRec->appendAssertions(Class);
2375
2376   // Copy dumps from class to instance.
2377   NewRec->appendDumps(Class);
2378
2379   // Substitute and resolve template arguments
2380   ArrayRef<const Init *> TArgs = Class->getTemplateArgs();
2381   MapResolver R(NewRec);
2382
2383   for (const Init *Arg : TArgs) {
2384     R.set(Arg, NewRec->getValue(Arg)->getValue());
2385     NewRec->removeValue(Arg);
2386   }
2387
2388   for (auto *Arg : args()) {
2389     if (Arg->isPositional())
2390       R.set(TArgs[Arg->getIndex()], Arg->getValue());
2391     if (Arg->isNamed())
2392       R.set(Arg->getName(), Arg->getValue());
2393   }
2394
2395   NewRec->resolveReferences(R);
2396
2397   // Add superclasses.
2398   for (const auto &[SC, Loc] : Class->getSuperClasses())
2399     NewRec->addSuperClass(SC, Loc);
2400
2401   NewRec->addSuperClass(
2402       Class, SMRange(Class->getLoc().back(), Class->getLoc().back()));
2403
2404   // Resolve internal references and store in record keeper
2405   NewRec->resolveReferences();
2406   Records.addDef(std::move(NewRecOwner));
2407
2408   // Check the assertions.
2409   NewRec->checkRecordAssertions();
2410
2411   // Check the assertions.
2412   NewRec->emitRecordDumps();
2413
2414   return Def = NewRec->getDefInit();
2415 }
2416
2417 const Init *VarDefInit::resolveReferences(Resolver &R) const {
2418   TrackUnresolvedResolver UR(&R);
2419   bool Changed = false;
2420   SmallVector<const ArgumentInit *, 8> NewArgs;
2421   NewArgs.reserve(args_size());
2422
2423   for (const ArgumentInit *Arg : args()) {
2424     const auto *NewArg = cast<ArgumentInit>(Arg->resolveReferences(UR));
2425     NewArgs.push_back(NewArg);
2426     Changed |= NewArg != Arg;
2427   }
2428
2429   if (Changed) {
2430     auto *New = VarDefInit::get(Loc, Class, NewArgs);
2431     if (!UR.foundUnresolved())
2432       return const_cast<VarDefInit *>(New)->instantiate();
2433     return New;
2434   }
2435   return this;
2436 }
2437
2438 const Init *VarDefInit::Fold() const {
2439   if (Def)
2440     return Def;
2441
2442   TrackUnresolvedResolver R;
2443   for (const Init *Arg : args())
2444     Arg->resolveReferences(R);
2445
2446   if (!R.foundUnresolved())
2447     return const_cast<VarDefInit *>(this)->instantiate();
2448   return this;
2449 }
2450
2451 std::string VarDefInit::getAsString() const {
2452   std::string Result = Class->getNameInitAsString() + "<";
2453   const char *sep = "";
2454   for (const Init *Arg : args()) {
2455     Result += sep;
2456     sep = ", ";
2457     Result += Arg->getAsString();
2458   }
2459   return Result + ">";
2460 }
2461
2462 const FieldInit *FieldInit::get(const Init *R, const StringInit *FN) {
2463   detail::RecordKeeperImpl &RK = R->getRecordKeeper().getImpl();
2464   FieldInit *&I = RK.TheFieldInitPool[std::make_pair(R, FN)];
2465   if (!I)
2466     I = new (RK.Allocator) FieldInit(R, FN);
2467   return I;
2468 }
2469
2470 const Init *FieldInit::getBit(unsigned Bit) const {
2471   if (getType() == BitRecTy::get(getRecordKeeper()))
2472     return this;
2473   return VarBitInit::get(this, Bit);
2474 }
2475
2476 const Init *FieldInit::resolveReferences(Resolver &R) const {
2477   const Init *NewRec = Rec->resolveReferences(R);
2478   if (NewRec != Rec)
2479     return FieldInit::get(NewRec, FieldName)->Fold(R.getCurrentRecord());
2480   return this;
2481 }
2482
2483 const Init *FieldInit::Fold(const Record *CurRec) const {
2484   if (const auto *DI = dyn_cast<DefInit>(Rec)) {
2485     const Record *Def = DI->getDef();
2486     if (Def == CurRec)
2487       PrintFatalError(CurRec->getLoc(),
2488                       Twine("Attempting to access field '") +
2489                       FieldName->getAsUnquotedString() + "' of '" +
2490                       Rec->getAsString() + "' is a forbidden self-reference");
2491     const Init *FieldVal = Def->getValue(FieldName)->getValue();
2492     if (FieldVal->isConcrete())
2493       return FieldVal;
2494   }
2495   return this;
2496 }
2497
2498 bool FieldInit::isConcrete() const {
2499   if (const auto *DI = dyn_cast<DefInit>(Rec)) {
2500     const Init *FieldVal = DI->getDef()->getValue(FieldName)->getValue();
2501     return FieldVal->isConcrete();
2502   }
2503   return false;
2504 }
2505
2506 static void ProfileCondOpInit(FoldingSetNodeID &ID,
2507                               ArrayRef<const Init *> CondRange,
2508                               ArrayRef<const Init *> ValRange,
2509                               const RecTy *ValType) {
2510   assert(CondRange.size() == ValRange.size() &&
2511          "Number of conditions and values must match!");
2512   ID.AddPointer(ValType);
2513   ArrayRef<const Init *>::iterator Case = CondRange.begin();
2514   ArrayRef<const Init *>::iterator Val = ValRange.begin();
2515
2516   while (Case != CondRange.end()) {
2517     ID.AddPointer(*Case++);
2518     ID.AddPointer(*Val++);
2519   }
2520 }
2521
2522 void CondOpInit::Profile(FoldingSetNodeID &ID) const {
2523   ProfileCondOpInit(
2524       ID, ArrayRef(getTrailingObjects<const Init *>(), NumConds),
2525       ArrayRef(getTrailingObjects<const Init *>() + NumConds, NumConds),
2526       ValType);
2527 }
2528
2529 const CondOpInit *CondOpInit::get(ArrayRef<const Init *> CondRange,
2530                                   ArrayRef<const Init *> ValRange,
2531                                   const RecTy *Ty) {
2532   assert(CondRange.size() == ValRange.size() &&
2533          "Number of conditions and values must match!");
2534
2535   FoldingSetNodeID ID;
2536   ProfileCondOpInit(ID, CondRange, ValRange, Ty);
2537
2538   detail::RecordKeeperImpl &RK = Ty->getRecordKeeper().getImpl();
2539   void *IP = nullptr;
2540   if (const CondOpInit *I = RK.TheCondOpInitPool.FindNodeOrInsertPos(ID, IP))
2541     return I;
2542
2543   void *Mem = RK.Allocator.Allocate(
2544       totalSizeToAlloc<const Init *>(2 * CondRange.size()), alignof(BitsInit));
2545   CondOpInit *I = new(Mem) CondOpInit(CondRange.size(), Ty);
2546
2547   std::uninitialized_copy(CondRange.begin(), CondRange.end(),
2548                           I->getTrailingObjects<const Init *>());
2549   std::uninitialized_copy(ValRange.begin(), ValRange.end(),
2550                           I->getTrailingObjects<const Init *>() +
2551                               CondRange.size());
2552   RK.TheCondOpInitPool.InsertNode(I, IP);
2553   return I;
2554 }
2555
2556 const Init *CondOpInit::resolveReferences(Resolver &R) const {
2557   SmallVector<const Init *, 4> NewConds;
2558   bool Changed = false;
2559   for (const Init *Case : getConds()) {
2560     const Init *NewCase = Case->resolveReferences(R);
2561     NewConds.push_back(NewCase);
2562     Changed |= NewCase != Case;
2563   }
2564
2565   SmallVector<const Init *, 4> NewVals;
2566   for (const Init *Val : getVals()) {
2567     const Init *NewVal = Val->resolveReferences(R);
2568     NewVals.push_back(NewVal);
2569     Changed |= NewVal != Val;
2570   }
2571
2572   if (Changed)
2573     return (CondOpInit::get(NewConds, NewVals,
2574             getValType()))->Fold(R.getCurrentRecord());
2575
2576   return this;
2577 }
2578
2579 const Init *CondOpInit::Fold(const Record *CurRec) const {
2580   RecordKeeper &RK = getRecordKeeper();
2581   for (unsigned i = 0; i < NumConds; ++i) {
2582     const Init *Cond = getCond(i);
2583     const Init *Val = getVal(i);
2584
2585     if (const auto *CondI = dyn_cast_or_null<IntInit>(
2586             Cond->convertInitializerTo(IntRecTy::get(RK)))) {
2587       if (CondI->getValue())
2588         return Val->convertInitializerTo(getValType());
2589     } else {
2590       return this;
2591     }
2592   }
2593
2594   PrintFatalError(CurRec->getLoc(),
2595                   CurRec->getNameInitAsString() +
2596                   " does not have any true condition in:" +
2597                   this->getAsString());
2598   return nullptr;
2599 }
2600
2601 bool CondOpInit::isConcrete() const {
2602   for (const Init *Case : getConds())
2603     if (!Case->isConcrete())
2604       return false;
2605
2606   for (const Init *Val : getVals())
2607     if (!Val->isConcrete())
2608       return false;
2609
2610   return true;
2611 }
2612
2613 bool CondOpInit::isComplete() const {
2614   for (const Init *Case : getConds())
2615     if (!Case->isComplete())
2616       return false;
2617
2618   for (const Init *Val : getVals())
2619     if (!Val->isConcrete())
2620       return false;
2621
2622   return true;
2623 }
2624
2625 std::string CondOpInit::getAsString() const {
2626   std::string Result = "!cond(";
2627   for (unsigned i = 0; i < getNumConds(); i++) {
2628     Result += getCond(i)->getAsString() + ": ";
2629     Result += getVal(i)->getAsString();
2630     if (i != getNumConds()-1)
2631       Result += ", ";
2632   }
2633   return Result + ")";
2634 }
2635
2636 const Init *CondOpInit::getBit(unsigned Bit) const {
2637   return VarBitInit::get(this, Bit);
2638 }
2639
2640 static void ProfileDagInit(FoldingSetNodeID &ID, const Init *V,
2641                            const StringInit *VN,
2642                            ArrayRef<const Init *> ArgRange,
2643                            ArrayRef<const StringInit *> NameRange) {
2644   ID.AddPointer(V);
2645   ID.AddPointer(VN);
2646
2647   ArrayRef<const Init *>::iterator Arg = ArgRange.begin();
2648   ArrayRef<const StringInit *>::iterator Name = NameRange.begin();
2649   while (Arg != ArgRange.end()) {
2650     assert(Name != NameRange.end() && "Arg name underflow!");
2651     ID.AddPointer(*Arg++);
2652     ID.AddPointer(*Name++);
2653   }
2654   assert(Name == NameRange.end() && "Arg name overflow!");
2655 }
2656
2657 const DagInit *DagInit::get(const Init *V, const StringInit *VN,
2658                             ArrayRef<const Init *> ArgRange,
2659                             ArrayRef<const StringInit *> NameRange) {
2660   assert(ArgRange.size() == NameRange.size());
2661   FoldingSetNodeID ID;
2662   ProfileDagInit(ID, V, VN, ArgRange, NameRange);
2663
2664   detail::RecordKeeperImpl &RK = V->getRecordKeeper().getImpl();
2665   void *IP = nullptr;
2666   if (const DagInit *I = RK.TheDagInitPool.FindNodeOrInsertPos(ID, IP))
2667     return I;
2668
2669   void *Mem =
2670       RK.Allocator.Allocate(totalSizeToAlloc<const Init *, const StringInit *>(
2671                                 ArgRange.size(), NameRange.size()),
2672                             alignof(BitsInit));
2673   DagInit *I = new (Mem) DagInit(V, VN, ArgRange.size(), NameRange.size());
2674   std::uninitialized_copy(ArgRange.begin(), ArgRange.end(),
2675                           I->getTrailingObjects<const Init *>());
2676   std::uninitialized_copy(NameRange.begin(), NameRange.end(),
2677                           I->getTrailingObjects<const StringInit *>());
2678   RK.TheDagInitPool.InsertNode(I, IP);
2679   return I;
2680 }
2681
2682 const DagInit *
2683 DagInit::get(const Init *V, const StringInit *VN,
2684              ArrayRef<std::pair<const Init *, const StringInit *>> args) {
2685   SmallVector<const Init *, 8> Args;
2686   SmallVector<const StringInit *, 8> Names;
2687
2688   for (const auto &Arg : args) {
2689     Args.push_back(Arg.first);
2690     Names.push_back(Arg.second);
2691   }
2692
2693   return DagInit::get(V, VN, Args, Names);
2694 }
2695
2696 void DagInit::Profile(FoldingSetNodeID &ID) const {
2697   ProfileDagInit(
2698       ID, Val, ValName, ArrayRef(getTrailingObjects<const Init *>(), NumArgs),
2699       ArrayRef(getTrailingObjects<const StringInit *>(), NumArgNames));
2700 }
2701
2702 const Record *DagInit::getOperatorAsDef(ArrayRef<SMLoc> Loc) const {
2703   if (const auto *DefI = dyn_cast<DefInit>(Val))
2704     return DefI->getDef();
2705   PrintFatalError(Loc, "Expected record as operator");
2706   return nullptr;
2707 }
2708
2709 std::optional<unsigned> DagInit::getArgNo(StringRef Name) const {
2710   for (unsigned i = 0, e = getNumArgs(); i < e; ++i) {
2711     const StringInit *ArgName = getArgName(i);
2712     if (ArgName && ArgName->getValue() == Name)
2713       return i;
2714   }
2715   return std::nullopt;
2716 }
2717
2718 const Init *DagInit::resolveReferences(Resolver &R) const {
2719   SmallVector<const Init *, 8> NewArgs;
2720   NewArgs.reserve(arg_size());
2721   bool ArgsChanged = false;
2722   for (const Init *Arg : getArgs()) {
2723     const Init *NewArg = Arg->resolveReferences(R);
2724     NewArgs.push_back(NewArg);
2725     ArgsChanged |= NewArg != Arg;
2726   }
2727
2728   const Init *Op = Val->resolveReferences(R);
2729   if (Op != Val || ArgsChanged)
2730     return DagInit::get(Op, ValName, NewArgs, getArgNames());
2731
2732   return this;
2733 }
2734
2735 bool DagInit::isConcrete() const {
2736   if (!Val->isConcrete())
2737     return false;
2738   for (const Init *Elt : getArgs()) {
2739     if (!Elt->isConcrete())
2740       return false;
2741   }
2742   return true;
2743 }
2744
2745 std::string DagInit::getAsString() const {
2746   std::string Result = "(" + Val->getAsString();
2747   if (ValName)
2748     Result += ":" + ValName->getAsUnquotedString();
2749   if (!arg_empty()) {
2750     Result += " " + getArg(0)->getAsString();
2751     if (getArgName(0)) Result += ":$" + getArgName(0)->getAsUnquotedString();
2752     for (unsigned i = 1, e = getNumArgs(); i != e; ++i) {
2753       Result += ", " + getArg(i)->getAsString();
2754       if (getArgName(i)) Result += ":$" + getArgName(i)->getAsUnquotedString();
2755     }
2756   }
2757   return Result + ")";
2758 }
2759
2760 //===----------------------------------------------------------------------===//
2761 //    Other implementations
2762 //===----------------------------------------------------------------------===//
2763
2764 RecordVal::RecordVal(const Init *N, const RecTy *T, FieldKind K)
2765     : Name(N), TyAndKind(T, K) {
2766   setValue(UnsetInit::get(N->getRecordKeeper()));
2767   assert(Value && "Cannot create unset value for current type!");
2768 }
2769
2770 // This constructor accepts the same arguments as the above, but also
2771 // a source location.
2772 RecordVal::RecordVal(const Init *N, SMLoc Loc, const RecTy *T, FieldKind K)
2773     : Name(N), Loc(Loc), TyAndKind(T, K) {
2774   setValue(UnsetInit::get(N->getRecordKeeper()));
2775   assert(Value && "Cannot create unset value for current type!");
2776 }
2777
2778 StringRef RecordVal::getName() const {
2779   return cast<StringInit>(getNameInit())->getValue();
2780 }
2781
2782 std::string RecordVal::getPrintType() const {
2783   if (getType() == StringRecTy::get(getRecordKeeper())) {
2784     if (const auto *StrInit = dyn_cast<StringInit>(Value)) {
2785       if (StrInit->hasCodeFormat())
2786         return "code";
2787       else
2788         return "string";
2789     } else {
2790       return "string";
2791     }
2792   } else {
2793     return TyAndKind.getPointer()->getAsString();
2794   }
2795 }
2796
2797 bool RecordVal::setValue(const Init *V) {
2798   if (V) {
2799     Value = V->getCastTo(getType());
2800     if (Value) {
2801       assert(!isa<TypedInit>(Value) ||
2802              cast<TypedInit>(Value)->getType()->typeIsA(getType()));
2803       if (const auto *BTy = dyn_cast<BitsRecTy>(getType())) {
2804         if (!isa<BitsInit>(Value)) {
2805           SmallVector<const Init *, 64> Bits;
2806           Bits.reserve(BTy->getNumBits());
2807           for (unsigned I = 0, E = BTy->getNumBits(); I < E; ++I)
2808             Bits.push_back(Value->getBit(I));
2809           Value = BitsInit::get(V->getRecordKeeper(), Bits);
2810         }
2811       }
2812     }
2813     return Value == nullptr;
2814   }
2815   Value = nullptr;
2816   return false;
2817 }
2818
2819 // This version of setValue takes a source location and resets the
2820 // location in the RecordVal.
2821 bool RecordVal::setValue(const Init *V, SMLoc NewLoc) {
2822   Loc = NewLoc;
2823   if (V) {
2824     Value = V->getCastTo(getType());
2825     if (Value) {
2826       assert(!isa<TypedInit>(Value) ||
2827              cast<TypedInit>(Value)->getType()->typeIsA(getType()));
2828       if (const auto *BTy = dyn_cast<BitsRecTy>(getType())) {
2829         if (!isa<BitsInit>(Value)) {
2830           SmallVector<const Init *, 64> Bits;
2831           Bits.reserve(BTy->getNumBits());
2832           for (unsigned I = 0, E = BTy->getNumBits(); I < E; ++I)
2833             Bits.push_back(Value->getBit(I));
2834           Value = BitsInit::get(getRecordKeeper(), Bits);
2835         }
2836       }
2837     }
2838     return Value == nullptr;
2839   }
2840   Value = nullptr;
2841   return false;
2842 }
2843
2844 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2845 #include "llvm/TableGen/Record.h"
2846 LLVM_DUMP_METHOD void RecordVal::dump() const { errs() << *this; }
2847 #endif
2848
2849 void RecordVal::print(raw_ostream &OS, bool PrintSem) const {
2850   if (isNonconcreteOK()) OS << "field ";
2851   OS << getPrintType() << " " << getNameInitAsString();
2852
2853   if (getValue())
2854     OS << " = " << *getValue();
2855
2856   if (PrintSem) OS << ";\n";
2857 }
2858
2859 void Record::updateClassLoc(SMLoc Loc) {
2860   assert(Locs.size() == 1);
2861   ForwardDeclarationLocs.push_back(Locs.front());
2862
2863   Locs.clear();
2864   Locs.push_back(Loc);
2865 }
2866
2867 void Record::checkName() {
2868   // Ensure the record name has string type.
2869   const auto *TypedName = cast<const TypedInit>(Name);
2870   if (!isa<StringRecTy>(TypedName->getType()))
2871     PrintFatalError(getLoc(), Twine("Record name '") + Name->getAsString() +
2872                                   "' is not a string!");
2873 }
2874
2875 const RecordRecTy *Record::getType() const {
2876   SmallVector<const Record *, 4> DirectSCs;
2877   getDirectSuperClasses(DirectSCs);
2878   return RecordRecTy::get(TrackedRecords, DirectSCs);
2879 }
2880
2881 DefInit *Record::getDefInit() const {
2882   if (!CorrespondingDefInit) {
2883     CorrespondingDefInit =
2884         new (TrackedRecords.getImpl().Allocator) DefInit(this);
2885   }
2886   return CorrespondingDefInit;
2887 }
2888
2889 unsigned Record::getNewUID(RecordKeeper &RK) {
2890   return RK.getImpl().LastRecordID++;
2891 }
2892
2893 void Record::setName(const Init *NewName) {
2894   Name = NewName;
2895   checkName();
2896   // DO NOT resolve record values to the name at this point because
2897   // there might be default values for arguments of this def.  Those
2898   // arguments might not have been resolved yet so we don't want to
2899   // prematurely assume values for those arguments were not passed to
2900   // this def.
2901   //
2902   // Nonetheless, it may be that some of this Record's values
2903   // reference the record name.  Indeed, the reason for having the
2904   // record name be an Init is to provide this flexibility.  The extra
2905   // resolve steps after completely instantiating defs takes care of
2906   // this.  See TGParser::ParseDef and TGParser::ParseDefm.
2907 }
2908
2909 // NOTE for the next two functions:
2910 // Superclasses are in post-order, so the final one is a direct
2911 // superclass. All of its transitive superclases immediately precede it,
2912 // so we can step through the direct superclasses in reverse order.
2913
2914 bool Record::hasDirectSuperClass(const Record *Superclass) const {
2915   ArrayRef<std::pair<const Record *, SMRange>> SCs = getSuperClasses();
2916
2917   for (int I = SCs.size() - 1; I >= 0; --I) {
2918     const Record *SC = SCs[I].first;
2919     if (SC == Superclass)
2920       return true;
2921     I -= SC->getSuperClasses().size();
2922   }
2923
2924   return false;
2925 }
2926
2927 void Record::getDirectSuperClasses(
2928     SmallVectorImpl<const Record *> &Classes) const {
2929   ArrayRef<std::pair<const Record *, SMRange>> SCs = getSuperClasses();
2930
2931   while (!SCs.empty()) {
2932     const Record *SC = SCs.back().first;
2933     SCs = SCs.drop_back(1 + SC->getSuperClasses().size());
2934     Classes.push_back(SC);
2935   }
2936 }
2937
2938 void Record::resolveReferences(Resolver &R, const RecordVal *SkipVal) {
2939   const Init *OldName = getNameInit();
2940   const Init *NewName = Name->resolveReferences(R);
2941   if (NewName != OldName) {
2942     // Re-register with RecordKeeper.
2943     setName(NewName);
2944   }
2945
2946   // Resolve the field values.
2947   for (RecordVal &Value : Values) {
2948     if (SkipVal == &Value) // Skip resolve the same field as the given one
2949       continue;
2950     if (const Init *V = Value.getValue()) {
2951       const Init *VR = V->resolveReferences(R);
2952       if (Value.setValue(VR)) {
2953         std::string Type;
2954         if (const auto *VRT = dyn_cast<TypedInit>(VR))
2955           Type =
2956               (Twine("of type '") + VRT->getType()->getAsString() + "' ").str();
2957         PrintFatalError(
2958             getLoc(),
2959             Twine("Invalid value ") + Type + "found when setting field '" +
2960                 Value.getNameInitAsString() + "' of type '" +
2961                 Value.getType()->getAsString() +
2962                 "' after resolving references: " + VR->getAsUnquotedString() +
2963                 "\n");
2964       }
2965     }
2966   }
2967
2968   // Resolve the assertion expressions.
2969   for (auto &Assertion : Assertions) {
2970     const Init *Value = Assertion.Condition->resolveReferences(R);
2971     Assertion.Condition = Value;
2972     Value = Assertion.Message->resolveReferences(R);
2973     Assertion.Message = Value;
2974   }
2975   // Resolve the dump expressions.
2976   for (auto &Dump : Dumps) {
2977     const Init *Value = Dump.Message->resolveReferences(R);
2978     Dump.Message = Value;
2979   }
2980 }
2981
2982 void Record::resolveReferences(const Init *NewName) {
2983   RecordResolver R(*this);
2984   R.setName(NewName);
2985   R.setFinal(true);
2986   resolveReferences(R);
2987 }
2988
2989 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2990 LLVM_DUMP_METHOD void Record::dump() const { errs() << *this; }
2991 #endif
2992
2993 raw_ostream &llvm::operator<<(raw_ostream &OS, const Record &R) {
2994   OS << R.getNameInitAsString();
2995
2996   ArrayRef<const Init *> TArgs = R.getTemplateArgs();
2997   if (!TArgs.empty()) {
2998     OS << "<";
2999     bool NeedComma = false;
3000     for (const Init *TA : TArgs) {
3001       if (NeedComma) OS << ", ";
3002       NeedComma = true;
3003       const RecordVal *RV = R.getValue(TA);
3004       assert(RV && "Template argument record not found??");
3005       RV->print(OS, false);
3006     }
3007     OS << ">";
3008   }
3009
3010   OS << " {";
3011   ArrayRef<std::pair<const Record *, SMRange>> SC = R.getSuperClasses();
3012   if (!SC.empty()) {
3013     OS << "\t//";
3014     for (const auto &[SC, _] : SC)
3015       OS << " " << SC->getNameInitAsString();
3016   }
3017   OS << "\n";
3018
3019   for (const RecordVal &Val : R.getValues())
3020     if (Val.isNonconcreteOK() && !R.isTemplateArg(Val.getNameInit()))
3021       OS << Val;
3022   for (const RecordVal &Val : R.getValues())
3023     if (!Val.isNonconcreteOK() && !R.isTemplateArg(Val.getNameInit()))
3024       OS << Val;
3025
3026   return OS << "}\n";
3027 }
3028
3029 SMLoc Record::getFieldLoc(StringRef FieldName) const {
3030   const RecordVal *R = getValue(FieldName);
3031   if (!R)
3032     PrintFatalError(getLoc(), "Record `" + getName() +
3033       "' does not have a field named `" + FieldName + "'!\n");
3034   return R->getLoc();
3035 }
3036
3037 const Init *Record::getValueInit(StringRef FieldName) const {
3038   const RecordVal *R = getValue(FieldName);
3039   if (!R || !R->getValue())
3040     PrintFatalError(getLoc(), "Record `" + getName() +
3041       "' does not have a field named `" + FieldName + "'!\n");
3042   return R->getValue();
3043 }
3044
3045 StringRef Record::getValueAsString(StringRef FieldName) const {
3046   std::optional<StringRef> S = getValueAsOptionalString(FieldName);
3047   if (!S)
3048     PrintFatalError(getLoc(), "Record `" + getName() +
3049       "' does not have a field named `" + FieldName + "'!\n");
3050   return *S;
3051 }
3052
3053 std::optional<StringRef>
3054 Record::getValueAsOptionalString(StringRef FieldName) const {
3055   const RecordVal *R = getValue(FieldName);
3056   if (!R || !R->getValue())
3057     return std::nullopt;
3058   if (isa<UnsetInit>(R->getValue()))
3059     return std::nullopt;
3060
3061   if (const auto *SI = dyn_cast<StringInit>(R->getValue()))
3062     return SI->getValue();
3063
3064   PrintFatalError(getLoc(),
3065                   "Record `" + getName() + "', ` field `" + FieldName +
3066                       "' exists but does not have a string initializer!");
3067 }
3068
3069 const BitsInit *Record::getValueAsBitsInit(StringRef FieldName) const {
3070   const RecordVal *R = getValue(FieldName);
3071   if (!R || !R->getValue())
3072     PrintFatalError(getLoc(), "Record `" + getName() +
3073       "' does not have a field named `" + FieldName + "'!\n");
3074
3075   if (const auto *BI = dyn_cast<BitsInit>(R->getValue()))
3076     return BI;
3077   PrintFatalError(getLoc(), "Record `" + getName() + "', field `" + FieldName +
3078                                 "' exists but does not have a bits value");
3079 }
3080
3081 const ListInit *Record::getValueAsListInit(StringRef FieldName) const {
3082   const RecordVal *R = getValue(FieldName);
3083   if (!R || !R->getValue())
3084     PrintFatalError(getLoc(), "Record `" + getName() +
3085       "' does not have a field named `" + FieldName + "'!\n");
3086
3087   if (const auto *LI = dyn_cast<ListInit>(R->getValue()))
3088     return LI;
3089   PrintFatalError(getLoc(), "Record `" + getName() + "', field `" + FieldName +
3090                                 "' exists but does not have a list value");
3091 }
3092
3093 std::vector<const Record *>
3094 Record::getValueAsListOfDefs(StringRef FieldName) const {
3095   const ListInit *List = getValueAsListInit(FieldName);
3096   std::vector<const Record *> Defs;
3097   for (const Init *I : List->getValues()) {
3098     if (const auto *DI = dyn_cast<DefInit>(I))
3099       Defs.push_back(DI->getDef());
3100     else
3101       PrintFatalError(getLoc(), "Record `" + getName() + "', field `" +
3102                                     FieldName +
3103                                     "' list is not entirely DefInit!");
3104   }
3105   return Defs;
3106 }
3107
3108 int64_t Record::getValueAsInt(StringRef FieldName) const {
3109   const RecordVal *R = getValue(FieldName);
3110   if (!R || !R->getValue())
3111     PrintFatalError(getLoc(), "Record `" + getName() +
3112       "' does not have a field named `" + FieldName + "'!\n");
3113
3114   if (const auto *II = dyn_cast<IntInit>(R->getValue()))
3115     return II->getValue();
3116   PrintFatalError(getLoc(), Twine("Record `") + getName() + "', field `" +
3117                                 FieldName +
3118                                 "' exists but does not have an int value: " +
3119                                 R->getValue()->getAsString());
3120 }
3121
3122 std::vector<int64_t>
3123 Record::getValueAsListOfInts(StringRef FieldName) const {
3124   const ListInit *List = getValueAsListInit(FieldName);
3125   std::vector<int64_t> Ints;
3126   for (const Init *I : List->getValues()) {
3127     if (const auto *II = dyn_cast<IntInit>(I))
3128       Ints.push_back(II->getValue());
3129     else
3130       PrintFatalError(getLoc(),
3131                       Twine("Record `") + getName() + "', field `" + FieldName +
3132                           "' exists but does not have a list of ints value: " +
3133                           I->getAsString());
3134   }
3135   return Ints;
3136 }
3137
3138 std::vector<StringRef>
3139 Record::getValueAsListOfStrings(StringRef FieldName) const {
3140   const ListInit *List = getValueAsListInit(FieldName);
3141   std::vector<StringRef> Strings;
3142   for (const Init *I : List->getValues()) {
3143     if (const auto *SI = dyn_cast<StringInit>(I))
3144       Strings.push_back(SI->getValue());
3145     else
3146       PrintFatalError(getLoc(),
3147                       Twine("Record `") + getName() + "', field `" + FieldName +
3148                           "' exists but does not have a list of strings value: " +
3149                           I->getAsString());
3150   }
3151   return Strings;
3152 }
3153
3154 const Record *Record::getValueAsDef(StringRef FieldName) const {
3155   const RecordVal *R = getValue(FieldName);
3156   if (!R || !R->getValue())
3157     PrintFatalError(getLoc(), "Record `" + getName() +
3158       "' does not have a field named `" + FieldName + "'!\n");
3159
3160   if (const auto *DI = dyn_cast<DefInit>(R->getValue()))
3161     return DI->getDef();
3162   PrintFatalError(getLoc(), "Record `" + getName() + "', field `" +
3163     FieldName + "' does not have a def initializer!");
3164 }
3165
3166 const Record *Record::getValueAsOptionalDef(StringRef FieldName) const {
3167   const RecordVal *R = getValue(FieldName);
3168   if (!R || !R->getValue())
3169     PrintFatalError(getLoc(), "Record `" + getName() +
3170       "' does not have a field named `" + FieldName + "'!\n");
3171
3172   if (const auto *DI = dyn_cast<DefInit>(R->getValue()))
3173     return DI->getDef();
3174   if (isa<UnsetInit>(R->getValue()))
3175     return nullptr;
3176   PrintFatalError(getLoc(), "Record `" + getName() + "', field `" +
3177     FieldName + "' does not have either a def initializer or '?'!");
3178 }
3179
3180 bool Record::getValueAsBit(StringRef FieldName) const {
3181   const RecordVal *R = getValue(FieldName);
3182   if (!R || !R->getValue())
3183     PrintFatalError(getLoc(), "Record `" + getName() +
3184       "' does not have a field named `" + FieldName + "'!\n");
3185
3186   if (const auto *BI = dyn_cast<BitInit>(R->getValue()))
3187     return BI->getValue();
3188   PrintFatalError(getLoc(), "Record `" + getName() + "', field `" +
3189     FieldName + "' does not have a bit initializer!");
3190 }
3191
3192 bool Record::getValueAsBitOrUnset(StringRef FieldName, bool &Unset) const {
3193   const RecordVal *R = getValue(FieldName);
3194   if (!R || !R->getValue())
3195     PrintFatalError(getLoc(), "Record `" + getName() +
3196       "' does not have a field named `" + FieldName.str() + "'!\n");
3197
3198   if (isa<UnsetInit>(R->getValue())) {
3199     Unset = true;
3200     return false;
3201   }
3202   Unset = false;
3203   if (const auto *BI = dyn_cast<BitInit>(R->getValue()))
3204     return BI->getValue();
3205   PrintFatalError(getLoc(), "Record `" + getName() + "', field `" +
3206     FieldName + "' does not have a bit initializer!");
3207 }
3208
3209 const DagInit *Record::getValueAsDag(StringRef FieldName) const {
3210   const RecordVal *R = getValue(FieldName);
3211   if (!R || !R->getValue())
3212     PrintFatalError(getLoc(), "Record `" + getName() +
3213       "' does not have a field named `" + FieldName + "'!\n");
3214
3215   if (const auto *DI = dyn_cast<DagInit>(R->getValue()))
3216     return DI;
3217   PrintFatalError(getLoc(), "Record `" + getName() + "', field `" +
3218     FieldName + "' does not have a dag initializer!");
3219 }
3220
3221 // Check all record assertions: For each one, resolve the condition
3222 // and message, then call CheckAssert().
3223 // Note: The condition and message are probably already resolved,
3224 //       but resolving again allows calls before records are resolved.
3225 void Record::checkRecordAssertions() {
3226   RecordResolver R(*this);
3227   R.setFinal(true);
3228
3229   bool AnyFailed = false;
3230   for (const auto &Assertion : getAssertions()) {
3231     const Init *Condition = Assertion.Condition->resolveReferences(R);
3232     const Init *Message = Assertion.Message->resolveReferences(R);
3233     AnyFailed |= CheckAssert(Assertion.Loc, Condition, Message);
3234   }
3235
3236   if (!AnyFailed)
3237     return;
3238
3239   // If any of the record assertions failed, print some context that will
3240   // help see where the record that caused these assert failures is defined.
3241   PrintError(this, "assertion failed in this record");
3242 }
3243
3244 void Record::emitRecordDumps() {
3245   RecordResolver R(*this);
3246   R.setFinal(true);
3247
3248   for (const auto &Dump : getDumps()) {
3249     const Init *Message = Dump.Message->resolveReferences(R);
3250     dumpMessage(Dump.Loc, Message);
3251   }
3252 }
3253
3254 // Report a warning if the record has unused template arguments.
3255 void Record::checkUnusedTemplateArgs() {
3256   for (const Init *TA : getTemplateArgs()) {
3257     const RecordVal *Arg = getValue(TA);
3258     if (!Arg->isUsed())
3259       PrintWarning(Arg->getLoc(),
3260                    "unused template argument: " + Twine(Arg->getName()));
3261   }
3262 }
3263
3264 RecordKeeper::RecordKeeper()
3265     : Impl(std::make_unique<detail::RecordKeeperImpl>(*this)),
3266       Timer(std::make_unique<TGTimer>()) {}
3267
3268 RecordKeeper::~RecordKeeper() = default;
3269
3270 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3271 LLVM_DUMP_METHOD void RecordKeeper::dump() const { errs() << *this; }
3272 #endif
3273
3274 raw_ostream &llvm::operator<<(raw_ostream &OS, const RecordKeeper &RK) {
3275   OS << "------------- Classes -----------------\n";
3276   for (const auto &C : RK.getClasses())
3277     OS << "class " << *C.second;
3278
3279   OS << "------------- Defs -----------------\n";
3280   for (const auto &D : RK.getDefs())
3281     OS << "def " << *D.second;
3282   return OS;
3283 }
3284
3285 /// GetNewAnonymousName - Generate a unique anonymous name that can be used as
3286 /// an identifier.
3287 const Init *RecordKeeper::getNewAnonymousName() {
3288   return AnonymousNameInit::get(*this, getImpl().AnonCounter++);
3289 }
3290
3291 ArrayRef<const Record *>
3292 RecordKeeper::getAllDerivedDefinitions(StringRef ClassName) const {
3293   // We cache the record vectors for single classes. Many backends request
3294   // the same vectors multiple times.
3295   auto [Iter, Inserted] = Cache.try_emplace(ClassName.str());
3296   if (Inserted)
3297     Iter->second = getAllDerivedDefinitions(ArrayRef(ClassName));
3298   return Iter->second;
3299 }
3300
3301 std::vector<const Record *>
3302 RecordKeeper::getAllDerivedDefinitions(ArrayRef<StringRef> ClassNames) const {
3303   SmallVector<const Record *, 2> ClassRecs;
3304   std::vector<const Record *> Defs;
3305
3306   assert(ClassNames.size() > 0 && "At least one class must be passed.");
3307   for (const auto &ClassName : ClassNames) {
3308     const Record *Class = getClass(ClassName);
3309     if (!Class)
3310       PrintFatalError("The class '" + ClassName + "' is not defined\n");
3311     ClassRecs.push_back(Class);
3312   }
3313
3314   for (const auto &OneDef : getDefs()) {
3315     if (all_of(ClassRecs, [&OneDef](const Record *Class) {
3316           return OneDef.second->isSubClassOf(Class);
3317         }))
3318       Defs.push_back(OneDef.second.get());
3319   }
3320   llvm::sort(Defs, LessRecord());
3321   return Defs;
3322 }
3323
3324 ArrayRef<const Record *>
3325 RecordKeeper::getAllDerivedDefinitionsIfDefined(StringRef ClassName) const {
3326   if (getClass(ClassName))
3327     return getAllDerivedDefinitions(ClassName);
3328   return Cache[""];
3329 }
3330
3331 void RecordKeeper::dumpAllocationStats(raw_ostream &OS) const {
3332   Impl->dumpAllocationStats(OS);
3333 }
3334
3335 const Init *MapResolver::resolve(const Init *VarName) {
3336   auto It = Map.find(VarName);
3337   if (It == Map.end())
3338     return nullptr;
3339
3340   const Init *I = It->second.V;
3341
3342   if (!It->second.Resolved && Map.size() > 1) {
3343     // Resolve mutual references among the mapped variables, but prevent
3344     // infinite recursion.
3345     Map.erase(It);
3346     I = I->resolveReferences(*this);
3347     Map[VarName] = {I, true};
3348   }
3349
3350   return I;
3351 }
3352
3353 const Init *RecordResolver::resolve(const Init *VarName) {
3354   const Init *Val = Cache.lookup(VarName);
3355   if (Val)
3356     return Val;
3357
3358   if (llvm::is_contained(Stack, VarName))
3359     return nullptr; // prevent infinite recursion
3360
3361   if (const RecordVal *RV = getCurrentRecord()->getValue(VarName)) {
3362     if (!isa<UnsetInit>(RV->getValue())) {
3363       Val = RV->getValue();
3364       Stack.push_back(VarName);
3365       Val = Val->resolveReferences(*this);
3366       Stack.pop_back();
3367     }
3368   } else if (Name && VarName == getCurrentRecord()->getNameInit()) {
3369     Stack.push_back(VarName);
3370     Val = Name->resolveReferences(*this);
3371     Stack.pop_back();
3372   }
3373
3374   Cache[VarName] = Val;
3375   return Val;
3376 }
3377
3378 const Init *TrackUnresolvedResolver::resolve(const Init *VarName) {
3379   const Init *I = nullptr;
3380
3381   if (R) {
3382     I = R->resolve(VarName);
3383     if (I && !FoundUnresolved) {
3384       // Do not recurse into the resolved initializer, as that would change
3385       // the behavior of the resolver we're delegating, but do check to see
3386       // if there are unresolved variables remaining.
3387       TrackUnresolvedResolver Sub;
3388       I->resolveReferences(Sub);
3389       FoundUnresolved |= Sub.FoundUnresolved;
3390     }
3391   }
3392
3393   if (!I)
3394     FoundUnresolved = true;
3395   return I;
3396 }
3397
3398 const Init *HasReferenceResolver::resolve(const Init *VarName) {
3399   if (VarName == VarNameToTrack)
3400     Found = true;
3401   return nullptr;
3402 }