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