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       DefInit *DI = DefInit::get(Dag->getOperatorAsDef({}));
 927       if (!DI->getType()->typeIsA(getType())) {
 928         PrintFatalError(CurRec->getLoc(),
 929                         Twine("Expected type '") +
 930                         getType()->getAsString() + "', got '" +
 931                         DI->getType()->getAsString() + "' in: " +
 932                         getAsString() + "\n");
 933       } else {
 934         return DI;
 935       }
 936     }
 937     break;
 938
 939   case LOG2:
 940     if (IntInit *LHSi = dyn_cast_or_null<IntInit>(
 941             LHS->convertInitializerTo(IntRecTy::get(RK)))) {
 942       int64_t LHSv = LHSi->getValue();
 943       if (LHSv <= 0) {
 944         PrintFatalError(CurRec->getLoc(),
 945                         "Illegal operation: logtwo is undefined "
 946                         "on arguments less than or equal to 0");
 947       } else {
 948         uint64_t Log = Log2_64(LHSv);
 949         assert(Log <= INT64_MAX &&
 950                "Log of an int64_t must be smaller than INT64_MAX");
 951         return IntInit::get(RK, static_cast<int64_t>(Log));
 952       }
 953     }
 954     break;
 955   }
 956   return const_cast<UnOpInit *>(this);
 957 }
 958
 959 Init *UnOpInit::resolveReferences(Resolver &R) const {
 960   Init *lhs = LHS->resolveReferences(R);
 961
 962   if (LHS != lhs || (R.isFinal() && getOpcode() == CAST))
 963     return (UnOpInit::get(getOpcode(), lhs, getType()))
 964         ->Fold(R.getCurrentRecord(), R.isFinal());
 965   return const_cast<UnOpInit *>(this);
 966 }
 967
 968 std::string UnOpInit::getAsString() const {
 969   std::string Result;
 970   switch (getOpcode()) {
 971   case CAST: Result = "!cast<" + getType()->getAsString() + ">"; break;
 972   case NOT: Result = "!not"; break;
 973   case HEAD: Result = "!head"; break;
 974   case TAIL: Result = "!tail"; break;
 975   case SIZE: Result = "!size"; break;
 976   case EMPTY: Result = "!empty"; break;
 977   case GETDAGOP: Result = "!getdagop"; break;
 978   case LOG2 : Result = "!logtwo"; break;
 979   case REPR:
 980     Result = "!repr";
 981     break;
 982   case TOLOWER:
 983     Result = "!tolower";
 984     break;
 985   case TOUPPER:
 986     Result = "!toupper";
 987     break;
 988   }
 989   return Result + "(" + LHS->getAsString() + ")";
 990 }
 991
 992 static void
 993 ProfileBinOpInit(FoldingSetNodeID &ID, unsigned Opcode, Init *LHS, Init *RHS,
 994                  RecTy *Type) {
 995   ID.AddInteger(Opcode);
 996   ID.AddPointer(LHS);
 997   ID.AddPointer(RHS);
 998   ID.AddPointer(Type);
 999 }
1000
1001 BinOpInit *BinOpInit::get(BinaryOp Opc, Init *LHS, Init *RHS, RecTy *Type) {
1002   FoldingSetNodeID ID;
1003   ProfileBinOpInit(ID, Opc, LHS, RHS, Type);
1004
1005   detail::RecordKeeperImpl &RK = LHS->getRecordKeeper().getImpl();
1006   void *IP = nullptr;
1007   if (BinOpInit *I = RK.TheBinOpInitPool.FindNodeOrInsertPos(ID, IP))
1008     return I;
1009
1010   BinOpInit *I = new (RK.Allocator) BinOpInit(Opc, LHS, RHS, Type);
1011   RK.TheBinOpInitPool.InsertNode(I, IP);
1012   return I;
1013 }
1014
1015 void BinOpInit::Profile(FoldingSetNodeID &ID) const {
1016   ProfileBinOpInit(ID, getOpcode(), getLHS(), getRHS(), getType());
1017 }
1018
1019 static StringInit *ConcatStringInits(const StringInit *I0,
1020                                      const StringInit *I1) {
1021   SmallString<80> Concat(I0->getValue());
1022   Concat.append(I1->getValue());
1023   return StringInit::get(
1024       I0->getRecordKeeper(), Concat,
1025       StringInit::determineFormat(I0->getFormat(), I1->getFormat()));
1026 }
1027
1028 static StringInit *interleaveStringList(const ListInit *List,
1029                                         const StringInit *Delim) {
1030   if (List->size() == 0)
1031     return StringInit::get(List->getRecordKeeper(), "");
1032   StringInit *Element = dyn_cast<StringInit>(List->getElement(0));
1033   if (!Element)
1034     return nullptr;
1035   SmallString<80> Result(Element->getValue());
1036   StringInit::StringFormat Fmt = StringInit::SF_String;
1037
1038   for (unsigned I = 1, E = List->size(); I < E; ++I) {
1039     Result.append(Delim->getValue());
1040     StringInit *Element = dyn_cast<StringInit>(List->getElement(I));
1041     if (!Element)
1042       return nullptr;
1043     Result.append(Element->getValue());
1044     Fmt = StringInit::determineFormat(Fmt, Element->getFormat());
1045   }
1046   return StringInit::get(List->getRecordKeeper(), Result, Fmt);
1047 }
1048
1049 static StringInit *interleaveIntList(const ListInit *List,
1050                                      const StringInit *Delim) {
1051   RecordKeeper &RK = List->getRecordKeeper();
1052   if (List->size() == 0)
1053     return StringInit::get(RK, "");
1054   IntInit *Element = dyn_cast_or_null<IntInit>(
1055       List->getElement(0)->convertInitializerTo(IntRecTy::get(RK)));
1056   if (!Element)
1057     return nullptr;
1058   SmallString<80> Result(Element->getAsString());
1059
1060   for (unsigned I = 1, E = List->size(); I < E; ++I) {
1061     Result.append(Delim->getValue());
1062     IntInit *Element = dyn_cast_or_null<IntInit>(
1063         List->getElement(I)->convertInitializerTo(IntRecTy::get(RK)));
1064     if (!Element)
1065       return nullptr;
1066     Result.append(Element->getAsString());
1067   }
1068   return StringInit::get(RK, Result);
1069 }
1070
1071 Init *BinOpInit::getStrConcat(Init *I0, Init *I1) {
1072   // Shortcut for the common case of concatenating two strings.
1073   if (const StringInit *I0s = dyn_cast<StringInit>(I0))
1074     if (const StringInit *I1s = dyn_cast<StringInit>(I1))
1075       return ConcatStringInits(I0s, I1s);
1076   return BinOpInit::get(BinOpInit::STRCONCAT, I0, I1,
1077                         StringRecTy::get(I0->getRecordKeeper()));
1078 }
1079
1080 static ListInit *ConcatListInits(const ListInit *LHS,
1081                                  const ListInit *RHS) {
1082   SmallVector<Init *, 8> Args;
1083   llvm::append_range(Args, *LHS);
1084   llvm::append_range(Args, *RHS);
1085   return ListInit::get(Args, LHS->getElementType());
1086 }
1087
1088 Init *BinOpInit::getListConcat(TypedInit *LHS, Init *RHS) {
1089   assert(isa<ListRecTy>(LHS->getType()) && "First arg must be a list");
1090
1091   // Shortcut for the common case of concatenating two lists.
1092   if (const ListInit *LHSList = dyn_cast<ListInit>(LHS))
1093     if (const ListInit *RHSList = dyn_cast<ListInit>(RHS))
1094       return ConcatListInits(LHSList, RHSList);
1095   return BinOpInit::get(BinOpInit::LISTCONCAT, LHS, RHS, LHS->getType());
1096 }
1097
1098 std::optional<bool> BinOpInit::CompareInit(unsigned Opc, Init *LHS,
1099                                            Init *RHS) const {
1100   // First see if we have two bit, bits, or int.
1101   IntInit *LHSi = dyn_cast_or_null<IntInit>(
1102       LHS->convertInitializerTo(IntRecTy::get(getRecordKeeper())));
1103   IntInit *RHSi = dyn_cast_or_null<IntInit>(
1104       RHS->convertInitializerTo(IntRecTy::get(getRecordKeeper())));
1105
1106   if (LHSi && RHSi) {
1107     bool Result;
1108     switch (Opc) {
1109     case EQ:
1110       Result = LHSi->getValue() == RHSi->getValue();
1111       break;
1112     case NE:
1113       Result = LHSi->getValue() != RHSi->getValue();
1114       break;
1115     case LE:
1116       Result = LHSi->getValue() <= RHSi->getValue();
1117       break;
1118     case LT:
1119       Result = LHSi->getValue() < RHSi->getValue();
1120       break;
1121     case GE:
1122       Result = LHSi->getValue() >= RHSi->getValue();
1123       break;
1124     case GT:
1125       Result = LHSi->getValue() > RHSi->getValue();
1126       break;
1127     default:
1128       llvm_unreachable("unhandled comparison");
1129     }
1130     return Result;
1131   }
1132
1133   // Next try strings.
1134   StringInit *LHSs = dyn_cast<StringInit>(LHS);
1135   StringInit *RHSs = dyn_cast<StringInit>(RHS);
1136
1137   if (LHSs && RHSs) {
1138     bool Result;
1139     switch (Opc) {
1140     case EQ:
1141       Result = LHSs->getValue() == RHSs->getValue();
1142       break;
1143     case NE:
1144       Result = LHSs->getValue() != RHSs->getValue();
1145       break;
1146     case LE:
1147       Result = LHSs->getValue() <= RHSs->getValue();
1148       break;
1149     case LT:
1150       Result = LHSs->getValue() < RHSs->getValue();
1151       break;
1152     case GE:
1153       Result = LHSs->getValue() >= RHSs->getValue();
1154       break;
1155     case GT:
1156       Result = LHSs->getValue() > RHSs->getValue();
1157       break;
1158     default:
1159       llvm_unreachable("unhandled comparison");
1160     }
1161     return Result;
1162   }
1163
1164   // Finally, !eq and !ne can be used with records.
1165   if (Opc == EQ || Opc == NE) {
1166     DefInit *LHSd = dyn_cast<DefInit>(LHS);
1167     DefInit *RHSd = dyn_cast<DefInit>(RHS);
1168     if (LHSd && RHSd)
1169       return (Opc == EQ) ? LHSd == RHSd : LHSd != RHSd;
1170   }
1171
1172   return std::nullopt;
1173 }
1174
1175 static std::optional<unsigned> getDagArgNoByKey(DagInit *Dag, Init *Key,
1176                                                 std::string &Error) {
1177   // Accessor by index
1178   if (IntInit *Idx = dyn_cast<IntInit>(Key)) {
1179     int64_t Pos = Idx->getValue();
1180     if (Pos < 0) {
1181       // The index is negative.
1182       Error =
1183           (Twine("index ") + std::to_string(Pos) + Twine(" is negative")).str();
1184       return std::nullopt;
1185     }
1186     if (Pos >= Dag->getNumArgs()) {
1187       // The index is out-of-range.
1188       Error = (Twine("index ") + std::to_string(Pos) +
1189                " is out of range (dag has " +
1190                std::to_string(Dag->getNumArgs()) + " arguments)")
1191                   .str();
1192       return std::nullopt;
1193     }
1194     return Pos;
1195   }
1196   assert(isa<StringInit>(Key));
1197   // Accessor by name
1198   StringInit *Name = dyn_cast<StringInit>(Key);
1199   auto ArgNo = Dag->getArgNo(Name->getValue());
1200   if (!ArgNo) {
1201     // The key is not found.
1202     Error = (Twine("key '") + Name->getValue() + Twine("' is not found")).str();
1203     return std::nullopt;
1204   }
1205   return *ArgNo;
1206 }
1207
1208 Init *BinOpInit::Fold(Record *CurRec) const {
1209   switch (getOpcode()) {
1210   case CONCAT: {
1211     DagInit *LHSs = dyn_cast<DagInit>(LHS);
1212     DagInit *RHSs = dyn_cast<DagInit>(RHS);
1213     if (LHSs && RHSs) {
1214       DefInit *LOp = dyn_cast<DefInit>(LHSs->getOperator());
1215       DefInit *ROp = dyn_cast<DefInit>(RHSs->getOperator());
1216       if ((!LOp && !isa<UnsetInit>(LHSs->getOperator())) ||
1217           (!ROp && !isa<UnsetInit>(RHSs->getOperator())))
1218         break;
1219       if (LOp && ROp && LOp->getDef() != ROp->getDef()) {
1220         PrintFatalError(Twine("Concatenated Dag operators do not match: '") +
1221                         LHSs->getAsString() + "' vs. '" + RHSs->getAsString() +
1222                         "'");
1223       }
1224       Init *Op = LOp ? LOp : ROp;
1225       if (!Op)
1226         Op = UnsetInit::get(getRecordKeeper());
1227
1228       SmallVector<Init*, 8> Args;
1229       SmallVector<StringInit*, 8> ArgNames;
1230       for (unsigned i = 0, e = LHSs->getNumArgs(); i != e; ++i) {
1231         Args.push_back(LHSs->getArg(i));
1232         ArgNames.push_back(LHSs->getArgName(i));
1233       }
1234       for (unsigned i = 0, e = RHSs->getNumArgs(); i != e; ++i) {
1235         Args.push_back(RHSs->getArg(i));
1236         ArgNames.push_back(RHSs->getArgName(i));
1237       }
1238       return DagInit::get(Op, nullptr, Args, ArgNames);
1239     }
1240     break;
1241   }
1242   case LISTCONCAT: {
1243     ListInit *LHSs = dyn_cast<ListInit>(LHS);
1244     ListInit *RHSs = dyn_cast<ListInit>(RHS);
1245     if (LHSs && RHSs) {
1246       SmallVector<Init *, 8> Args;
1247       llvm::append_range(Args, *LHSs);
1248       llvm::append_range(Args, *RHSs);
1249       return ListInit::get(Args, LHSs->getElementType());
1250     }
1251     break;
1252   }
1253   case LISTSPLAT: {
1254     TypedInit *Value = dyn_cast<TypedInit>(LHS);
1255     IntInit *Size = dyn_cast<IntInit>(RHS);
1256     if (Value && Size) {
1257       SmallVector<Init *, 8> Args(Size->getValue(), Value);
1258       return ListInit::get(Args, Value->getType());
1259     }
1260     break;
1261   }
1262   case LISTREMOVE: {
1263     ListInit *LHSs = dyn_cast<ListInit>(LHS);
1264     ListInit *RHSs = dyn_cast<ListInit>(RHS);
1265     if (LHSs && RHSs) {
1266       SmallVector<Init *, 8> Args;
1267       for (Init *EltLHS : *LHSs) {
1268         bool Found = false;
1269         for (Init *EltRHS : *RHSs) {
1270           if (std::optional<bool> Result = CompareInit(EQ, EltLHS, EltRHS)) {
1271             if (*Result) {
1272               Found = true;
1273               break;
1274             }
1275           }
1276         }
1277         if (!Found)
1278           Args.push_back(EltLHS);
1279       }
1280       return ListInit::get(Args, LHSs->getElementType());
1281     }
1282     break;
1283   }
1284   case LISTELEM: {
1285     auto *TheList = dyn_cast<ListInit>(LHS);
1286     auto *Idx = dyn_cast<IntInit>(RHS);
1287     if (!TheList || !Idx)
1288       break;
1289     auto i = Idx->getValue();
1290     if (i < 0 || i >= (ssize_t)TheList->size())
1291       break;
1292     return TheList->getElement(i);
1293   }
1294   case LISTSLICE: {
1295     auto *TheList = dyn_cast<ListInit>(LHS);
1296     auto *SliceIdxs = dyn_cast<ListInit>(RHS);
1297     if (!TheList || !SliceIdxs)
1298       break;
1299     SmallVector<Init *, 8> Args;
1300     Args.reserve(SliceIdxs->size());
1301     for (auto *I : *SliceIdxs) {
1302       auto *II = dyn_cast<IntInit>(I);
1303       if (!II)
1304         goto unresolved;
1305       auto i = II->getValue();
1306       if (i < 0 || i >= (ssize_t)TheList->size())
1307         goto unresolved;
1308       Args.push_back(TheList->getElement(i));
1309     }
1310     return ListInit::get(Args, TheList->getElementType());
1311   }
1312   case RANGEC: {
1313     auto *LHSi = dyn_cast<IntInit>(LHS);
1314     auto *RHSi = dyn_cast<IntInit>(RHS);
1315     if (!LHSi || !RHSi)
1316       break;
1317
1318     auto Start = LHSi->getValue();
1319     auto End = RHSi->getValue();
1320     SmallVector<Init *, 8> Args;
1321     if (getOpcode() == RANGEC) {
1322       // Closed interval
1323       if (Start <= End) {
1324         // Ascending order
1325         Args.reserve(End - Start + 1);
1326         for (auto i = Start; i <= End; ++i)
1327           Args.push_back(IntInit::get(getRecordKeeper(), i));
1328       } else {
1329         // Descending order
1330         Args.reserve(Start - End + 1);
1331         for (auto i = Start; i >= End; --i)
1332           Args.push_back(IntInit::get(getRecordKeeper(), i));
1333       }
1334     } else if (Start < End) {
1335       // Half-open interval (excludes `End`)
1336       Args.reserve(End - Start);
1337       for (auto i = Start; i < End; ++i)
1338         Args.push_back(IntInit::get(getRecordKeeper(), i));
1339     } else {
1340       // Empty set
1341     }
1342     return ListInit::get(Args, LHSi->getType());
1343   }
1344   case STRCONCAT: {
1345     StringInit *LHSs = dyn_cast<StringInit>(LHS);
1346     StringInit *RHSs = dyn_cast<StringInit>(RHS);
1347     if (LHSs && RHSs)
1348       return ConcatStringInits(LHSs, RHSs);
1349     break;
1350   }
1351   case INTERLEAVE: {
1352     ListInit *List = dyn_cast<ListInit>(LHS);
1353     StringInit *Delim = dyn_cast<StringInit>(RHS);
1354     if (List && Delim) {
1355       StringInit *Result;
1356       if (isa<StringRecTy>(List->getElementType()))
1357         Result = interleaveStringList(List, Delim);
1358       else
1359         Result = interleaveIntList(List, Delim);
1360       if (Result)
1361         return Result;
1362     }
1363     break;
1364   }
1365   case EQ:
1366   case NE:
1367   case LE:
1368   case LT:
1369   case GE:
1370   case GT: {
1371     if (std::optional<bool> Result = CompareInit(getOpcode(), LHS, RHS))
1372       return BitInit::get(getRecordKeeper(), *Result);
1373     break;
1374   }
1375   case GETDAGARG: {
1376     DagInit *Dag = dyn_cast<DagInit>(LHS);
1377     if (Dag && isa<IntInit, StringInit>(RHS)) {
1378       std::string Error;
1379       auto ArgNo = getDagArgNoByKey(Dag, RHS, Error);
1380       if (!ArgNo)
1381         PrintFatalError(CurRec->getLoc(), "!getdagarg " + Error);
1382
1383       assert(*ArgNo < Dag->getNumArgs());
1384
1385       Init *Arg = Dag->getArg(*ArgNo);
1386       if (auto *TI = dyn_cast<TypedInit>(Arg))
1387         if (!TI->getType()->typeIsConvertibleTo(getType()))
1388           return UnsetInit::get(Dag->getRecordKeeper());
1389       return Arg;
1390     }
1391     break;
1392   }
1393   case GETDAGNAME: {
1394     DagInit *Dag = dyn_cast<DagInit>(LHS);
1395     IntInit *Idx = dyn_cast<IntInit>(RHS);
1396     if (Dag && Idx) {
1397       int64_t Pos = Idx->getValue();
1398       if (Pos < 0 || Pos >= Dag->getNumArgs()) {
1399         // The index is out-of-range.
1400         PrintError(CurRec->getLoc(),
1401                    Twine("!getdagname index is out of range 0...") +
1402                        std::to_string(Dag->getNumArgs() - 1) + ": " +
1403                        std::to_string(Pos));
1404       }
1405       Init *ArgName = Dag->getArgName(Pos);
1406       if (!ArgName)
1407         return UnsetInit::get(getRecordKeeper());
1408       return ArgName;
1409     }
1410     break;
1411   }
1412   case SETDAGOP: {
1413     DagInit *Dag = dyn_cast<DagInit>(LHS);
1414     DefInit *Op = dyn_cast<DefInit>(RHS);
1415     if (Dag && Op) {
1416       SmallVector<Init*, 8> Args;
1417       SmallVector<StringInit*, 8> ArgNames;
1418       for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) {
1419         Args.push_back(Dag->getArg(i));
1420         ArgNames.push_back(Dag->getArgName(i));
1421       }
1422       return DagInit::get(Op, nullptr, Args, ArgNames);
1423     }
1424     break;
1425   }
1426   case ADD:
1427   case SUB:
1428   case MUL:
1429   case DIV:
1430   case AND:
1431   case OR:
1432   case XOR:
1433   case SHL:
1434   case SRA:
1435   case SRL: {
1436     IntInit *LHSi = dyn_cast_or_null<IntInit>(
1437         LHS->convertInitializerTo(IntRecTy::get(getRecordKeeper())));
1438     IntInit *RHSi = dyn_cast_or_null<IntInit>(
1439         RHS->convertInitializerTo(IntRecTy::get(getRecordKeeper())));
1440     if (LHSi && RHSi) {
1441       int64_t LHSv = LHSi->getValue(), RHSv = RHSi->getValue();
1442       int64_t Result;
1443       switch (getOpcode()) {
1444       default: llvm_unreachable("Bad opcode!");
1445       case ADD: Result = LHSv + RHSv; break;
1446       case SUB: Result = LHSv - RHSv; break;
1447       case MUL: Result = LHSv * RHSv; break;
1448       case DIV:
1449         if (RHSv == 0)
1450           PrintFatalError(CurRec->getLoc(),
1451                           "Illegal operation: division by zero");
1452         else if (LHSv == INT64_MIN && RHSv == -1)
1453           PrintFatalError(CurRec->getLoc(),
1454                           "Illegal operation: INT64_MIN / -1");
1455         else
1456           Result = LHSv / RHSv;
1457         break;
1458       case AND: Result = LHSv & RHSv; break;
1459       case OR:  Result = LHSv | RHSv; break;
1460       case XOR: Result = LHSv ^ RHSv; break;
1461       case SHL: Result = (uint64_t)LHSv << (uint64_t)RHSv; break;
1462       case SRA: Result = LHSv >> RHSv; break;
1463       case SRL: Result = (uint64_t)LHSv >> (uint64_t)RHSv; break;
1464       }
1465       return IntInit::get(getRecordKeeper(), Result);
1466     }
1467     break;
1468   }
1469   }
1470 unresolved:
1471   return const_cast<BinOpInit *>(this);
1472 }
1473
1474 Init *BinOpInit::resolveReferences(Resolver &R) const {
1475   Init *lhs = LHS->resolveReferences(R);
1476   Init *rhs = RHS->resolveReferences(R);
1477
1478   if (LHS != lhs || RHS != rhs)
1479     return (BinOpInit::get(getOpcode(), lhs, rhs, getType()))
1480         ->Fold(R.getCurrentRecord());
1481   return const_cast<BinOpInit *>(this);
1482 }
1483
1484 std::string BinOpInit::getAsString() const {
1485   std::string Result;
1486   switch (getOpcode()) {
1487   case LISTELEM:
1488   case LISTSLICE:
1489     return LHS->getAsString() + "[" + RHS->getAsString() + "]";
1490   case RANGEC:
1491     return LHS->getAsString() + "..." + RHS->getAsString();
1492   case CONCAT: Result = "!con"; break;
1493   case ADD: Result = "!add"; break;
1494   case SUB: Result = "!sub"; break;
1495   case MUL: Result = "!mul"; break;
1496   case DIV: Result = "!div"; break;
1497   case AND: Result = "!and"; break;
1498   case OR: Result = "!or"; break;
1499   case XOR: Result = "!xor"; break;
1500   case SHL: Result = "!shl"; break;
1501   case SRA: Result = "!sra"; break;
1502   case SRL: Result = "!srl"; break;
1503   case EQ: Result = "!eq"; break;
1504   case NE: Result = "!ne"; break;
1505   case LE: Result = "!le"; break;
1506   case LT: Result = "!lt"; break;
1507   case GE: Result = "!ge"; break;
1508   case GT: Result = "!gt"; break;
1509   case LISTCONCAT: Result = "!listconcat"; break;
1510   case LISTSPLAT: Result = "!listsplat"; break;
1511   case LISTREMOVE:
1512     Result = "!listremove";
1513     break;
1514   case STRCONCAT: Result = "!strconcat"; break;
1515   case INTERLEAVE: Result = "!interleave"; break;
1516   case SETDAGOP: Result = "!setdagop"; break;
1517   case GETDAGARG:
1518     Result = "!getdagarg<" + getType()->getAsString() + ">";
1519     break;
1520   case GETDAGNAME:
1521     Result = "!getdagname";
1522     break;
1523   }
1524   return Result + "(" + LHS->getAsString() + ", " + RHS->getAsString() + ")";
1525 }
1526
1527 static void
1528 ProfileTernOpInit(FoldingSetNodeID &ID, unsigned Opcode, Init *LHS, Init *MHS,
1529                   Init *RHS, RecTy *Type) {
1530   ID.AddInteger(Opcode);
1531   ID.AddPointer(LHS);
1532   ID.AddPointer(MHS);
1533   ID.AddPointer(RHS);
1534   ID.AddPointer(Type);
1535 }
1536
1537 TernOpInit *TernOpInit::get(TernaryOp Opc, Init *LHS, Init *MHS, Init *RHS,
1538                             RecTy *Type) {
1539   FoldingSetNodeID ID;
1540   ProfileTernOpInit(ID, Opc, LHS, MHS, RHS, Type);
1541
1542   detail::RecordKeeperImpl &RK = LHS->getRecordKeeper().getImpl();
1543   void *IP = nullptr;
1544   if (TernOpInit *I = RK.TheTernOpInitPool.FindNodeOrInsertPos(ID, IP))
1545     return I;
1546
1547   TernOpInit *I = new (RK.Allocator) TernOpInit(Opc, LHS, MHS, RHS, Type);
1548   RK.TheTernOpInitPool.InsertNode(I, IP);
1549   return I;
1550 }
1551
1552 void TernOpInit::Profile(FoldingSetNodeID &ID) const {
1553   ProfileTernOpInit(ID, getOpcode(), getLHS(), getMHS(), getRHS(), getType());
1554 }
1555
1556 static Init *ItemApply(Init *LHS, Init *MHSe, Init *RHS, Record *CurRec) {
1557   MapResolver R(CurRec);
1558   R.set(LHS, MHSe);
1559   return RHS->resolveReferences(R);
1560 }
1561
1562 static Init *ForeachDagApply(Init *LHS, DagInit *MHSd, Init *RHS,
1563                              Record *CurRec) {
1564   bool Change = false;
1565   Init *Val = ItemApply(LHS, MHSd->getOperator(), RHS, CurRec);
1566   if (Val != MHSd->getOperator())
1567     Change = true;
1568
1569   SmallVector<std::pair<Init *, StringInit *>, 8> NewArgs;
1570   for (unsigned int i = 0; i < MHSd->getNumArgs(); ++i) {
1571     Init *Arg = MHSd->getArg(i);
1572     Init *NewArg;
1573     StringInit *ArgName = MHSd->getArgName(i);
1574
1575     if (DagInit *Argd = dyn_cast<DagInit>(Arg))
1576       NewArg = ForeachDagApply(LHS, Argd, RHS, CurRec);
1577     else
1578       NewArg = ItemApply(LHS, Arg, RHS, CurRec);
1579
1580     NewArgs.push_back(std::make_pair(NewArg, ArgName));
1581     if (Arg != NewArg)
1582       Change = true;
1583   }
1584
1585   if (Change)
1586     return DagInit::get(Val, nullptr, NewArgs);
1587   return MHSd;
1588 }
1589
1590 // Applies RHS to all elements of MHS, using LHS as a temp variable.
1591 static Init *ForeachHelper(Init *LHS, Init *MHS, Init *RHS, RecTy *Type,
1592                            Record *CurRec) {
1593   if (DagInit *MHSd = dyn_cast<DagInit>(MHS))
1594     return ForeachDagApply(LHS, MHSd, RHS, CurRec);
1595
1596   if (ListInit *MHSl = dyn_cast<ListInit>(MHS)) {
1597     SmallVector<Init *, 8> NewList(MHSl->begin(), MHSl->end());
1598
1599     for (Init *&Item : NewList) {
1600       Init *NewItem = ItemApply(LHS, Item, RHS, CurRec);
1601       if (NewItem != Item)
1602         Item = NewItem;
1603     }
1604     return ListInit::get(NewList, cast<ListRecTy>(Type)->getElementType());
1605   }
1606
1607   return nullptr;
1608 }
1609
1610 // Evaluates RHS for all elements of MHS, using LHS as a temp variable.
1611 // Creates a new list with the elements that evaluated to true.
1612 static Init *FilterHelper(Init *LHS, Init *MHS, Init *RHS, RecTy *Type,
1613                           Record *CurRec) {
1614   if (ListInit *MHSl = dyn_cast<ListInit>(MHS)) {
1615     SmallVector<Init *, 8> NewList;
1616
1617     for (Init *Item : MHSl->getValues()) {
1618       Init *Include = ItemApply(LHS, Item, RHS, CurRec);
1619       if (!Include)
1620         return nullptr;
1621       if (IntInit *IncludeInt =
1622               dyn_cast_or_null<IntInit>(Include->convertInitializerTo(
1623                   IntRecTy::get(LHS->getRecordKeeper())))) {
1624         if (IncludeInt->getValue())
1625           NewList.push_back(Item);
1626       } else {
1627         return nullptr;
1628       }
1629     }
1630     return ListInit::get(NewList, cast<ListRecTy>(Type)->getElementType());
1631   }
1632
1633   return nullptr;
1634 }
1635
1636 Init *TernOpInit::Fold(Record *CurRec) const {
1637   RecordKeeper &RK = getRecordKeeper();
1638   switch (getOpcode()) {
1639   case SUBST: {
1640     DefInit *LHSd = dyn_cast<DefInit>(LHS);
1641     VarInit *LHSv = dyn_cast<VarInit>(LHS);
1642     StringInit *LHSs = dyn_cast<StringInit>(LHS);
1643
1644     DefInit *MHSd = dyn_cast<DefInit>(MHS);
1645     VarInit *MHSv = dyn_cast<VarInit>(MHS);
1646     StringInit *MHSs = dyn_cast<StringInit>(MHS);
1647
1648     DefInit *RHSd = dyn_cast<DefInit>(RHS);
1649     VarInit *RHSv = dyn_cast<VarInit>(RHS);
1650     StringInit *RHSs = dyn_cast<StringInit>(RHS);
1651
1652     if (LHSd && MHSd && RHSd) {
1653       Record *Val = RHSd->getDef();
1654       if (LHSd->getAsString() == RHSd->getAsString())
1655         Val = MHSd->getDef();
1656       return DefInit::get(Val);
1657     }
1658     if (LHSv && MHSv && RHSv) {
1659       std::string Val = std::string(RHSv->getName());
1660       if (LHSv->getAsString() == RHSv->getAsString())
1661         Val = std::string(MHSv->getName());
1662       return VarInit::get(Val, getType());
1663     }
1664     if (LHSs && MHSs && RHSs) {
1665       std::string Val = std::string(RHSs->getValue());
1666
1667       std::string::size_type found;
1668       std::string::size_type idx = 0;
1669       while (true) {
1670         found = Val.find(std::string(LHSs->getValue()), idx);
1671         if (found == std::string::npos)
1672           break;
1673         Val.replace(found, LHSs->getValue().size(),
1674                     std::string(MHSs->getValue()));
1675         idx = found + MHSs->getValue().size();
1676       }
1677
1678       return StringInit::get(RK, Val);
1679     }
1680     break;
1681   }
1682
1683   case FOREACH: {
1684     if (Init *Result = ForeachHelper(LHS, MHS, RHS, getType(), CurRec))
1685       return Result;
1686     break;
1687   }
1688
1689   case FILTER: {
1690     if (Init *Result = FilterHelper(LHS, MHS, RHS, getType(), CurRec))
1691       return Result;
1692     break;
1693   }
1694
1695   case IF: {
1696     if (IntInit *LHSi = dyn_cast_or_null<IntInit>(
1697             LHS->convertInitializerTo(IntRecTy::get(RK)))) {
1698       if (LHSi->getValue())
1699         return MHS;
1700       return RHS;
1701     }
1702     break;
1703   }
1704
1705   case DAG: {
1706     ListInit *MHSl = dyn_cast<ListInit>(MHS);
1707     ListInit *RHSl = dyn_cast<ListInit>(RHS);
1708     bool MHSok = MHSl || isa<UnsetInit>(MHS);
1709     bool RHSok = RHSl || isa<UnsetInit>(RHS);
1710
1711     if (isa<UnsetInit>(MHS) && isa<UnsetInit>(RHS))
1712       break; // Typically prevented by the parser, but might happen with template args
1713
1714     if (MHSok && RHSok && (!MHSl || !RHSl || MHSl->size() == RHSl->size())) {
1715       SmallVector<std::pair<Init *, StringInit *>, 8> Children;
1716       unsigned Size = MHSl ? MHSl->size() : RHSl->size();
1717       for (unsigned i = 0; i != Size; ++i) {
1718         Init *Node = MHSl ? MHSl->getElement(i) : UnsetInit::get(RK);
1719         Init *Name = RHSl ? RHSl->getElement(i) : UnsetInit::get(RK);
1720         if (!isa<StringInit>(Name) && !isa<UnsetInit>(Name))
1721           return const_cast<TernOpInit *>(this);
1722         Children.emplace_back(Node, dyn_cast<StringInit>(Name));
1723       }
1724       return DagInit::get(LHS, nullptr, Children);
1725     }
1726     break;
1727   }
1728
1729   case RANGE: {
1730     auto *LHSi = dyn_cast<IntInit>(LHS);
1731     auto *MHSi = dyn_cast<IntInit>(MHS);
1732     auto *RHSi = dyn_cast<IntInit>(RHS);
1733     if (!LHSi || !MHSi || !RHSi)
1734       break;
1735
1736     auto Start = LHSi->getValue();
1737     auto End = MHSi->getValue();
1738     auto Step = RHSi->getValue();
1739     if (Step == 0)
1740       PrintError(CurRec->getLoc(), "Step of !range can't be 0");
1741
1742     SmallVector<Init *, 8> Args;
1743     if (Start < End && Step > 0) {
1744       Args.reserve((End - Start) / Step);
1745       for (auto I = Start; I < End; I += Step)
1746         Args.push_back(IntInit::get(getRecordKeeper(), I));
1747     } else if (Start > End && Step < 0) {
1748       Args.reserve((Start - End) / -Step);
1749       for (auto I = Start; I > End; I += Step)
1750         Args.push_back(IntInit::get(getRecordKeeper(), I));
1751     } else {
1752       // Empty set
1753     }
1754     return ListInit::get(Args, LHSi->getType());
1755   }
1756
1757   case SUBSTR: {
1758     StringInit *LHSs = dyn_cast<StringInit>(LHS);
1759     IntInit *MHSi = dyn_cast<IntInit>(MHS);
1760     IntInit *RHSi = dyn_cast<IntInit>(RHS);
1761     if (LHSs && MHSi && RHSi) {
1762       int64_t StringSize = LHSs->getValue().size();
1763       int64_t Start = MHSi->getValue();
1764       int64_t Length = RHSi->getValue();
1765       if (Start < 0 || Start > StringSize)
1766         PrintError(CurRec->getLoc(),
1767                    Twine("!substr start position is out of range 0...") +
1768                        std::to_string(StringSize) + ": " +
1769                        std::to_string(Start));
1770       if (Length < 0)
1771         PrintError(CurRec->getLoc(), "!substr length must be nonnegative");
1772       return StringInit::get(RK, LHSs->getValue().substr(Start, Length),
1773                              LHSs->getFormat());
1774     }
1775     break;
1776   }
1777
1778   case FIND: {
1779     StringInit *LHSs = dyn_cast<StringInit>(LHS);
1780     StringInit *MHSs = dyn_cast<StringInit>(MHS);
1781     IntInit *RHSi = dyn_cast<IntInit>(RHS);
1782     if (LHSs && MHSs && RHSi) {
1783       int64_t SourceSize = LHSs->getValue().size();
1784       int64_t Start = RHSi->getValue();
1785       if (Start < 0 || Start > SourceSize)
1786         PrintError(CurRec->getLoc(),
1787                    Twine("!find start position is out of range 0...") +
1788                        std::to_string(SourceSize) + ": " +
1789                        std::to_string(Start));
1790       auto I = LHSs->getValue().find(MHSs->getValue(), Start);
1791       if (I == std::string::npos)
1792         return IntInit::get(RK, -1);
1793       return IntInit::get(RK, I);
1794     }
1795     break;
1796   }
1797
1798   case SETDAGARG: {
1799     DagInit *Dag = dyn_cast<DagInit>(LHS);
1800     if (Dag && isa<IntInit, StringInit>(MHS)) {
1801       std::string Error;
1802       auto ArgNo = getDagArgNoByKey(Dag, MHS, Error);
1803       if (!ArgNo)
1804         PrintFatalError(CurRec->getLoc(), "!setdagarg " + Error);
1805
1806       assert(*ArgNo < Dag->getNumArgs());
1807
1808       SmallVector<Init *, 8> Args(Dag->getArgs());
1809       SmallVector<StringInit *, 8> Names(Dag->getArgNames());
1810       Args[*ArgNo] = RHS;
1811       return DagInit::get(Dag->getOperator(), Dag->getName(), Args, Names);
1812     }
1813     break;
1814   }
1815
1816   case SETDAGNAME: {
1817     DagInit *Dag = dyn_cast<DagInit>(LHS);
1818     if (Dag && isa<IntInit, StringInit>(MHS)) {
1819       std::string Error;
1820       auto ArgNo = getDagArgNoByKey(Dag, MHS, Error);
1821       if (!ArgNo)
1822         PrintFatalError(CurRec->getLoc(), "!setdagname " + Error);
1823
1824       assert(*ArgNo < Dag->getNumArgs());
1825
1826       SmallVector<Init *, 8> Args(Dag->getArgs());
1827       SmallVector<StringInit *, 8> Names(Dag->getArgNames());
1828       Names[*ArgNo] = dyn_cast<StringInit>(RHS);
1829       return DagInit::get(Dag->getOperator(), Dag->getName(), Args, Names);
1830     }
1831     break;
1832   }
1833   }
1834
1835   return const_cast<TernOpInit *>(this);
1836 }
1837
1838 Init *TernOpInit::resolveReferences(Resolver &R) const {
1839   Init *lhs = LHS->resolveReferences(R);
1840
1841   if (getOpcode() == IF && lhs != LHS) {
1842     if (IntInit *Value = dyn_cast_or_null<IntInit>(
1843             lhs->convertInitializerTo(IntRecTy::get(getRecordKeeper())))) {
1844       // Short-circuit
1845       if (Value->getValue())
1846         return MHS->resolveReferences(R);
1847       return RHS->resolveReferences(R);
1848     }
1849   }
1850
1851   Init *mhs = MHS->resolveReferences(R);
1852   Init *rhs;
1853
1854   if (getOpcode() == FOREACH || getOpcode() == FILTER) {
1855     ShadowResolver SR(R);
1856     SR.addShadow(lhs);
1857     rhs = RHS->resolveReferences(SR);
1858   } else {
1859     rhs = RHS->resolveReferences(R);
1860   }
1861
1862   if (LHS != lhs || MHS != mhs || RHS != rhs)
1863     return (TernOpInit::get(getOpcode(), lhs, mhs, rhs, getType()))
1864         ->Fold(R.getCurrentRecord());
1865   return const_cast<TernOpInit *>(this);
1866 }
1867
1868 std::string TernOpInit::getAsString() const {
1869   std::string Result;
1870   bool UnquotedLHS = false;
1871   switch (getOpcode()) {
1872   case DAG: Result = "!dag"; break;
1873   case FILTER: Result = "!filter"; UnquotedLHS = true; break;
1874   case FOREACH: Result = "!foreach"; UnquotedLHS = true; break;
1875   case IF: Result = "!if"; break;
1876   case RANGE:
1877     Result = "!range";
1878     break;
1879   case SUBST: Result = "!subst"; break;
1880   case SUBSTR: Result = "!substr"; break;
1881   case FIND: Result = "!find"; break;
1882   case SETDAGARG:
1883     Result = "!setdagarg";
1884     break;
1885   case SETDAGNAME:
1886     Result = "!setdagname";
1887     break;
1888   }
1889   return (Result + "(" +
1890           (UnquotedLHS ? LHS->getAsUnquotedString() : LHS->getAsString()) +
1891           ", " + MHS->getAsString() + ", " + RHS->getAsString() + ")");
1892 }
1893
1894 static void ProfileFoldOpInit(FoldingSetNodeID &ID, Init *Start, Init *List,
1895                               Init *A, Init *B, Init *Expr, RecTy *Type) {
1896   ID.AddPointer(Start);
1897   ID.AddPointer(List);
1898   ID.AddPointer(A);
1899   ID.AddPointer(B);
1900   ID.AddPointer(Expr);
1901   ID.AddPointer(Type);
1902 }
1903
1904 FoldOpInit *FoldOpInit::get(Init *Start, Init *List, Init *A, Init *B,
1905                             Init *Expr, RecTy *Type) {
1906   FoldingSetNodeID ID;
1907   ProfileFoldOpInit(ID, Start, List, A, B, Expr, Type);
1908
1909   detail::RecordKeeperImpl &RK = Start->getRecordKeeper().getImpl();
1910   void *IP = nullptr;
1911   if (FoldOpInit *I = RK.TheFoldOpInitPool.FindNodeOrInsertPos(ID, IP))
1912     return I;
1913
1914   FoldOpInit *I = new (RK.Allocator) FoldOpInit(Start, List, A, B, Expr, Type);
1915   RK.TheFoldOpInitPool.InsertNode(I, IP);
1916   return I;
1917 }
1918
1919 void FoldOpInit::Profile(FoldingSetNodeID &ID) const {
1920   ProfileFoldOpInit(ID, Start, List, A, B, Expr, getType());
1921 }
1922
1923 Init *FoldOpInit::Fold(Record *CurRec) const {
1924   if (ListInit *LI = dyn_cast<ListInit>(List)) {
1925     Init *Accum = Start;
1926     for (Init *Elt : *LI) {
1927       MapResolver R(CurRec);
1928       R.set(A, Accum);
1929       R.set(B, Elt);
1930       Accum = Expr->resolveReferences(R);
1931     }
1932     return Accum;
1933   }
1934   return const_cast<FoldOpInit *>(this);
1935 }
1936
1937 Init *FoldOpInit::resolveReferences(Resolver &R) const {
1938   Init *NewStart = Start->resolveReferences(R);
1939   Init *NewList = List->resolveReferences(R);
1940   ShadowResolver SR(R);
1941   SR.addShadow(A);
1942   SR.addShadow(B);
1943   Init *NewExpr = Expr->resolveReferences(SR);
1944
1945   if (Start == NewStart && List == NewList && Expr == NewExpr)
1946     return const_cast<FoldOpInit *>(this);
1947
1948   return get(NewStart, NewList, A, B, NewExpr, getType())
1949       ->Fold(R.getCurrentRecord());
1950 }
1951
1952 Init *FoldOpInit::getBit(unsigned Bit) const {
1953   return VarBitInit::get(const_cast<FoldOpInit *>(this), Bit);
1954 }
1955
1956 std::string FoldOpInit::getAsString() const {
1957   return (Twine("!foldl(") + Start->getAsString() + ", " + List->getAsString() +
1958           ", " + A->getAsUnquotedString() + ", " + B->getAsUnquotedString() +
1959           ", " + Expr->getAsString() + ")")
1960       .str();
1961 }
1962
1963 static void ProfileIsAOpInit(FoldingSetNodeID &ID, RecTy *CheckType,
1964                              Init *Expr) {
1965   ID.AddPointer(CheckType);
1966   ID.AddPointer(Expr);
1967 }
1968
1969 IsAOpInit *IsAOpInit::get(RecTy *CheckType, Init *Expr) {
1970
1971   FoldingSetNodeID ID;
1972   ProfileIsAOpInit(ID, CheckType, Expr);
1973
1974   detail::RecordKeeperImpl &RK = Expr->getRecordKeeper().getImpl();
1975   void *IP = nullptr;
1976   if (IsAOpInit *I = RK.TheIsAOpInitPool.FindNodeOrInsertPos(ID, IP))
1977     return I;
1978
1979   IsAOpInit *I = new (RK.Allocator) IsAOpInit(CheckType, Expr);
1980   RK.TheIsAOpInitPool.InsertNode(I, IP);
1981   return I;
1982 }
1983
1984 void IsAOpInit::Profile(FoldingSetNodeID &ID) const {
1985   ProfileIsAOpInit(ID, CheckType, Expr);
1986 }
1987
1988 Init *IsAOpInit::Fold() const {
1989   if (TypedInit *TI = dyn_cast<TypedInit>(Expr)) {
1990     // Is the expression type known to be (a subclass of) the desired type?
1991     if (TI->getType()->typeIsConvertibleTo(CheckType))
1992       return IntInit::get(getRecordKeeper(), 1);
1993
1994     if (isa<RecordRecTy>(CheckType)) {
1995       // If the target type is not a subclass of the expression type, or if
1996       // the expression has fully resolved to a record, we know that it can't
1997       // be of the required type.
1998       if (!CheckType->typeIsConvertibleTo(TI->getType()) || isa<DefInit>(Expr))
1999         return IntInit::get(getRecordKeeper(), 0);
2000     } else {
2001       // We treat non-record types as not castable.
2002       return IntInit::get(getRecordKeeper(), 0);
2003     }
2004   }
2005   return const_cast<IsAOpInit *>(this);
2006 }
2007
2008 Init *IsAOpInit::resolveReferences(Resolver &R) const {
2009   Init *NewExpr = Expr->resolveReferences(R);
2010   if (Expr != NewExpr)
2011     return get(CheckType, NewExpr)->Fold();
2012   return const_cast<IsAOpInit *>(this);
2013 }
2014
2015 Init *IsAOpInit::getBit(unsigned Bit) const {
2016   return VarBitInit::get(const_cast<IsAOpInit *>(this), Bit);
2017 }
2018
2019 std::string IsAOpInit::getAsString() const {
2020   return (Twine("!isa<") + CheckType->getAsString() + ">(" +
2021           Expr->getAsString() + ")")
2022       .str();
2023 }
2024
2025 static void ProfileExistsOpInit(FoldingSetNodeID &ID, RecTy *CheckType,
2026                                 Init *Expr) {
2027   ID.AddPointer(CheckType);
2028   ID.AddPointer(Expr);
2029 }
2030
2031 ExistsOpInit *ExistsOpInit::get(RecTy *CheckType, Init *Expr) {
2032   FoldingSetNodeID ID;
2033   ProfileExistsOpInit(ID, CheckType, Expr);
2034
2035   detail::RecordKeeperImpl &RK = Expr->getRecordKeeper().getImpl();
2036   void *IP = nullptr;
2037   if (ExistsOpInit *I = RK.TheExistsOpInitPool.FindNodeOrInsertPos(ID, IP))
2038     return I;
2039
2040   ExistsOpInit *I = new (RK.Allocator) ExistsOpInit(CheckType, Expr);
2041   RK.TheExistsOpInitPool.InsertNode(I, IP);
2042   return I;
2043 }
2044
2045 void ExistsOpInit::Profile(FoldingSetNodeID &ID) const {
2046   ProfileExistsOpInit(ID, CheckType, Expr);
2047 }
2048
2049 Init *ExistsOpInit::Fold(Record *CurRec, bool IsFinal) const {
2050   if (StringInit *Name = dyn_cast<StringInit>(Expr)) {
2051
2052     // Look up all defined records to see if we can find one.
2053     Record *D = CheckType->getRecordKeeper().getDef(Name->getValue());
2054     if (D) {
2055       // Check if types are compatible.
2056       return IntInit::get(getRecordKeeper(),
2057                           DefInit::get(D)->getType()->typeIsA(CheckType));
2058     }
2059
2060     if (CurRec) {
2061       // Self-references are allowed, but their resolution is delayed until
2062       // the final resolve to ensure that we get the correct type for them.
2063       auto *Anonymous = dyn_cast<AnonymousNameInit>(CurRec->getNameInit());
2064       if (Name == CurRec->getNameInit() ||
2065           (Anonymous && Name == Anonymous->getNameInit())) {
2066         if (!IsFinal)
2067           return const_cast<ExistsOpInit *>(this);
2068
2069         // No doubt that there exists a record, so we should check if types are
2070         // compatible.
2071         return IntInit::get(getRecordKeeper(),
2072                             CurRec->getType()->typeIsA(CheckType));
2073       }
2074     }
2075
2076     if (IsFinal)
2077       return IntInit::get(getRecordKeeper(), 0);
2078     return const_cast<ExistsOpInit *>(this);
2079   }
2080   return const_cast<ExistsOpInit *>(this);
2081 }
2082
2083 Init *ExistsOpInit::resolveReferences(Resolver &R) const {
2084   Init *NewExpr = Expr->resolveReferences(R);
2085   if (Expr != NewExpr || R.isFinal())
2086     return get(CheckType, NewExpr)->Fold(R.getCurrentRecord(), R.isFinal());
2087   return const_cast<ExistsOpInit *>(this);
2088 }
2089
2090 Init *ExistsOpInit::getBit(unsigned Bit) const {
2091   return VarBitInit::get(const_cast<ExistsOpInit *>(this), Bit);
2092 }
2093
2094 std::string ExistsOpInit::getAsString() const {
2095   return (Twine("!exists<") + CheckType->getAsString() + ">(" +
2096           Expr->getAsString() + ")")
2097       .str();
2098 }
2099
2100 RecTy *TypedInit::getFieldType(StringInit *FieldName) const {
2101   if (RecordRecTy *RecordType = dyn_cast<RecordRecTy>(getType())) {
2102     for (Record *Rec : RecordType->getClasses()) {
2103       if (RecordVal *Field = Rec->getValue(FieldName))
2104         return Field->getType();
2105     }
2106   }
2107   return nullptr;
2108 }
2109
2110 Init *
2111 TypedInit::convertInitializerTo(RecTy *Ty) const {
2112   if (getType() == Ty || getType()->typeIsA(Ty))
2113     return const_cast<TypedInit *>(this);
2114
2115   if (isa<BitRecTy>(getType()) && isa<BitsRecTy>(Ty) &&
2116       cast<BitsRecTy>(Ty)->getNumBits() == 1)
2117     return BitsInit::get(getRecordKeeper(), {const_cast<TypedInit *>(this)});
2118
2119   return nullptr;
2120 }
2121
2122 Init *TypedInit::convertInitializerBitRange(ArrayRef<unsigned> Bits) const {
2123   BitsRecTy *T = dyn_cast<BitsRecTy>(getType());
2124   if (!T) return nullptr;  // Cannot subscript a non-bits variable.
2125   unsigned NumBits = T->getNumBits();
2126
2127   SmallVector<Init *, 16> NewBits;
2128   NewBits.reserve(Bits.size());
2129   for (unsigned Bit : Bits) {
2130     if (Bit >= NumBits)
2131       return nullptr;
2132
2133     NewBits.push_back(VarBitInit::get(const_cast<TypedInit *>(this), Bit));
2134   }
2135   return BitsInit::get(getRecordKeeper(), NewBits);
2136 }
2137
2138 Init *TypedInit::getCastTo(RecTy *Ty) const {
2139   // Handle the common case quickly
2140   if (getType() == Ty || getType()->typeIsA(Ty))
2141     return const_cast<TypedInit *>(this);
2142
2143   if (Init *Converted = convertInitializerTo(Ty)) {
2144     assert(!isa<TypedInit>(Converted) ||
2145            cast<TypedInit>(Converted)->getType()->typeIsA(Ty));
2146     return Converted;
2147   }
2148
2149   if (!getType()->typeIsConvertibleTo(Ty))
2150     return nullptr;
2151
2152   return UnOpInit::get(UnOpInit::CAST, const_cast<TypedInit *>(this), Ty)
2153       ->Fold(nullptr);
2154 }
2155
2156 VarInit *VarInit::get(StringRef VN, RecTy *T) {
2157   Init *Value = StringInit::get(T->getRecordKeeper(), VN);
2158   return VarInit::get(Value, T);
2159 }
2160
2161 VarInit *VarInit::get(Init *VN, RecTy *T) {
2162   detail::RecordKeeperImpl &RK = T->getRecordKeeper().getImpl();
2163   VarInit *&I = RK.TheVarInitPool[std::make_pair(T, VN)];
2164   if (!I)
2165     I = new (RK.Allocator) VarInit(VN, T);
2166   return I;
2167 }
2168
2169 StringRef VarInit::getName() const {
2170   StringInit *NameString = cast<StringInit>(getNameInit());
2171   return NameString->getValue();
2172 }
2173
2174 Init *VarInit::getBit(unsigned Bit) const {
2175   if (getType() == BitRecTy::get(getRecordKeeper()))
2176     return const_cast<VarInit*>(this);
2177   return VarBitInit::get(const_cast<VarInit*>(this), Bit);
2178 }
2179
2180 Init *VarInit::resolveReferences(Resolver &R) const {
2181   if (Init *Val = R.resolve(VarName))
2182     return Val;
2183   return const_cast<VarInit *>(this);
2184 }
2185
2186 VarBitInit *VarBitInit::get(TypedInit *T, unsigned B) {
2187   detail::RecordKeeperImpl &RK = T->getRecordKeeper().getImpl();
2188   VarBitInit *&I = RK.TheVarBitInitPool[std::make_pair(T, B)];
2189   if (!I)
2190     I = new (RK.Allocator) VarBitInit(T, B);
2191   return I;
2192 }
2193
2194 std::string VarBitInit::getAsString() const {
2195   return TI->getAsString() + "{" + utostr(Bit) + "}";
2196 }
2197
2198 Init *VarBitInit::resolveReferences(Resolver &R) const {
2199   Init *I = TI->resolveReferences(R);
2200   if (TI != I)
2201     return I->getBit(getBitNum());
2202
2203   return const_cast<VarBitInit*>(this);
2204 }
2205
2206 DefInit::DefInit(Record *D)
2207     : TypedInit(IK_DefInit, D->getType()), Def(D) {}
2208
2209 DefInit *DefInit::get(Record *R) {
2210   return R->getDefInit();
2211 }
2212
2213 Init *DefInit::convertInitializerTo(RecTy *Ty) const {
2214   if (auto *RRT = dyn_cast<RecordRecTy>(Ty))
2215     if (getType()->typeIsConvertibleTo(RRT))
2216       return const_cast<DefInit *>(this);
2217   return nullptr;
2218 }
2219
2220 RecTy *DefInit::getFieldType(StringInit *FieldName) const {
2221   if (const RecordVal *RV = Def->getValue(FieldName))
2222     return RV->getType();
2223   return nullptr;
2224 }
2225
2226 std::string DefInit::getAsString() const { return std::string(Def->getName()); }
2227
2228 static void ProfileVarDefInit(FoldingSetNodeID &ID, Record *Class,
2229                               ArrayRef<ArgumentInit *> Args) {
2230   ID.AddInteger(Args.size());
2231   ID.AddPointer(Class);
2232
2233   for (Init *I : Args)
2234     ID.AddPointer(I);
2235 }
2236
2237 VarDefInit::VarDefInit(Record *Class, unsigned N)
2238     : TypedInit(IK_VarDefInit, RecordRecTy::get(Class)), Class(Class),
2239       NumArgs(N) {}
2240
2241 VarDefInit *VarDefInit::get(Record *Class, ArrayRef<ArgumentInit *> Args) {
2242   FoldingSetNodeID ID;
2243   ProfileVarDefInit(ID, Class, Args);
2244
2245   detail::RecordKeeperImpl &RK = Class->getRecords().getImpl();
2246   void *IP = nullptr;
2247   if (VarDefInit *I = RK.TheVarDefInitPool.FindNodeOrInsertPos(ID, IP))
2248     return I;
2249
2250   void *Mem = RK.Allocator.Allocate(
2251       totalSizeToAlloc<ArgumentInit *>(Args.size()), alignof(VarDefInit));
2252   VarDefInit *I = new (Mem) VarDefInit(Class, Args.size());
2253   std::uninitialized_copy(Args.begin(), Args.end(),
2254                           I->getTrailingObjects<ArgumentInit *>());
2255   RK.TheVarDefInitPool.InsertNode(I, IP);
2256   return I;
2257 }
2258
2259 void VarDefInit::Profile(FoldingSetNodeID &ID) const {
2260   ProfileVarDefInit(ID, Class, args());
2261 }
2262
2263 DefInit *VarDefInit::instantiate() {
2264   if (!Def) {
2265     RecordKeeper &Records = Class->getRecords();
2266     auto NewRecOwner =
2267         std::make_unique<Record>(Records.getNewAnonymousName(), Class->getLoc(),
2268                                  Records, Record::RK_AnonymousDef);
2269     Record *NewRec = NewRecOwner.get();
2270
2271     // Copy values from class to instance
2272     for (const RecordVal &Val : Class->getValues())
2273       NewRec->addValue(Val);
2274
2275     // Copy assertions from class to instance.
2276     NewRec->appendAssertions(Class);
2277
2278     // Copy dumps from class to instance.
2279     NewRec->appendDumps(Class);
2280
2281     // Substitute and resolve template arguments
2282     ArrayRef<Init *> TArgs = Class->getTemplateArgs();
2283     MapResolver R(NewRec);
2284
2285     for (unsigned I = 0, E = TArgs.size(); I != E; ++I) {
2286       R.set(TArgs[I], NewRec->getValue(TArgs[I])->getValue());
2287       NewRec->removeValue(TArgs[I]);
2288     }
2289
2290     for (auto *Arg : args()) {
2291       if (Arg->isPositional())
2292         R.set(TArgs[Arg->getIndex()], Arg->getValue());
2293       if (Arg->isNamed())
2294         R.set(Arg->getName(), Arg->getValue());
2295     }
2296
2297     NewRec->resolveReferences(R);
2298
2299     // Add superclasses.
2300     ArrayRef<std::pair<Record *, SMRange>> SCs = Class->getSuperClasses();
2301     for (const auto &SCPair : SCs)
2302       NewRec->addSuperClass(SCPair.first, SCPair.second);
2303
2304     NewRec->addSuperClass(Class,
2305                           SMRange(Class->getLoc().back(),
2306                                   Class->getLoc().back()));
2307
2308     // Resolve internal references and store in record keeper
2309     NewRec->resolveReferences();
2310     Records.addDef(std::move(NewRecOwner));
2311
2312     // Check the assertions.
2313     NewRec->checkRecordAssertions();
2314
2315     // Check the assertions.
2316     NewRec->emitRecordDumps();
2317
2318     Def = DefInit::get(NewRec);
2319   }
2320
2321   return Def;
2322 }
2323
2324 Init *VarDefInit::resolveReferences(Resolver &R) const {
2325   TrackUnresolvedResolver UR(&R);
2326   bool Changed = false;
2327   SmallVector<ArgumentInit *, 8> NewArgs;
2328   NewArgs.reserve(args_size());
2329
2330   for (ArgumentInit *Arg : args()) {
2331     auto *NewArg = cast<ArgumentInit>(Arg->resolveReferences(UR));
2332     NewArgs.push_back(NewArg);
2333     Changed |= NewArg != Arg;
2334   }
2335
2336   if (Changed) {
2337     auto New = VarDefInit::get(Class, NewArgs);
2338     if (!UR.foundUnresolved())
2339       return New->instantiate();
2340     return New;
2341   }
2342   return const_cast<VarDefInit *>(this);
2343 }
2344
2345 Init *VarDefInit::Fold() const {
2346   if (Def)
2347     return Def;
2348
2349   TrackUnresolvedResolver R;
2350   for (Init *Arg : args())
2351     Arg->resolveReferences(R);
2352
2353   if (!R.foundUnresolved())
2354     return const_cast<VarDefInit *>(this)->instantiate();
2355   return const_cast<VarDefInit *>(this);
2356 }
2357
2358 std::string VarDefInit::getAsString() const {
2359   std::string Result = Class->getNameInitAsString() + "<";
2360   const char *sep = "";
2361   for (Init *Arg : args()) {
2362     Result += sep;
2363     sep = ", ";
2364     Result += Arg->getAsString();
2365   }
2366   return Result + ">";
2367 }
2368
2369 FieldInit *FieldInit::get(Init *R, StringInit *FN) {
2370   detail::RecordKeeperImpl &RK = R->getRecordKeeper().getImpl();
2371   FieldInit *&I = RK.TheFieldInitPool[std::make_pair(R, FN)];
2372   if (!I)
2373     I = new (RK.Allocator) FieldInit(R, FN);
2374   return I;
2375 }
2376
2377 Init *FieldInit::getBit(unsigned Bit) const {
2378   if (getType() == BitRecTy::get(getRecordKeeper()))
2379     return const_cast<FieldInit*>(this);
2380   return VarBitInit::get(const_cast<FieldInit*>(this), Bit);
2381 }
2382
2383 Init *FieldInit::resolveReferences(Resolver &R) const {
2384   Init *NewRec = Rec->resolveReferences(R);
2385   if (NewRec != Rec)
2386     return FieldInit::get(NewRec, FieldName)->Fold(R.getCurrentRecord());
2387   return const_cast<FieldInit *>(this);
2388 }
2389
2390 Init *FieldInit::Fold(Record *CurRec) const {
2391   if (DefInit *DI = dyn_cast<DefInit>(Rec)) {
2392     Record *Def = DI->getDef();
2393     if (Def == CurRec)
2394       PrintFatalError(CurRec->getLoc(),
2395                       Twine("Attempting to access field '") +
2396                       FieldName->getAsUnquotedString() + "' of '" +
2397                       Rec->getAsString() + "' is a forbidden self-reference");
2398     Init *FieldVal = Def->getValue(FieldName)->getValue();
2399     if (FieldVal->isConcrete())
2400       return FieldVal;
2401   }
2402   return const_cast<FieldInit *>(this);
2403 }
2404
2405 bool FieldInit::isConcrete() const {
2406   if (DefInit *DI = dyn_cast<DefInit>(Rec)) {
2407     Init *FieldVal = DI->getDef()->getValue(FieldName)->getValue();
2408     return FieldVal->isConcrete();
2409   }
2410   return false;
2411 }
2412
2413 static void ProfileCondOpInit(FoldingSetNodeID &ID,
2414                              ArrayRef<Init *> CondRange,
2415                              ArrayRef<Init *> ValRange,
2416                              const RecTy *ValType) {
2417   assert(CondRange.size() == ValRange.size() &&
2418          "Number of conditions and values must match!");
2419   ID.AddPointer(ValType);
2420   ArrayRef<Init *>::iterator Case = CondRange.begin();
2421   ArrayRef<Init *>::iterator Val = ValRange.begin();
2422
2423   while (Case != CondRange.end()) {
2424     ID.AddPointer(*Case++);
2425     ID.AddPointer(*Val++);
2426   }
2427 }
2428
2429 void CondOpInit::Profile(FoldingSetNodeID &ID) const {
2430   ProfileCondOpInit(ID, ArrayRef(getTrailingObjects<Init *>(), NumConds),
2431                     ArrayRef(getTrailingObjects<Init *>() + NumConds, NumConds),
2432                     ValType);
2433 }
2434
2435 CondOpInit *CondOpInit::get(ArrayRef<Init *> CondRange,
2436                             ArrayRef<Init *> ValRange, RecTy *Ty) {
2437   assert(CondRange.size() == ValRange.size() &&
2438          "Number of conditions and values must match!");
2439
2440   FoldingSetNodeID ID;
2441   ProfileCondOpInit(ID, CondRange, ValRange, Ty);
2442
2443   detail::RecordKeeperImpl &RK = Ty->getRecordKeeper().getImpl();
2444   void *IP = nullptr;
2445   if (CondOpInit *I = RK.TheCondOpInitPool.FindNodeOrInsertPos(ID, IP))
2446     return I;
2447
2448   void *Mem = RK.Allocator.Allocate(
2449       totalSizeToAlloc<Init *>(2 * CondRange.size()), alignof(BitsInit));
2450   CondOpInit *I = new(Mem) CondOpInit(CondRange.size(), Ty);
2451
2452   std::uninitialized_copy(CondRange.begin(), CondRange.end(),
2453                           I->getTrailingObjects<Init *>());
2454   std::uninitialized_copy(ValRange.begin(), ValRange.end(),
2455                           I->getTrailingObjects<Init *>()+CondRange.size());
2456   RK.TheCondOpInitPool.InsertNode(I, IP);
2457   return I;
2458 }
2459
2460 Init *CondOpInit::resolveReferences(Resolver &R) const {
2461   SmallVector<Init*, 4> NewConds;
2462   bool Changed = false;
2463   for (const Init *Case : getConds()) {
2464     Init *NewCase = Case->resolveReferences(R);
2465     NewConds.push_back(NewCase);
2466     Changed |= NewCase != Case;
2467   }
2468
2469   SmallVector<Init*, 4> NewVals;
2470   for (const Init *Val : getVals()) {
2471     Init *NewVal = Val->resolveReferences(R);
2472     NewVals.push_back(NewVal);
2473     Changed |= NewVal != Val;
2474   }
2475
2476   if (Changed)
2477     return (CondOpInit::get(NewConds, NewVals,
2478             getValType()))->Fold(R.getCurrentRecord());
2479
2480   return const_cast<CondOpInit *>(this);
2481 }
2482
2483 Init *CondOpInit::Fold(Record *CurRec) const {
2484   RecordKeeper &RK = getRecordKeeper();
2485   for ( unsigned i = 0; i < NumConds; ++i) {
2486     Init *Cond = getCond(i);
2487     Init *Val = getVal(i);
2488
2489     if (IntInit *CondI = dyn_cast_or_null<IntInit>(
2490             Cond->convertInitializerTo(IntRecTy::get(RK)))) {
2491       if (CondI->getValue())
2492         return Val->convertInitializerTo(getValType());
2493     } else {
2494       return const_cast<CondOpInit *>(this);
2495     }
2496   }
2497
2498   PrintFatalError(CurRec->getLoc(),
2499                   CurRec->getNameInitAsString() +
2500                   " does not have any true condition in:" +
2501                   this->getAsString());
2502   return nullptr;
2503 }
2504
2505 bool CondOpInit::isConcrete() const {
2506   for (const Init *Case : getConds())
2507     if (!Case->isConcrete())
2508       return false;
2509
2510   for (const Init *Val : getVals())
2511     if (!Val->isConcrete())
2512       return false;
2513
2514   return true;
2515 }
2516
2517 bool CondOpInit::isComplete() const {
2518   for (const Init *Case : getConds())
2519     if (!Case->isComplete())
2520       return false;
2521
2522   for (const Init *Val : getVals())
2523     if (!Val->isConcrete())
2524       return false;
2525
2526   return true;
2527 }
2528
2529 std::string CondOpInit::getAsString() const {
2530   std::string Result = "!cond(";
2531   for (unsigned i = 0; i < getNumConds(); i++) {
2532     Result += getCond(i)->getAsString() + ": ";
2533     Result += getVal(i)->getAsString();
2534     if (i != getNumConds()-1)
2535       Result += ", ";
2536   }
2537   return Result + ")";
2538 }
2539
2540 Init *CondOpInit::getBit(unsigned Bit) const {
2541   return VarBitInit::get(const_cast<CondOpInit *>(this), Bit);
2542 }
2543
2544 static void ProfileDagInit(FoldingSetNodeID &ID, Init *V, StringInit *VN,
2545                            ArrayRef<Init *> ArgRange,
2546                            ArrayRef<StringInit *> NameRange) {
2547   ID.AddPointer(V);
2548   ID.AddPointer(VN);
2549
2550   ArrayRef<Init *>::iterator Arg = ArgRange.begin();
2551   ArrayRef<StringInit *>::iterator Name = NameRange.begin();
2552   while (Arg != ArgRange.end()) {
2553     assert(Name != NameRange.end() && "Arg name underflow!");
2554     ID.AddPointer(*Arg++);
2555     ID.AddPointer(*Name++);
2556   }
2557   assert(Name == NameRange.end() && "Arg name overflow!");
2558 }
2559
2560 DagInit *DagInit::get(Init *V, StringInit *VN, ArrayRef<Init *> ArgRange,
2561                       ArrayRef<StringInit *> NameRange) {
2562   assert(ArgRange.size() == NameRange.size());
2563   FoldingSetNodeID ID;
2564   ProfileDagInit(ID, V, VN, ArgRange, NameRange);
2565
2566   detail::RecordKeeperImpl &RK = V->getRecordKeeper().getImpl();
2567   void *IP = nullptr;
2568   if (DagInit *I = RK.TheDagInitPool.FindNodeOrInsertPos(ID, IP))
2569     return I;
2570
2571   void *Mem = RK.Allocator.Allocate(
2572       totalSizeToAlloc<Init *, StringInit *>(ArgRange.size(), NameRange.size()),
2573       alignof(BitsInit));
2574   DagInit *I = new (Mem) DagInit(V, VN, ArgRange.size(), NameRange.size());
2575   std::uninitialized_copy(ArgRange.begin(), ArgRange.end(),
2576                           I->getTrailingObjects<Init *>());
2577   std::uninitialized_copy(NameRange.begin(), NameRange.end(),
2578                           I->getTrailingObjects<StringInit *>());
2579   RK.TheDagInitPool.InsertNode(I, IP);
2580   return I;
2581 }
2582
2583 DagInit *
2584 DagInit::get(Init *V, StringInit *VN,
2585              ArrayRef<std::pair<Init*, StringInit*>> args) {
2586   SmallVector<Init *, 8> Args;
2587   SmallVector<StringInit *, 8> Names;
2588
2589   for (const auto &Arg : args) {
2590     Args.push_back(Arg.first);
2591     Names.push_back(Arg.second);
2592   }
2593
2594   return DagInit::get(V, VN, Args, Names);
2595 }
2596
2597 void DagInit::Profile(FoldingSetNodeID &ID) const {
2598   ProfileDagInit(ID, Val, ValName,
2599                  ArrayRef(getTrailingObjects<Init *>(), NumArgs),
2600                  ArrayRef(getTrailingObjects<StringInit *>(), NumArgNames));
2601 }
2602
2603 Record *DagInit::getOperatorAsDef(ArrayRef<SMLoc> Loc) const {
2604   if (DefInit *DefI = dyn_cast<DefInit>(Val))
2605     return DefI->getDef();
2606   PrintFatalError(Loc, "Expected record as operator");
2607   return nullptr;
2608 }
2609
2610 std::optional<unsigned> DagInit::getArgNo(StringRef Name) const {
2611   for (unsigned i = 0, e = getNumArgs(); i < e; ++i) {
2612     StringInit *ArgName = getArgName(i);
2613     if (ArgName && ArgName->getValue() == Name)
2614       return i;
2615   }
2616   return std::nullopt;
2617 }
2618
2619 Init *DagInit::resolveReferences(Resolver &R) const {
2620   SmallVector<Init*, 8> NewArgs;
2621   NewArgs.reserve(arg_size());
2622   bool ArgsChanged = false;
2623   for (const Init *Arg : getArgs()) {
2624     Init *NewArg = Arg->resolveReferences(R);
2625     NewArgs.push_back(NewArg);
2626     ArgsChanged |= NewArg != Arg;
2627   }
2628
2629   Init *Op = Val->resolveReferences(R);
2630   if (Op != Val || ArgsChanged)
2631     return DagInit::get(Op, ValName, NewArgs, getArgNames());
2632
2633   return const_cast<DagInit *>(this);
2634 }
2635
2636 bool DagInit::isConcrete() const {
2637   if (!Val->isConcrete())
2638     return false;
2639   for (const Init *Elt : getArgs()) {
2640     if (!Elt->isConcrete())
2641       return false;
2642   }
2643   return true;
2644 }
2645
2646 std::string DagInit::getAsString() const {
2647   std::string Result = "(" + Val->getAsString();
2648   if (ValName)
2649     Result += ":" + ValName->getAsUnquotedString();
2650   if (!arg_empty()) {
2651     Result += " " + getArg(0)->getAsString();
2652     if (getArgName(0)) Result += ":$" + getArgName(0)->getAsUnquotedString();
2653     for (unsigned i = 1, e = getNumArgs(); i != e; ++i) {
2654       Result += ", " + getArg(i)->getAsString();
2655       if (getArgName(i)) Result += ":$" + getArgName(i)->getAsUnquotedString();
2656     }
2657   }
2658   return Result + ")";
2659 }
2660
2661 //===----------------------------------------------------------------------===//
2662 //    Other implementations
2663 //===----------------------------------------------------------------------===//
2664
2665 RecordVal::RecordVal(Init *N, RecTy *T, FieldKind K)
2666     : Name(N), TyAndKind(T, K) {
2667   setValue(UnsetInit::get(N->getRecordKeeper()));
2668   assert(Value && "Cannot create unset value for current type!");
2669 }
2670
2671 // This constructor accepts the same arguments as the above, but also
2672 // a source location.
2673 RecordVal::RecordVal(Init *N, SMLoc Loc, RecTy *T, FieldKind K)
2674     : Name(N), Loc(Loc), TyAndKind(T, K) {
2675   setValue(UnsetInit::get(N->getRecordKeeper()));
2676   assert(Value && "Cannot create unset value for current type!");
2677 }
2678
2679 StringRef RecordVal::getName() const {
2680   return cast<StringInit>(getNameInit())->getValue();
2681 }
2682
2683 std::string RecordVal::getPrintType() const {
2684   if (getType() == StringRecTy::get(getRecordKeeper())) {
2685     if (auto *StrInit = dyn_cast<StringInit>(Value)) {
2686       if (StrInit->hasCodeFormat())
2687         return "code";
2688       else
2689         return "string";
2690     } else {
2691       return "string";
2692     }
2693   } else {
2694     return TyAndKind.getPointer()->getAsString();
2695   }
2696 }
2697
2698 bool RecordVal::setValue(Init *V) {
2699   if (V) {
2700     Value = V->getCastTo(getType());
2701     if (Value) {
2702       assert(!isa<TypedInit>(Value) ||
2703              cast<TypedInit>(Value)->getType()->typeIsA(getType()));
2704       if (BitsRecTy *BTy = dyn_cast<BitsRecTy>(getType())) {
2705         if (!isa<BitsInit>(Value)) {
2706           SmallVector<Init *, 64> Bits;
2707           Bits.reserve(BTy->getNumBits());
2708           for (unsigned I = 0, E = BTy->getNumBits(); I < E; ++I)
2709             Bits.push_back(Value->getBit(I));
2710           Value = BitsInit::get(V->getRecordKeeper(), Bits);
2711         }
2712       }
2713     }
2714     return Value == nullptr;
2715   }
2716   Value = nullptr;
2717   return false;
2718 }
2719
2720 // This version of setValue takes a source location and resets the
2721 // location in the RecordVal.
2722 bool RecordVal::setValue(Init *V, SMLoc NewLoc) {
2723   Loc = NewLoc;
2724   if (V) {
2725     Value = V->getCastTo(getType());
2726     if (Value) {
2727       assert(!isa<TypedInit>(Value) ||
2728              cast<TypedInit>(Value)->getType()->typeIsA(getType()));
2729       if (BitsRecTy *BTy = dyn_cast<BitsRecTy>(getType())) {
2730         if (!isa<BitsInit>(Value)) {
2731           SmallVector<Init *, 64> Bits;
2732           Bits.reserve(BTy->getNumBits());
2733           for (unsigned I = 0, E = BTy->getNumBits(); I < E; ++I)
2734             Bits.push_back(Value->getBit(I));
2735           Value = BitsInit::get(getRecordKeeper(), Bits);
2736         }
2737       }
2738     }
2739     return Value == nullptr;
2740   }
2741   Value = nullptr;
2742   return false;
2743 }
2744
2745 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2746 #include "llvm/TableGen/Record.h"
2747 LLVM_DUMP_METHOD void RecordVal::dump() const { errs() << *this; }
2748 #endif
2749
2750 void RecordVal::print(raw_ostream &OS, bool PrintSem) const {
2751   if (isNonconcreteOK()) OS << "field ";
2752   OS << getPrintType() << " " << getNameInitAsString();
2753
2754   if (getValue())
2755     OS << " = " << *getValue();
2756
2757   if (PrintSem) OS << ";\n";
2758 }
2759
2760 void Record::updateClassLoc(SMLoc Loc) {
2761   assert(Locs.size() == 1);
2762   ForwardDeclarationLocs.push_back(Locs.front());
2763
2764   Locs.clear();
2765   Locs.push_back(Loc);
2766 }
2767
2768 void Record::checkName() {
2769   // Ensure the record name has string type.
2770   const TypedInit *TypedName = cast<const TypedInit>(Name);
2771   if (!isa<StringRecTy>(TypedName->getType()))
2772     PrintFatalError(getLoc(), Twine("Record name '") + Name->getAsString() +
2773                                   "' is not a string!");
2774 }
2775
2776 RecordRecTy *Record::getType() {
2777   SmallVector<Record *, 4> DirectSCs;
2778   getDirectSuperClasses(DirectSCs);
2779   return RecordRecTy::get(TrackedRecords, DirectSCs);
2780 }
2781
2782 DefInit *Record::getDefInit() {
2783   if (!CorrespondingDefInit) {
2784     CorrespondingDefInit =
2785         new (TrackedRecords.getImpl().Allocator) DefInit(this);
2786   }
2787   return CorrespondingDefInit;
2788 }
2789
2790 unsigned Record::getNewUID(RecordKeeper &RK) {
2791   return RK.getImpl().LastRecordID++;
2792 }
2793
2794 void Record::setName(Init *NewName) {
2795   Name = NewName;
2796   checkName();
2797   // DO NOT resolve record values to the name at this point because
2798   // there might be default values for arguments of this def.  Those
2799   // arguments might not have been resolved yet so we don't want to
2800   // prematurely assume values for those arguments were not passed to
2801   // this def.
2802   //
2803   // Nonetheless, it may be that some of this Record's values
2804   // reference the record name.  Indeed, the reason for having the
2805   // record name be an Init is to provide this flexibility.  The extra
2806   // resolve steps after completely instantiating defs takes care of
2807   // this.  See TGParser::ParseDef and TGParser::ParseDefm.
2808 }
2809
2810 // NOTE for the next two functions:
2811 // Superclasses are in post-order, so the final one is a direct
2812 // superclass. All of its transitive superclases immediately precede it,
2813 // so we can step through the direct superclasses in reverse order.
2814
2815 bool Record::hasDirectSuperClass(const Record *Superclass) const {
2816   ArrayRef<std::pair<Record *, SMRange>> SCs = getSuperClasses();
2817
2818   for (int I = SCs.size() - 1; I >= 0; --I) {
2819     const Record *SC = SCs[I].first;
2820     if (SC == Superclass)
2821       return true;
2822     I -= SC->getSuperClasses().size();
2823   }
2824
2825   return false;
2826 }
2827
2828 void Record::getDirectSuperClasses(SmallVectorImpl<Record *> &Classes) const {
2829   ArrayRef<std::pair<Record *, SMRange>> SCs = getSuperClasses();
2830
2831   while (!SCs.empty()) {
2832     Record *SC = SCs.back().first;
2833     SCs = SCs.drop_back(1 + SC->getSuperClasses().size());
2834     Classes.push_back(SC);
2835   }
2836 }
2837
2838 void Record::resolveReferences(Resolver &R, const RecordVal *SkipVal) {
2839   Init *OldName = getNameInit();
2840   Init *NewName = Name->resolveReferences(R);
2841   if (NewName != OldName) {
2842     // Re-register with RecordKeeper.
2843     setName(NewName);
2844   }
2845
2846   // Resolve the field values.
2847   for (RecordVal &Value : Values) {
2848     if (SkipVal == &Value) // Skip resolve the same field as the given one
2849       continue;
2850     if (Init *V = Value.getValue()) {
2851       Init *VR = V->resolveReferences(R);
2852       if (Value.setValue(VR)) {
2853         std::string Type;
2854         if (TypedInit *VRT = dyn_cast<TypedInit>(VR))
2855           Type =
2856               (Twine("of type '") + VRT->getType()->getAsString() + "' ").str();
2857         PrintFatalError(
2858             getLoc(),
2859             Twine("Invalid value ") + Type + "found when setting field '" +
2860                 Value.getNameInitAsString() + "' of type '" +
2861                 Value.getType()->getAsString() +
2862                 "' after resolving references: " + VR->getAsUnquotedString() +
2863                 "\n");
2864       }
2865     }
2866   }
2867
2868   // Resolve the assertion expressions.
2869   for (auto &Assertion : Assertions) {
2870     Init *Value = Assertion.Condition->resolveReferences(R);
2871     Assertion.Condition = Value;
2872     Value = Assertion.Message->resolveReferences(R);
2873     Assertion.Message = Value;
2874   }
2875   // Resolve the dump expressions.
2876   for (auto &Dump : Dumps) {
2877     Init *Value = Dump.Message->resolveReferences(R);
2878     Dump.Message = Value;
2879   }
2880 }
2881
2882 void Record::resolveReferences(Init *NewName) {
2883   RecordResolver R(*this);
2884   R.setName(NewName);
2885   R.setFinal(true);
2886   resolveReferences(R);
2887 }
2888
2889 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2890 LLVM_DUMP_METHOD void Record::dump() const { errs() << *this; }
2891 #endif
2892
2893 raw_ostream &llvm::operator<<(raw_ostream &OS, const Record &R) {
2894   OS << R.getNameInitAsString();
2895
2896   ArrayRef<Init *> TArgs = R.getTemplateArgs();
2897   if (!TArgs.empty()) {
2898     OS << "<";
2899     bool NeedComma = false;
2900     for (const Init *TA : TArgs) {
2901       if (NeedComma) OS << ", ";
2902       NeedComma = true;
2903       const RecordVal *RV = R.getValue(TA);
2904       assert(RV && "Template argument record not found??");
2905       RV->print(OS, false);
2906     }
2907     OS << ">";
2908   }
2909
2910   OS << " {";
2911   ArrayRef<std::pair<Record *, SMRange>> SC = R.getSuperClasses();
2912   if (!SC.empty()) {
2913     OS << "\t//";
2914     for (const auto &SuperPair : SC)
2915       OS << " " << SuperPair.first->getNameInitAsString();
2916   }
2917   OS << "\n";
2918
2919   for (const RecordVal &Val : R.getValues())
2920     if (Val.isNonconcreteOK() && !R.isTemplateArg(Val.getNameInit()))
2921       OS << Val;
2922   for (const RecordVal &Val : R.getValues())
2923     if (!Val.isNonconcreteOK() && !R.isTemplateArg(Val.getNameInit()))
2924       OS << Val;
2925
2926   return OS << "}\n";
2927 }
2928
2929 SMLoc Record::getFieldLoc(StringRef FieldName) const {
2930   const RecordVal *R = getValue(FieldName);
2931   if (!R)
2932     PrintFatalError(getLoc(), "Record `" + getName() +
2933       "' does not have a field named `" + FieldName + "'!\n");
2934   return R->getLoc();
2935 }
2936
2937 Init *Record::getValueInit(StringRef FieldName) const {
2938   const RecordVal *R = getValue(FieldName);
2939   if (!R || !R->getValue())
2940     PrintFatalError(getLoc(), "Record `" + getName() +
2941       "' does not have a field named `" + FieldName + "'!\n");
2942   return R->getValue();
2943 }
2944
2945 StringRef Record::getValueAsString(StringRef FieldName) const {
2946   std::optional<StringRef> S = getValueAsOptionalString(FieldName);
2947   if (!S)
2948     PrintFatalError(getLoc(), "Record `" + getName() +
2949       "' does not have a field named `" + FieldName + "'!\n");
2950   return *S;
2951 }
2952
2953 std::optional<StringRef>
2954 Record::getValueAsOptionalString(StringRef FieldName) const {
2955   const RecordVal *R = getValue(FieldName);
2956   if (!R || !R->getValue())
2957     return std::nullopt;
2958   if (isa<UnsetInit>(R->getValue()))
2959     return std::nullopt;
2960
2961   if (StringInit *SI = dyn_cast<StringInit>(R->getValue()))
2962     return SI->getValue();
2963
2964   PrintFatalError(getLoc(),
2965                   "Record `" + getName() + "', ` field `" + FieldName +
2966                       "' exists but does not have a string initializer!");
2967 }
2968
2969 BitsInit *Record::getValueAsBitsInit(StringRef FieldName) const {
2970   const RecordVal *R = getValue(FieldName);
2971   if (!R || !R->getValue())
2972     PrintFatalError(getLoc(), "Record `" + getName() +
2973       "' does not have a field named `" + FieldName + "'!\n");
2974
2975   if (BitsInit *BI = dyn_cast<BitsInit>(R->getValue()))
2976     return BI;
2977   PrintFatalError(getLoc(), "Record `" + getName() + "', field `" + FieldName +
2978                                 "' exists but does not have a bits value");
2979 }
2980
2981 ListInit *Record::getValueAsListInit(StringRef FieldName) const {
2982   const RecordVal *R = getValue(FieldName);
2983   if (!R || !R->getValue())
2984     PrintFatalError(getLoc(), "Record `" + getName() +
2985       "' does not have a field named `" + FieldName + "'!\n");
2986
2987   if (ListInit *LI = dyn_cast<ListInit>(R->getValue()))
2988     return LI;
2989   PrintFatalError(getLoc(), "Record `" + getName() + "', field `" + FieldName +
2990                                 "' exists but does not have a list value");
2991 }
2992
2993 std::vector<Record*>
2994 Record::getValueAsListOfDefs(StringRef FieldName) const {
2995   ListInit *List = getValueAsListInit(FieldName);
2996   std::vector<Record*> Defs;
2997   for (Init *I : List->getValues()) {
2998     if (DefInit *DI = dyn_cast<DefInit>(I))
2999       Defs.push_back(DI->getDef());
3000     else
3001       PrintFatalError(getLoc(), "Record `" + getName() + "', field `" +
3002         FieldName + "' list is not entirely DefInit!");
3003   }
3004   return Defs;
3005 }
3006
3007 int64_t Record::getValueAsInt(StringRef FieldName) const {
3008   const RecordVal *R = getValue(FieldName);
3009   if (!R || !R->getValue())
3010     PrintFatalError(getLoc(), "Record `" + getName() +
3011       "' does not have a field named `" + FieldName + "'!\n");
3012
3013   if (IntInit *II = dyn_cast<IntInit>(R->getValue()))
3014     return II->getValue();
3015   PrintFatalError(getLoc(), Twine("Record `") + getName() + "', field `" +
3016                                 FieldName +
3017                                 "' exists but does not have an int value: " +
3018                                 R->getValue()->getAsString());
3019 }
3020
3021 std::vector<int64_t>
3022 Record::getValueAsListOfInts(StringRef FieldName) const {
3023   ListInit *List = getValueAsListInit(FieldName);
3024   std::vector<int64_t> Ints;
3025   for (Init *I : List->getValues()) {
3026     if (IntInit *II = dyn_cast<IntInit>(I))
3027       Ints.push_back(II->getValue());
3028     else
3029       PrintFatalError(getLoc(),
3030                       Twine("Record `") + getName() + "', field `" + FieldName +
3031                           "' exists but does not have a list of ints value: " +
3032                           I->getAsString());
3033   }
3034   return Ints;
3035 }
3036
3037 std::vector<StringRef>
3038 Record::getValueAsListOfStrings(StringRef FieldName) const {
3039   ListInit *List = getValueAsListInit(FieldName);
3040   std::vector<StringRef> Strings;
3041   for (Init *I : List->getValues()) {
3042     if (StringInit *SI = dyn_cast<StringInit>(I))
3043       Strings.push_back(SI->getValue());
3044     else
3045       PrintFatalError(getLoc(),
3046                       Twine("Record `") + getName() + "', field `" + FieldName +
3047                           "' exists but does not have a list of strings value: " +
3048                           I->getAsString());
3049   }
3050   return Strings;
3051 }
3052
3053 Record *Record::getValueAsDef(StringRef FieldName) const {
3054   const RecordVal *R = getValue(FieldName);
3055   if (!R || !R->getValue())
3056     PrintFatalError(getLoc(), "Record `" + getName() +
3057       "' does not have a field named `" + FieldName + "'!\n");
3058
3059   if (DefInit *DI = dyn_cast<DefInit>(R->getValue()))
3060     return DI->getDef();
3061   PrintFatalError(getLoc(), "Record `" + getName() + "', field `" +
3062     FieldName + "' does not have a def initializer!");
3063 }
3064
3065 Record *Record::getValueAsOptionalDef(StringRef FieldName) const {
3066   const RecordVal *R = getValue(FieldName);
3067   if (!R || !R->getValue())
3068     PrintFatalError(getLoc(), "Record `" + getName() +
3069       "' does not have a field named `" + FieldName + "'!\n");
3070
3071   if (DefInit *DI = dyn_cast<DefInit>(R->getValue()))
3072     return DI->getDef();
3073   if (isa<UnsetInit>(R->getValue()))
3074     return nullptr;
3075   PrintFatalError(getLoc(), "Record `" + getName() + "', field `" +
3076     FieldName + "' does not have either a def initializer or '?'!");
3077 }
3078
3079
3080 bool Record::getValueAsBit(StringRef FieldName) const {
3081   const RecordVal *R = getValue(FieldName);
3082   if (!R || !R->getValue())
3083     PrintFatalError(getLoc(), "Record `" + getName() +
3084       "' does not have a field named `" + FieldName + "'!\n");
3085
3086   if (BitInit *BI = dyn_cast<BitInit>(R->getValue()))
3087     return BI->getValue();
3088   PrintFatalError(getLoc(), "Record `" + getName() + "', field `" +
3089     FieldName + "' does not have a bit initializer!");
3090 }
3091
3092 bool Record::getValueAsBitOrUnset(StringRef FieldName, bool &Unset) const {
3093   const RecordVal *R = getValue(FieldName);
3094   if (!R || !R->getValue())
3095     PrintFatalError(getLoc(), "Record `" + getName() +
3096       "' does not have a field named `" + FieldName.str() + "'!\n");
3097
3098   if (isa<UnsetInit>(R->getValue())) {
3099     Unset = true;
3100     return false;
3101   }
3102   Unset = false;
3103   if (BitInit *BI = dyn_cast<BitInit>(R->getValue()))
3104     return BI->getValue();
3105   PrintFatalError(getLoc(), "Record `" + getName() + "', field `" +
3106     FieldName + "' does not have a bit initializer!");
3107 }
3108
3109 DagInit *Record::getValueAsDag(StringRef FieldName) const {
3110   const RecordVal *R = getValue(FieldName);
3111   if (!R || !R->getValue())
3112     PrintFatalError(getLoc(), "Record `" + getName() +
3113       "' does not have a field named `" + FieldName + "'!\n");
3114
3115   if (DagInit *DI = dyn_cast<DagInit>(R->getValue()))
3116     return DI;
3117   PrintFatalError(getLoc(), "Record `" + getName() + "', field `" +
3118     FieldName + "' does not have a dag initializer!");
3119 }
3120
3121 // Check all record assertions: For each one, resolve the condition
3122 // and message, then call CheckAssert().
3123 // Note: The condition and message are probably already resolved,
3124 //       but resolving again allows calls before records are resolved.
3125 void Record::checkRecordAssertions() {
3126   RecordResolver R(*this);
3127   R.setFinal(true);
3128
3129   for (const auto &Assertion : getAssertions()) {
3130     Init *Condition = Assertion.Condition->resolveReferences(R);
3131     Init *Message = Assertion.Message->resolveReferences(R);
3132     CheckAssert(Assertion.Loc, Condition, Message);
3133   }
3134 }
3135
3136 void Record::emitRecordDumps() {
3137   RecordResolver R(*this);
3138   R.setFinal(true);
3139
3140   for (const auto &Dump : getDumps()) {
3141     Init *Message = Dump.Message->resolveReferences(R);
3142     dumpMessage(Dump.Loc, Message);
3143   }
3144 }
3145
3146 // Report a warning if the record has unused template arguments.
3147 void Record::checkUnusedTemplateArgs() {
3148   for (const Init *TA : getTemplateArgs()) {
3149     const RecordVal *Arg = getValue(TA);
3150     if (!Arg->isUsed())
3151       PrintWarning(Arg->getLoc(),
3152                    "unused template argument: " + Twine(Arg->getName()));
3153   }
3154 }
3155
3156 RecordKeeper::RecordKeeper()
3157     : Impl(std::make_unique<detail::RecordKeeperImpl>(*this)) {}
3158 RecordKeeper::~RecordKeeper() = default;
3159
3160 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3161 LLVM_DUMP_METHOD void RecordKeeper::dump() const { errs() << *this; }
3162 #endif
3163
3164 raw_ostream &llvm::operator<<(raw_ostream &OS, const RecordKeeper &RK) {
3165   OS << "------------- Classes -----------------\n";
3166   for (const auto &C : RK.getClasses())
3167     OS << "class " << *C.second;
3168
3169   OS << "------------- Defs -----------------\n";
3170   for (const auto &D : RK.getDefs())
3171     OS << "def " << *D.second;
3172   return OS;
3173 }
3174
3175 /// GetNewAnonymousName - Generate a unique anonymous name that can be used as
3176 /// an identifier.
3177 Init *RecordKeeper::getNewAnonymousName() {
3178   return AnonymousNameInit::get(*this, getImpl().AnonCounter++);
3179 }
3180
3181 // These functions implement the phase timing facility. Starting a timer
3182 // when one is already running stops the running one.
3183
3184 void RecordKeeper::startTimer(StringRef Name) {
3185   if (TimingGroup) {
3186     if (LastTimer && LastTimer->isRunning()) {
3187       LastTimer->stopTimer();
3188       if (BackendTimer) {
3189         LastTimer->clear();
3190         BackendTimer = false;
3191       }
3192     }
3193
3194     LastTimer = new Timer("", Name, *TimingGroup);
3195     LastTimer->startTimer();
3196   }
3197 }
3198
3199 void RecordKeeper::stopTimer() {
3200   if (TimingGroup) {
3201     assert(LastTimer && "No phase timer was started");
3202     LastTimer->stopTimer();
3203   }
3204 }
3205
3206 void RecordKeeper::startBackendTimer(StringRef Name) {
3207   if (TimingGroup) {
3208     startTimer(Name);
3209     BackendTimer = true;
3210   }
3211 }
3212
3213 void RecordKeeper::stopBackendTimer() {
3214   if (TimingGroup) {
3215     if (BackendTimer) {
3216       stopTimer();
3217       BackendTimer = false;
3218     }
3219   }
3220 }
3221
3222 std::vector<Record *>
3223 RecordKeeper::getAllDerivedDefinitions(StringRef ClassName) const {
3224   // We cache the record vectors for single classes. Many backends request
3225   // the same vectors multiple times.
3226   auto Pair = ClassRecordsMap.try_emplace(ClassName);
3227   if (Pair.second)
3228     Pair.first->second = getAllDerivedDefinitions(ArrayRef(ClassName));
3229
3230   return Pair.first->second;
3231 }
3232
3233 std::vector<Record *> RecordKeeper::getAllDerivedDefinitions(
3234     ArrayRef<StringRef> ClassNames) const {
3235   SmallVector<Record *, 2> ClassRecs;
3236   std::vector<Record *> Defs;
3237
3238   assert(ClassNames.size() > 0 && "At least one class must be passed.");
3239   for (const auto &ClassName : ClassNames) {
3240     Record *Class = getClass(ClassName);
3241     if (!Class)
3242       PrintFatalError("The class '" + ClassName + "' is not defined\n");
3243     ClassRecs.push_back(Class);
3244   }
3245
3246   for (const auto &OneDef : getDefs()) {
3247     if (all_of(ClassRecs, [&OneDef](const Record *Class) {
3248                             return OneDef.second->isSubClassOf(Class);
3249                           }))
3250       Defs.push_back(OneDef.second.get());
3251   }
3252
3253   llvm::sort(Defs, [](Record *LHS, Record *RHS) {
3254     return LHS->getName().compare_numeric(RHS->getName()) < 0;
3255   });
3256
3257   return Defs;
3258 }
3259
3260 std::vector<Record *>
3261 RecordKeeper::getAllDerivedDefinitionsIfDefined(StringRef ClassName) const {
3262   return getClass(ClassName) ? getAllDerivedDefinitions(ClassName)
3263                              : std::vector<Record *>();
3264 }
3265
3266 Init *MapResolver::resolve(Init *VarName) {
3267   auto It = Map.find(VarName);
3268   if (It == Map.end())
3269     return nullptr;
3270
3271   Init *I = It->second.V;
3272
3273   if (!It->second.Resolved && Map.size() > 1) {
3274     // Resolve mutual references among the mapped variables, but prevent
3275     // infinite recursion.
3276     Map.erase(It);
3277     I = I->resolveReferences(*this);
3278     Map[VarName] = {I, true};
3279   }
3280
3281   return I;
3282 }
3283
3284 Init *RecordResolver::resolve(Init *VarName) {
3285   Init *Val = Cache.lookup(VarName);
3286   if (Val)
3287     return Val;
3288
3289   if (llvm::is_contained(Stack, VarName))
3290     return nullptr; // prevent infinite recursion
3291
3292   if (RecordVal *RV = getCurrentRecord()->getValue(VarName)) {
3293     if (!isa<UnsetInit>(RV->getValue())) {
3294       Val = RV->getValue();
3295       Stack.push_back(VarName);
3296       Val = Val->resolveReferences(*this);
3297       Stack.pop_back();
3298     }
3299   } else if (Name && VarName == getCurrentRecord()->getNameInit()) {
3300     Stack.push_back(VarName);
3301     Val = Name->resolveReferences(*this);
3302     Stack.pop_back();
3303   }
3304
3305   Cache[VarName] = Val;
3306   return Val;
3307 }
3308
3309 Init *TrackUnresolvedResolver::resolve(Init *VarName) {
3310   Init *I = nullptr;
3311
3312   if (R) {
3313     I = R->resolve(VarName);
3314     if (I && !FoundUnresolved) {
3315       // Do not recurse into the resolved initializer, as that would change
3316       // the behavior of the resolver we're delegating, but do check to see
3317       // if there are unresolved variables remaining.
3318       TrackUnresolvedResolver Sub;
3319       I->resolveReferences(Sub);
3320       FoundUnresolved |= Sub.FoundUnresolved;
3321     }
3322   }
3323
3324   if (!I)
3325     FoundUnresolved = true;
3326   return I;
3327 }
3328
3329 Init *HasReferenceResolver::resolve(Init *VarName)
3330 {
3331   if (VarName == VarNameToTrack)
3332     Found = true;
3333   return nullptr;
3334 }