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