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