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