1 //===- LLVMContextImpl.h - The LLVMContextImpl opaque class -----*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file declares LLVMContextImpl, the opaque implementation
11 //  of LLVMContext.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_LIB_IR_LLVMCONTEXTIMPL_H
16 #define LLVM_LIB_IR_LLVMCONTEXTIMPL_H
17 
18 #include "AttributeImpl.h"
19 #include "ConstantsContext.h"
20 #include "llvm/ADT/APFloat.h"
21 #include "llvm/ADT/APInt.h"
22 #include "llvm/ADT/ArrayRef.h"
23 #include "llvm/ADT/DenseMap.h"
24 #include "llvm/ADT/DenseMapInfo.h"
25 #include "llvm/ADT/DenseSet.h"
26 #include "llvm/ADT/FoldingSet.h"
27 #include "llvm/ADT/Hashing.h"
28 #include "llvm/ADT/Optional.h"
29 #include "llvm/ADT/STLExtras.h"
30 #include "llvm/ADT/SmallPtrSet.h"
31 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/ADT/StringMap.h"
33 #include "llvm/ADT/StringRef.h"
34 #include "llvm/ADT/StringSet.h"
35 #include "llvm/BinaryFormat/Dwarf.h"
36 #include "llvm/IR/Constants.h"
37 #include "llvm/IR/DebugInfoMetadata.h"
38 #include "llvm/IR/DerivedTypes.h"
39 #include "llvm/IR/LLVMContext.h"
40 #include "llvm/IR/Metadata.h"
41 #include "llvm/IR/TrackingMDRef.h"
42 #include "llvm/Support/Allocator.h"
43 #include "llvm/Support/Casting.h"
44 #include "llvm/Support/YAMLTraits.h"
45 #include <algorithm>
46 #include <cassert>
47 #include <cstddef>
48 #include <cstdint>
49 #include <memory>
50 #include <string>
51 #include <utility>
52 #include <vector>
53 
54 namespace llvm {
55 
56 class ConstantFP;
57 class ConstantInt;
58 class Type;
59 class Value;
60 class ValueHandleBase;
61 
62 struct DenseMapAPIntKeyInfo {
getEmptyKeyDenseMapAPIntKeyInfo63   static inline APInt getEmptyKey() {
64     APInt V(nullptr, 0);
65     V.U.VAL = 0;
66     return V;
67   }
68 
getTombstoneKeyDenseMapAPIntKeyInfo69   static inline APInt getTombstoneKey() {
70     APInt V(nullptr, 0);
71     V.U.VAL = 1;
72     return V;
73   }
74 
getHashValueDenseMapAPIntKeyInfo75   static unsigned getHashValue(const APInt &Key) {
76     return static_cast<unsigned>(hash_value(Key));
77   }
78 
isEqualDenseMapAPIntKeyInfo79   static bool isEqual(const APInt &LHS, const APInt &RHS) {
80     return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS;
81   }
82 };
83 
84 struct DenseMapAPFloatKeyInfo {
getEmptyKeyDenseMapAPFloatKeyInfo85   static inline APFloat getEmptyKey() { return APFloat(APFloat::Bogus(), 1); }
getTombstoneKeyDenseMapAPFloatKeyInfo86   static inline APFloat getTombstoneKey() { return APFloat(APFloat::Bogus(), 2); }
87 
getHashValueDenseMapAPFloatKeyInfo88   static unsigned getHashValue(const APFloat &Key) {
89     return static_cast<unsigned>(hash_value(Key));
90   }
91 
isEqualDenseMapAPFloatKeyInfo92   static bool isEqual(const APFloat &LHS, const APFloat &RHS) {
93     return LHS.bitwiseIsEqual(RHS);
94   }
95 };
96 
97 struct AnonStructTypeKeyInfo {
98   struct KeyTy {
99     ArrayRef<Type*> ETypes;
100     bool isPacked;
101 
KeyTyAnonStructTypeKeyInfo::KeyTy102     KeyTy(const ArrayRef<Type*>& E, bool P) :
103       ETypes(E), isPacked(P) {}
104 
KeyTyAnonStructTypeKeyInfo::KeyTy105     KeyTy(const StructType *ST)
106         : ETypes(ST->elements()), isPacked(ST->isPacked()) {}
107 
108     bool operator==(const KeyTy& that) const {
109       if (isPacked != that.isPacked)
110         return false;
111       if (ETypes != that.ETypes)
112         return false;
113       return true;
114     }
115     bool operator!=(const KeyTy& that) const {
116       return !this->operator==(that);
117     }
118   };
119 
getEmptyKeyAnonStructTypeKeyInfo120   static inline StructType* getEmptyKey() {
121     return DenseMapInfo<StructType*>::getEmptyKey();
122   }
123 
getTombstoneKeyAnonStructTypeKeyInfo124   static inline StructType* getTombstoneKey() {
125     return DenseMapInfo<StructType*>::getTombstoneKey();
126   }
127 
getHashValueAnonStructTypeKeyInfo128   static unsigned getHashValue(const KeyTy& Key) {
129     return hash_combine(hash_combine_range(Key.ETypes.begin(),
130                                            Key.ETypes.end()),
131                         Key.isPacked);
132   }
133 
getHashValueAnonStructTypeKeyInfo134   static unsigned getHashValue(const StructType *ST) {
135     return getHashValue(KeyTy(ST));
136   }
137 
isEqualAnonStructTypeKeyInfo138   static bool isEqual(const KeyTy& LHS, const StructType *RHS) {
139     if (RHS == getEmptyKey() || RHS == getTombstoneKey())
140       return false;
141     return LHS == KeyTy(RHS);
142   }
143 
isEqualAnonStructTypeKeyInfo144   static bool isEqual(const StructType *LHS, const StructType *RHS) {
145     return LHS == RHS;
146   }
147 };
148 
149 struct FunctionTypeKeyInfo {
150   struct KeyTy {
151     const Type *ReturnType;
152     ArrayRef<Type*> Params;
153     bool isVarArg;
154 
KeyTyFunctionTypeKeyInfo::KeyTy155     KeyTy(const Type* R, const ArrayRef<Type*>& P, bool V) :
156       ReturnType(R), Params(P), isVarArg(V) {}
KeyTyFunctionTypeKeyInfo::KeyTy157     KeyTy(const FunctionType *FT)
158         : ReturnType(FT->getReturnType()), Params(FT->params()),
159           isVarArg(FT->isVarArg()) {}
160 
161     bool operator==(const KeyTy& that) const {
162       if (ReturnType != that.ReturnType)
163         return false;
164       if (isVarArg != that.isVarArg)
165         return false;
166       if (Params != that.Params)
167         return false;
168       return true;
169     }
170     bool operator!=(const KeyTy& that) const {
171       return !this->operator==(that);
172     }
173   };
174 
getEmptyKeyFunctionTypeKeyInfo175   static inline FunctionType* getEmptyKey() {
176     return DenseMapInfo<FunctionType*>::getEmptyKey();
177   }
178 
getTombstoneKeyFunctionTypeKeyInfo179   static inline FunctionType* getTombstoneKey() {
180     return DenseMapInfo<FunctionType*>::getTombstoneKey();
181   }
182 
getHashValueFunctionTypeKeyInfo183   static unsigned getHashValue(const KeyTy& Key) {
184     return hash_combine(Key.ReturnType,
185                         hash_combine_range(Key.Params.begin(),
186                                            Key.Params.end()),
187                         Key.isVarArg);
188   }
189 
getHashValueFunctionTypeKeyInfo190   static unsigned getHashValue(const FunctionType *FT) {
191     return getHashValue(KeyTy(FT));
192   }
193 
isEqualFunctionTypeKeyInfo194   static bool isEqual(const KeyTy& LHS, const FunctionType *RHS) {
195     if (RHS == getEmptyKey() || RHS == getTombstoneKey())
196       return false;
197     return LHS == KeyTy(RHS);
198   }
199 
isEqualFunctionTypeKeyInfo200   static bool isEqual(const FunctionType *LHS, const FunctionType *RHS) {
201     return LHS == RHS;
202   }
203 };
204 
205 /// Structure for hashing arbitrary MDNode operands.
206 class MDNodeOpsKey {
207   ArrayRef<Metadata *> RawOps;
208   ArrayRef<MDOperand> Ops;
209   unsigned Hash;
210 
211 protected:
MDNodeOpsKey(ArrayRef<Metadata * > Ops)212   MDNodeOpsKey(ArrayRef<Metadata *> Ops)
213       : RawOps(Ops), Hash(calculateHash(Ops)) {}
214 
215   template <class NodeTy>
216   MDNodeOpsKey(const NodeTy *N, unsigned Offset = 0)
217       : Ops(N->op_begin() + Offset, N->op_end()), Hash(N->getHash()) {}
218 
219   template <class NodeTy>
220   bool compareOps(const NodeTy *RHS, unsigned Offset = 0) const {
221     if (getHash() != RHS->getHash())
222       return false;
223 
224     assert((RawOps.empty() || Ops.empty()) && "Two sets of operands?");
225     return RawOps.empty() ? compareOps(Ops, RHS, Offset)
226                           : compareOps(RawOps, RHS, Offset);
227   }
228 
229   static unsigned calculateHash(MDNode *N, unsigned Offset = 0);
230 
231 private:
232   template <class T>
compareOps(ArrayRef<T> Ops,const MDNode * RHS,unsigned Offset)233   static bool compareOps(ArrayRef<T> Ops, const MDNode *RHS, unsigned Offset) {
234     if (Ops.size() != RHS->getNumOperands() - Offset)
235       return false;
236     return std::equal(Ops.begin(), Ops.end(), RHS->op_begin() + Offset);
237   }
238 
239   static unsigned calculateHash(ArrayRef<Metadata *> Ops);
240 
241 public:
getHash()242   unsigned getHash() const { return Hash; }
243 };
244 
245 template <class NodeTy> struct MDNodeKeyImpl;
246 
247 /// Configuration point for MDNodeInfo::isEqual().
248 template <class NodeTy> struct MDNodeSubsetEqualImpl {
249   using KeyTy = MDNodeKeyImpl<NodeTy>;
250 
isSubsetEqualMDNodeSubsetEqualImpl251   static bool isSubsetEqual(const KeyTy &LHS, const NodeTy *RHS) {
252     return false;
253   }
254 
isSubsetEqualMDNodeSubsetEqualImpl255   static bool isSubsetEqual(const NodeTy *LHS, const NodeTy *RHS) {
256     return false;
257   }
258 };
259 
260 /// DenseMapInfo for MDTuple.
261 ///
262 /// Note that we don't need the is-function-local bit, since that's implicit in
263 /// the operands.
264 template <> struct MDNodeKeyImpl<MDTuple> : MDNodeOpsKey {
265   MDNodeKeyImpl(ArrayRef<Metadata *> Ops) : MDNodeOpsKey(Ops) {}
266   MDNodeKeyImpl(const MDTuple *N) : MDNodeOpsKey(N) {}
267 
268   bool isKeyOf(const MDTuple *RHS) const { return compareOps(RHS); }
269 
270   unsigned getHashValue() const { return getHash(); }
271 
272   static unsigned calculateHash(MDTuple *N) {
273     return MDNodeOpsKey::calculateHash(N);
274   }
275 };
276 
277 /// DenseMapInfo for DILocation.
278 template <> struct MDNodeKeyImpl<DILocation> {
279   unsigned Line;
280   unsigned Column;
281   Metadata *Scope;
282   Metadata *InlinedAt;
283   bool ImplicitCode;
284 
285   MDNodeKeyImpl(unsigned Line, unsigned Column, Metadata *Scope,
286                 Metadata *InlinedAt, bool ImplicitCode)
287       : Line(Line), Column(Column), Scope(Scope), InlinedAt(InlinedAt),
288         ImplicitCode(ImplicitCode) {}
289   MDNodeKeyImpl(const DILocation *L)
290       : Line(L->getLine()), Column(L->getColumn()), Scope(L->getRawScope()),
291         InlinedAt(L->getRawInlinedAt()), ImplicitCode(L->isImplicitCode()) {}
292 
293   bool isKeyOf(const DILocation *RHS) const {
294     return Line == RHS->getLine() && Column == RHS->getColumn() &&
295            Scope == RHS->getRawScope() && InlinedAt == RHS->getRawInlinedAt() &&
296            ImplicitCode == RHS->isImplicitCode();
297   }
298 
299   unsigned getHashValue() const {
300     return hash_combine(Line, Column, Scope, InlinedAt, ImplicitCode);
301   }
302 };
303 
304 /// DenseMapInfo for GenericDINode.
305 template <> struct MDNodeKeyImpl<GenericDINode> : MDNodeOpsKey {
306   unsigned Tag;
307   MDString *Header;
308 
309   MDNodeKeyImpl(unsigned Tag, MDString *Header, ArrayRef<Metadata *> DwarfOps)
310       : MDNodeOpsKey(DwarfOps), Tag(Tag), Header(Header) {}
311   MDNodeKeyImpl(const GenericDINode *N)
312       : MDNodeOpsKey(N, 1), Tag(N->getTag()), Header(N->getRawHeader()) {}
313 
314   bool isKeyOf(const GenericDINode *RHS) const {
315     return Tag == RHS->getTag() && Header == RHS->getRawHeader() &&
316            compareOps(RHS, 1);
317   }
318 
319   unsigned getHashValue() const { return hash_combine(getHash(), Tag, Header); }
320 
321   static unsigned calculateHash(GenericDINode *N) {
322     return MDNodeOpsKey::calculateHash(N, 1);
323   }
324 };
325 
326 template <> struct MDNodeKeyImpl<DISubrange> {
327   Metadata *CountNode;
328   int64_t LowerBound;
329 
330   MDNodeKeyImpl(Metadata *CountNode, int64_t LowerBound)
331       : CountNode(CountNode), LowerBound(LowerBound) {}
332   MDNodeKeyImpl(const DISubrange *N)
333       : CountNode(N->getRawCountNode()),
334         LowerBound(N->getLowerBound()) {}
335 
336   bool isKeyOf(const DISubrange *RHS) const {
337     if (LowerBound != RHS->getLowerBound())
338       return false;
339 
340     if (auto *RHSCount = RHS->getCount().dyn_cast<ConstantInt*>())
341       if (auto *MD = dyn_cast<ConstantAsMetadata>(CountNode))
342         if (RHSCount->getSExtValue() ==
343             cast<ConstantInt>(MD->getValue())->getSExtValue())
344           return true;
345 
346     return CountNode == RHS->getRawCountNode();
347   }
348 
349   unsigned getHashValue() const {
350     if (auto *MD = dyn_cast<ConstantAsMetadata>(CountNode))
351       return hash_combine(cast<ConstantInt>(MD->getValue())->getSExtValue(),
352                           LowerBound);
353     return hash_combine(CountNode, LowerBound);
354   }
355 };
356 
357 template <> struct MDNodeKeyImpl<DIEnumerator> {
358   int64_t Value;
359   MDString *Name;
360   bool IsUnsigned;
361 
362   MDNodeKeyImpl(int64_t Value, bool IsUnsigned, MDString *Name)
363       : Value(Value), Name(Name), IsUnsigned(IsUnsigned) {}
364   MDNodeKeyImpl(const DIEnumerator *N)
365       : Value(N->getValue()), Name(N->getRawName()),
366         IsUnsigned(N->isUnsigned()) {}
367 
368   bool isKeyOf(const DIEnumerator *RHS) const {
369     return Value == RHS->getValue() && IsUnsigned == RHS->isUnsigned() &&
370            Name == RHS->getRawName();
371   }
372 
373   unsigned getHashValue() const { return hash_combine(Value, Name); }
374 };
375 
376 template <> struct MDNodeKeyImpl<DIBasicType> {
377   unsigned Tag;
378   MDString *Name;
379   uint64_t SizeInBits;
380   uint32_t AlignInBits;
381   unsigned Encoding;
382   unsigned Flags;
383 
384   MDNodeKeyImpl(unsigned Tag, MDString *Name, uint64_t SizeInBits,
385                 uint32_t AlignInBits, unsigned Encoding, unsigned Flags)
386       : Tag(Tag), Name(Name), SizeInBits(SizeInBits), AlignInBits(AlignInBits),
387         Encoding(Encoding), Flags(Flags) {}
388   MDNodeKeyImpl(const DIBasicType *N)
389       : Tag(N->getTag()), Name(N->getRawName()), SizeInBits(N->getSizeInBits()),
390         AlignInBits(N->getAlignInBits()), Encoding(N->getEncoding()), Flags(N->getFlags()) {}
391 
392   bool isKeyOf(const DIBasicType *RHS) const {
393     return Tag == RHS->getTag() && Name == RHS->getRawName() &&
394            SizeInBits == RHS->getSizeInBits() &&
395            AlignInBits == RHS->getAlignInBits() &&
396            Encoding == RHS->getEncoding() &&
397            Flags == RHS->getFlags();
398   }
399 
400   unsigned getHashValue() const {
401     return hash_combine(Tag, Name, SizeInBits, AlignInBits, Encoding);
402   }
403 };
404 
405 template <> struct MDNodeKeyImpl<DIDerivedType> {
406   unsigned Tag;
407   MDString *Name;
408   Metadata *File;
409   unsigned Line;
410   Metadata *Scope;
411   Metadata *BaseType;
412   uint64_t SizeInBits;
413   uint64_t OffsetInBits;
414   uint32_t AlignInBits;
415   Optional<unsigned> DWARFAddressSpace;
416   unsigned Flags;
417   Metadata *ExtraData;
418 
419   MDNodeKeyImpl(unsigned Tag, MDString *Name, Metadata *File, unsigned Line,
420                 Metadata *Scope, Metadata *BaseType, uint64_t SizeInBits,
421                 uint32_t AlignInBits, uint64_t OffsetInBits,
422                 Optional<unsigned> DWARFAddressSpace, unsigned Flags,
423                 Metadata *ExtraData)
424       : Tag(Tag), Name(Name), File(File), Line(Line), Scope(Scope),
425         BaseType(BaseType), SizeInBits(SizeInBits), OffsetInBits(OffsetInBits),
426         AlignInBits(AlignInBits), DWARFAddressSpace(DWARFAddressSpace),
427         Flags(Flags), ExtraData(ExtraData) {}
428   MDNodeKeyImpl(const DIDerivedType *N)
429       : Tag(N->getTag()), Name(N->getRawName()), File(N->getRawFile()),
430         Line(N->getLine()), Scope(N->getRawScope()),
431         BaseType(N->getRawBaseType()), SizeInBits(N->getSizeInBits()),
432         OffsetInBits(N->getOffsetInBits()), AlignInBits(N->getAlignInBits()),
433         DWARFAddressSpace(N->getDWARFAddressSpace()), Flags(N->getFlags()),
434         ExtraData(N->getRawExtraData()) {}
435 
436   bool isKeyOf(const DIDerivedType *RHS) const {
437     return Tag == RHS->getTag() && Name == RHS->getRawName() &&
438            File == RHS->getRawFile() && Line == RHS->getLine() &&
439            Scope == RHS->getRawScope() && BaseType == RHS->getRawBaseType() &&
440            SizeInBits == RHS->getSizeInBits() &&
441            AlignInBits == RHS->getAlignInBits() &&
442            OffsetInBits == RHS->getOffsetInBits() &&
443            DWARFAddressSpace == RHS->getDWARFAddressSpace() &&
444            Flags == RHS->getFlags() &&
445            ExtraData == RHS->getRawExtraData();
446   }
447 
448   unsigned getHashValue() const {
449     // If this is a member inside an ODR type, only hash the type and the name.
450     // Otherwise the hash will be stronger than
451     // MDNodeSubsetEqualImpl::isODRMember().
452     if (Tag == dwarf::DW_TAG_member && Name)
453       if (auto *CT = dyn_cast_or_null<DICompositeType>(Scope))
454         if (CT->getRawIdentifier())
455           return hash_combine(Name, Scope);
456 
457     // Intentionally computes the hash on a subset of the operands for
458     // performance reason. The subset has to be significant enough to avoid
459     // collision "most of the time". There is no correctness issue in case of
460     // collision because of the full check above.
461     return hash_combine(Tag, Name, File, Line, Scope, BaseType, Flags);
462   }
463 };
464 
465 template <> struct MDNodeSubsetEqualImpl<DIDerivedType> {
466   using KeyTy = MDNodeKeyImpl<DIDerivedType>;
467 
468   static bool isSubsetEqual(const KeyTy &LHS, const DIDerivedType *RHS) {
469     return isODRMember(LHS.Tag, LHS.Scope, LHS.Name, RHS);
470   }
471 
472   static bool isSubsetEqual(const DIDerivedType *LHS, const DIDerivedType *RHS) {
473     return isODRMember(LHS->getTag(), LHS->getRawScope(), LHS->getRawName(),
474                        RHS);
475   }
476 
477   /// Subprograms compare equal if they declare the same function in an ODR
478   /// type.
479   static bool isODRMember(unsigned Tag, const Metadata *Scope,
480                           const MDString *Name, const DIDerivedType *RHS) {
481     // Check whether the LHS is eligible.
482     if (Tag != dwarf::DW_TAG_member || !Name)
483       return false;
484 
485     auto *CT = dyn_cast_or_null<DICompositeType>(Scope);
486     if (!CT || !CT->getRawIdentifier())
487       return false;
488 
489     // Compare to the RHS.
490     return Tag == RHS->getTag() && Name == RHS->getRawName() &&
491            Scope == RHS->getRawScope();
492   }
493 };
494 
495 template <> struct MDNodeKeyImpl<DICompositeType> {
496   unsigned Tag;
497   MDString *Name;
498   Metadata *File;
499   unsigned Line;
500   Metadata *Scope;
501   Metadata *BaseType;
502   uint64_t SizeInBits;
503   uint64_t OffsetInBits;
504   uint32_t AlignInBits;
505   unsigned Flags;
506   Metadata *Elements;
507   unsigned RuntimeLang;
508   Metadata *VTableHolder;
509   Metadata *TemplateParams;
510   MDString *Identifier;
511   Metadata *Discriminator;
512 
513   MDNodeKeyImpl(unsigned Tag, MDString *Name, Metadata *File, unsigned Line,
514                 Metadata *Scope, Metadata *BaseType, uint64_t SizeInBits,
515                 uint32_t AlignInBits, uint64_t OffsetInBits, unsigned Flags,
516                 Metadata *Elements, unsigned RuntimeLang,
517                 Metadata *VTableHolder, Metadata *TemplateParams,
518                 MDString *Identifier, Metadata *Discriminator)
519       : Tag(Tag), Name(Name), File(File), Line(Line), Scope(Scope),
520         BaseType(BaseType), SizeInBits(SizeInBits), OffsetInBits(OffsetInBits),
521         AlignInBits(AlignInBits), Flags(Flags), Elements(Elements),
522         RuntimeLang(RuntimeLang), VTableHolder(VTableHolder),
523         TemplateParams(TemplateParams), Identifier(Identifier),
524         Discriminator(Discriminator) {}
525   MDNodeKeyImpl(const DICompositeType *N)
526       : Tag(N->getTag()), Name(N->getRawName()), File(N->getRawFile()),
527         Line(N->getLine()), Scope(N->getRawScope()),
528         BaseType(N->getRawBaseType()), SizeInBits(N->getSizeInBits()),
529         OffsetInBits(N->getOffsetInBits()), AlignInBits(N->getAlignInBits()),
530         Flags(N->getFlags()), Elements(N->getRawElements()),
531         RuntimeLang(N->getRuntimeLang()), VTableHolder(N->getRawVTableHolder()),
532         TemplateParams(N->getRawTemplateParams()),
533         Identifier(N->getRawIdentifier()),
534         Discriminator(N->getRawDiscriminator()) {}
535 
536   bool isKeyOf(const DICompositeType *RHS) const {
537     return Tag == RHS->getTag() && Name == RHS->getRawName() &&
538            File == RHS->getRawFile() && Line == RHS->getLine() &&
539            Scope == RHS->getRawScope() && BaseType == RHS->getRawBaseType() &&
540            SizeInBits == RHS->getSizeInBits() &&
541            AlignInBits == RHS->getAlignInBits() &&
542            OffsetInBits == RHS->getOffsetInBits() && Flags == RHS->getFlags() &&
543            Elements == RHS->getRawElements() &&
544            RuntimeLang == RHS->getRuntimeLang() &&
545            VTableHolder == RHS->getRawVTableHolder() &&
546            TemplateParams == RHS->getRawTemplateParams() &&
547            Identifier == RHS->getRawIdentifier() &&
548            Discriminator == RHS->getRawDiscriminator();
549   }
550 
551   unsigned getHashValue() const {
552     // Intentionally computes the hash on a subset of the operands for
553     // performance reason. The subset has to be significant enough to avoid
554     // collision "most of the time". There is no correctness issue in case of
555     // collision because of the full check above.
556     return hash_combine(Name, File, Line, BaseType, Scope, Elements,
557                         TemplateParams);
558   }
559 };
560 
561 template <> struct MDNodeKeyImpl<DISubroutineType> {
562   unsigned Flags;
563   uint8_t CC;
564   Metadata *TypeArray;
565 
566   MDNodeKeyImpl(unsigned Flags, uint8_t CC, Metadata *TypeArray)
567       : Flags(Flags), CC(CC), TypeArray(TypeArray) {}
568   MDNodeKeyImpl(const DISubroutineType *N)
569       : Flags(N->getFlags()), CC(N->getCC()), TypeArray(N->getRawTypeArray()) {}
570 
571   bool isKeyOf(const DISubroutineType *RHS) const {
572     return Flags == RHS->getFlags() && CC == RHS->getCC() &&
573            TypeArray == RHS->getRawTypeArray();
574   }
575 
576   unsigned getHashValue() const { return hash_combine(Flags, CC, TypeArray); }
577 };
578 
579 template <> struct MDNodeKeyImpl<DIFile> {
580   MDString *Filename;
581   MDString *Directory;
582   Optional<DIFile::ChecksumInfo<MDString *>> Checksum;
583   Optional<MDString *> Source;
584 
585   MDNodeKeyImpl(MDString *Filename, MDString *Directory,
586                 Optional<DIFile::ChecksumInfo<MDString *>> Checksum,
587                 Optional<MDString *> Source)
588       : Filename(Filename), Directory(Directory), Checksum(Checksum),
589         Source(Source) {}
590   MDNodeKeyImpl(const DIFile *N)
591       : Filename(N->getRawFilename()), Directory(N->getRawDirectory()),
592         Checksum(N->getRawChecksum()), Source(N->getRawSource()) {}
593 
594   bool isKeyOf(const DIFile *RHS) const {
595     return Filename == RHS->getRawFilename() &&
596            Directory == RHS->getRawDirectory() &&
597            Checksum == RHS->getRawChecksum() &&
598            Source == RHS->getRawSource();
599   }
600 
601   unsigned getHashValue() const {
602     return hash_combine(
603         Filename, Directory, Checksum ? Checksum->Kind : 0,
604         Checksum ? Checksum->Value : nullptr, Source.getValueOr(nullptr));
605   }
606 };
607 
608 template <> struct MDNodeKeyImpl<DISubprogram> {
609   Metadata *Scope;
610   MDString *Name;
611   MDString *LinkageName;
612   Metadata *File;
613   unsigned Line;
614   Metadata *Type;
615   unsigned ScopeLine;
616   Metadata *ContainingType;
617   unsigned VirtualIndex;
618   int ThisAdjustment;
619   unsigned Flags;
620   unsigned SPFlags;
621   Metadata *Unit;
622   Metadata *TemplateParams;
623   Metadata *Declaration;
624   Metadata *RetainedNodes;
625   Metadata *ThrownTypes;
626 
627   MDNodeKeyImpl(Metadata *Scope, MDString *Name, MDString *LinkageName,
628                 Metadata *File, unsigned Line, Metadata *Type,
629                 unsigned ScopeLine, Metadata *ContainingType,
630                 unsigned VirtualIndex, int ThisAdjustment, unsigned Flags,
631                 unsigned SPFlags, Metadata *Unit, Metadata *TemplateParams,
632                 Metadata *Declaration, Metadata *RetainedNodes,
633                 Metadata *ThrownTypes)
634       : Scope(Scope), Name(Name), LinkageName(LinkageName), File(File),
635         Line(Line), Type(Type), ScopeLine(ScopeLine),
636         ContainingType(ContainingType), VirtualIndex(VirtualIndex),
637         ThisAdjustment(ThisAdjustment), Flags(Flags), SPFlags(SPFlags),
638         Unit(Unit), TemplateParams(TemplateParams), Declaration(Declaration),
639         RetainedNodes(RetainedNodes), ThrownTypes(ThrownTypes) {}
640   MDNodeKeyImpl(const DISubprogram *N)
641       : Scope(N->getRawScope()), Name(N->getRawName()),
642         LinkageName(N->getRawLinkageName()), File(N->getRawFile()),
643         Line(N->getLine()), Type(N->getRawType()), ScopeLine(N->getScopeLine()),
644         ContainingType(N->getRawContainingType()),
645         VirtualIndex(N->getVirtualIndex()),
646         ThisAdjustment(N->getThisAdjustment()), Flags(N->getFlags()),
647         SPFlags(N->getSPFlags()), Unit(N->getRawUnit()),
648         TemplateParams(N->getRawTemplateParams()),
649         Declaration(N->getRawDeclaration()),
650         RetainedNodes(N->getRawRetainedNodes()),
651         ThrownTypes(N->getRawThrownTypes()) {}
652 
653   bool isKeyOf(const DISubprogram *RHS) const {
654     return Scope == RHS->getRawScope() && Name == RHS->getRawName() &&
655            LinkageName == RHS->getRawLinkageName() &&
656            File == RHS->getRawFile() && Line == RHS->getLine() &&
657            Type == RHS->getRawType() && ScopeLine == RHS->getScopeLine() &&
658            ContainingType == RHS->getRawContainingType() &&
659            VirtualIndex == RHS->getVirtualIndex() &&
660            ThisAdjustment == RHS->getThisAdjustment() &&
661            Flags == RHS->getFlags() && SPFlags == RHS->getSPFlags() &&
662            Unit == RHS->getUnit() &&
663            TemplateParams == RHS->getRawTemplateParams() &&
664            Declaration == RHS->getRawDeclaration() &&
665            RetainedNodes == RHS->getRawRetainedNodes() &&
666            ThrownTypes == RHS->getRawThrownTypes();
667   }
668 
669   bool isDefinition() const { return SPFlags & DISubprogram::SPFlagDefinition; }
670 
671   unsigned getHashValue() const {
672     // If this is a declaration inside an ODR type, only hash the type and the
673     // name.  Otherwise the hash will be stronger than
674     // MDNodeSubsetEqualImpl::isDeclarationOfODRMember().
675     if (!isDefinition() && LinkageName)
676       if (auto *CT = dyn_cast_or_null<DICompositeType>(Scope))
677         if (CT->getRawIdentifier())
678           return hash_combine(LinkageName, Scope);
679 
680     // Intentionally computes the hash on a subset of the operands for
681     // performance reason. The subset has to be significant enough to avoid
682     // collision "most of the time". There is no correctness issue in case of
683     // collision because of the full check above.
684     return hash_combine(Name, Scope, File, Type, Line);
685   }
686 };
687 
688 template <> struct MDNodeSubsetEqualImpl<DISubprogram> {
689   using KeyTy = MDNodeKeyImpl<DISubprogram>;
690 
691   static bool isSubsetEqual(const KeyTy &LHS, const DISubprogram *RHS) {
692     return isDeclarationOfODRMember(LHS.isDefinition(), LHS.Scope,
693                                     LHS.LinkageName, LHS.TemplateParams, RHS);
694   }
695 
696   static bool isSubsetEqual(const DISubprogram *LHS, const DISubprogram *RHS) {
697     return isDeclarationOfODRMember(LHS->isDefinition(), LHS->getRawScope(),
698                                     LHS->getRawLinkageName(),
699                                     LHS->getRawTemplateParams(), RHS);
700   }
701 
702   /// Subprograms compare equal if they declare the same function in an ODR
703   /// type.
704   static bool isDeclarationOfODRMember(bool IsDefinition, const Metadata *Scope,
705                                        const MDString *LinkageName,
706                                        const Metadata *TemplateParams,
707                                        const DISubprogram *RHS) {
708     // Check whether the LHS is eligible.
709     if (IsDefinition || !Scope || !LinkageName)
710       return false;
711 
712     auto *CT = dyn_cast_or_null<DICompositeType>(Scope);
713     if (!CT || !CT->getRawIdentifier())
714       return false;
715 
716     // Compare to the RHS.
717     // FIXME: We need to compare template parameters here to avoid incorrect
718     // collisions in mapMetadata when RF_MoveDistinctMDs and a ODR-DISubprogram
719     // has a non-ODR template parameter (i.e., a DICompositeType that does not
720     // have an identifier). Eventually we should decouple ODR logic from
721     // uniquing logic.
722     return IsDefinition == RHS->isDefinition() && Scope == RHS->getRawScope() &&
723            LinkageName == RHS->getRawLinkageName() &&
724            TemplateParams == RHS->getRawTemplateParams();
725   }
726 };
727 
728 template <> struct MDNodeKeyImpl<DILexicalBlock> {
729   Metadata *Scope;
730   Metadata *File;
731   unsigned Line;
732   unsigned Column;
733 
734   MDNodeKeyImpl(Metadata *Scope, Metadata *File, unsigned Line, unsigned Column)
735       : Scope(Scope), File(File), Line(Line), Column(Column) {}
736   MDNodeKeyImpl(const DILexicalBlock *N)
737       : Scope(N->getRawScope()), File(N->getRawFile()), Line(N->getLine()),
738         Column(N->getColumn()) {}
739 
740   bool isKeyOf(const DILexicalBlock *RHS) const {
741     return Scope == RHS->getRawScope() && File == RHS->getRawFile() &&
742            Line == RHS->getLine() && Column == RHS->getColumn();
743   }
744 
745   unsigned getHashValue() const {
746     return hash_combine(Scope, File, Line, Column);
747   }
748 };
749 
750 template <> struct MDNodeKeyImpl<DILexicalBlockFile> {
751   Metadata *Scope;
752   Metadata *File;
753   unsigned Discriminator;
754 
755   MDNodeKeyImpl(Metadata *Scope, Metadata *File, unsigned Discriminator)
756       : Scope(Scope), File(File), Discriminator(Discriminator) {}
757   MDNodeKeyImpl(const DILexicalBlockFile *N)
758       : Scope(N->getRawScope()), File(N->getRawFile()),
759         Discriminator(N->getDiscriminator()) {}
760 
761   bool isKeyOf(const DILexicalBlockFile *RHS) const {
762     return Scope == RHS->getRawScope() && File == RHS->getRawFile() &&
763            Discriminator == RHS->getDiscriminator();
764   }
765 
766   unsigned getHashValue() const {
767     return hash_combine(Scope, File, Discriminator);
768   }
769 };
770 
771 template <> struct MDNodeKeyImpl<DINamespace> {
772   Metadata *Scope;
773   MDString *Name;
774   bool ExportSymbols;
775 
776   MDNodeKeyImpl(Metadata *Scope, MDString *Name, bool ExportSymbols)
777       : Scope(Scope), Name(Name), ExportSymbols(ExportSymbols) {}
778   MDNodeKeyImpl(const DINamespace *N)
779       : Scope(N->getRawScope()), Name(N->getRawName()),
780         ExportSymbols(N->getExportSymbols()) {}
781 
782   bool isKeyOf(const DINamespace *RHS) const {
783     return Scope == RHS->getRawScope() && Name == RHS->getRawName() &&
784            ExportSymbols == RHS->getExportSymbols();
785   }
786 
787   unsigned getHashValue() const {
788     return hash_combine(Scope, Name);
789   }
790 };
791 
792 template <> struct MDNodeKeyImpl<DIModule> {
793   Metadata *Scope;
794   MDString *Name;
795   MDString *ConfigurationMacros;
796   MDString *IncludePath;
797   MDString *ISysRoot;
798 
799   MDNodeKeyImpl(Metadata *Scope, MDString *Name, MDString *ConfigurationMacros,
800                 MDString *IncludePath, MDString *ISysRoot)
801       : Scope(Scope), Name(Name), ConfigurationMacros(ConfigurationMacros),
802         IncludePath(IncludePath), ISysRoot(ISysRoot) {}
803   MDNodeKeyImpl(const DIModule *N)
804       : Scope(N->getRawScope()), Name(N->getRawName()),
805         ConfigurationMacros(N->getRawConfigurationMacros()),
806         IncludePath(N->getRawIncludePath()), ISysRoot(N->getRawISysRoot()) {}
807 
808   bool isKeyOf(const DIModule *RHS) const {
809     return Scope == RHS->getRawScope() && Name == RHS->getRawName() &&
810            ConfigurationMacros == RHS->getRawConfigurationMacros() &&
811            IncludePath == RHS->getRawIncludePath() &&
812            ISysRoot == RHS->getRawISysRoot();
813   }
814 
815   unsigned getHashValue() const {
816     return hash_combine(Scope, Name,
817                         ConfigurationMacros, IncludePath, ISysRoot);
818   }
819 };
820 
821 template <> struct MDNodeKeyImpl<DITemplateTypeParameter> {
822   MDString *Name;
823   Metadata *Type;
824 
825   MDNodeKeyImpl(MDString *Name, Metadata *Type) : Name(Name), Type(Type) {}
826   MDNodeKeyImpl(const DITemplateTypeParameter *N)
827       : Name(N->getRawName()), Type(N->getRawType()) {}
828 
829   bool isKeyOf(const DITemplateTypeParameter *RHS) const {
830     return Name == RHS->getRawName() && Type == RHS->getRawType();
831   }
832 
833   unsigned getHashValue() const { return hash_combine(Name, Type); }
834 };
835 
836 template <> struct MDNodeKeyImpl<DITemplateValueParameter> {
837   unsigned Tag;
838   MDString *Name;
839   Metadata *Type;
840   Metadata *Value;
841 
842   MDNodeKeyImpl(unsigned Tag, MDString *Name, Metadata *Type, Metadata *Value)
843       : Tag(Tag), Name(Name), Type(Type), Value(Value) {}
844   MDNodeKeyImpl(const DITemplateValueParameter *N)
845       : Tag(N->getTag()), Name(N->getRawName()), Type(N->getRawType()),
846         Value(N->getValue()) {}
847 
848   bool isKeyOf(const DITemplateValueParameter *RHS) const {
849     return Tag == RHS->getTag() && Name == RHS->getRawName() &&
850            Type == RHS->getRawType() && Value == RHS->getValue();
851   }
852 
853   unsigned getHashValue() const { return hash_combine(Tag, Name, Type, Value); }
854 };
855 
856 template <> struct MDNodeKeyImpl<DIGlobalVariable> {
857   Metadata *Scope;
858   MDString *Name;
859   MDString *LinkageName;
860   Metadata *File;
861   unsigned Line;
862   Metadata *Type;
863   bool IsLocalToUnit;
864   bool IsDefinition;
865   Metadata *StaticDataMemberDeclaration;
866   Metadata *TemplateParams;
867   uint32_t AlignInBits;
868 
869   MDNodeKeyImpl(Metadata *Scope, MDString *Name, MDString *LinkageName,
870                 Metadata *File, unsigned Line, Metadata *Type,
871                 bool IsLocalToUnit, bool IsDefinition,
872                 Metadata *StaticDataMemberDeclaration, Metadata *TemplateParams,
873                 uint32_t AlignInBits)
874       : Scope(Scope), Name(Name), LinkageName(LinkageName), File(File),
875         Line(Line), Type(Type), IsLocalToUnit(IsLocalToUnit),
876         IsDefinition(IsDefinition),
877         StaticDataMemberDeclaration(StaticDataMemberDeclaration),
878         TemplateParams(TemplateParams), AlignInBits(AlignInBits) {}
879   MDNodeKeyImpl(const DIGlobalVariable *N)
880       : Scope(N->getRawScope()), Name(N->getRawName()),
881         LinkageName(N->getRawLinkageName()), File(N->getRawFile()),
882         Line(N->getLine()), Type(N->getRawType()),
883         IsLocalToUnit(N->isLocalToUnit()), IsDefinition(N->isDefinition()),
884         StaticDataMemberDeclaration(N->getRawStaticDataMemberDeclaration()),
885         TemplateParams(N->getRawTemplateParams()),
886         AlignInBits(N->getAlignInBits()) {}
887 
888   bool isKeyOf(const DIGlobalVariable *RHS) const {
889     return Scope == RHS->getRawScope() && Name == RHS->getRawName() &&
890            LinkageName == RHS->getRawLinkageName() &&
891            File == RHS->getRawFile() && Line == RHS->getLine() &&
892            Type == RHS->getRawType() && IsLocalToUnit == RHS->isLocalToUnit() &&
893            IsDefinition == RHS->isDefinition() &&
894            StaticDataMemberDeclaration ==
895                RHS->getRawStaticDataMemberDeclaration() &&
896            TemplateParams == RHS->getRawTemplateParams() &&
897            AlignInBits == RHS->getAlignInBits();
898   }
899 
900   unsigned getHashValue() const {
901     // We do not use AlignInBits in hashing function here on purpose:
902     // in most cases this param for local variable is zero (for function param
903     // it is always zero). This leads to lots of hash collisions and errors on
904     // cases with lots of similar variables.
905     // clang/test/CodeGen/debug-info-257-args.c is an example of this problem,
906     // generated IR is random for each run and test fails with Align included.
907     // TODO: make hashing work fine with such situations
908     return hash_combine(Scope, Name, LinkageName, File, Line, Type,
909                         IsLocalToUnit, IsDefinition, /* AlignInBits, */
910                         StaticDataMemberDeclaration);
911   }
912 };
913 
914 template <> struct MDNodeKeyImpl<DILocalVariable> {
915   Metadata *Scope;
916   MDString *Name;
917   Metadata *File;
918   unsigned Line;
919   Metadata *Type;
920   unsigned Arg;
921   unsigned Flags;
922   uint32_t AlignInBits;
923 
924   MDNodeKeyImpl(Metadata *Scope, MDString *Name, Metadata *File, unsigned Line,
925                 Metadata *Type, unsigned Arg, unsigned Flags,
926                 uint32_t AlignInBits)
927       : Scope(Scope), Name(Name), File(File), Line(Line), Type(Type), Arg(Arg),
928         Flags(Flags), AlignInBits(AlignInBits) {}
929   MDNodeKeyImpl(const DILocalVariable *N)
930       : Scope(N->getRawScope()), Name(N->getRawName()), File(N->getRawFile()),
931         Line(N->getLine()), Type(N->getRawType()), Arg(N->getArg()),
932         Flags(N->getFlags()), AlignInBits(N->getAlignInBits()) {}
933 
934   bool isKeyOf(const DILocalVariable *RHS) const {
935     return Scope == RHS->getRawScope() && Name == RHS->getRawName() &&
936            File == RHS->getRawFile() && Line == RHS->getLine() &&
937            Type == RHS->getRawType() && Arg == RHS->getArg() &&
938            Flags == RHS->getFlags() && AlignInBits == RHS->getAlignInBits();
939   }
940 
941   unsigned getHashValue() const {
942     // We do not use AlignInBits in hashing function here on purpose:
943     // in most cases this param for local variable is zero (for function param
944     // it is always zero). This leads to lots of hash collisions and errors on
945     // cases with lots of similar variables.
946     // clang/test/CodeGen/debug-info-257-args.c is an example of this problem,
947     // generated IR is random for each run and test fails with Align included.
948     // TODO: make hashing work fine with such situations
949     return hash_combine(Scope, Name, File, Line, Type, Arg, Flags);
950   }
951 };
952 
953 template <> struct MDNodeKeyImpl<DILabel> {
954   Metadata *Scope;
955   MDString *Name;
956   Metadata *File;
957   unsigned Line;
958 
959   MDNodeKeyImpl(Metadata *Scope, MDString *Name, Metadata *File, unsigned Line)
960       : Scope(Scope), Name(Name), File(File), Line(Line) {}
961   MDNodeKeyImpl(const DILabel *N)
962       : Scope(N->getRawScope()), Name(N->getRawName()), File(N->getRawFile()),
963         Line(N->getLine()) {}
964 
965   bool isKeyOf(const DILabel *RHS) const {
966     return Scope == RHS->getRawScope() && Name == RHS->getRawName() &&
967            File == RHS->getRawFile() && Line == RHS->getLine();
968   }
969 
970   /// Using name and line to get hash value. It should already be mostly unique.
971   unsigned getHashValue() const {
972     return hash_combine(Scope, Name, Line);
973   }
974 };
975 
976 template <> struct MDNodeKeyImpl<DIExpression> {
977   ArrayRef<uint64_t> Elements;
978 
979   MDNodeKeyImpl(ArrayRef<uint64_t> Elements) : Elements(Elements) {}
980   MDNodeKeyImpl(const DIExpression *N) : Elements(N->getElements()) {}
981 
982   bool isKeyOf(const DIExpression *RHS) const {
983     return Elements == RHS->getElements();
984   }
985 
986   unsigned getHashValue() const {
987     return hash_combine_range(Elements.begin(), Elements.end());
988   }
989 };
990 
991 template <> struct MDNodeKeyImpl<DIGlobalVariableExpression> {
992   Metadata *Variable;
993   Metadata *Expression;
994 
995   MDNodeKeyImpl(Metadata *Variable, Metadata *Expression)
996       : Variable(Variable), Expression(Expression) {}
997   MDNodeKeyImpl(const DIGlobalVariableExpression *N)
998       : Variable(N->getRawVariable()), Expression(N->getRawExpression()) {}
999 
1000   bool isKeyOf(const DIGlobalVariableExpression *RHS) const {
1001     return Variable == RHS->getRawVariable() &&
1002            Expression == RHS->getRawExpression();
1003   }
1004 
1005   unsigned getHashValue() const { return hash_combine(Variable, Expression); }
1006 };
1007 
1008 template <> struct MDNodeKeyImpl<DIObjCProperty> {
1009   MDString *Name;
1010   Metadata *File;
1011   unsigned Line;
1012   MDString *GetterName;
1013   MDString *SetterName;
1014   unsigned Attributes;
1015   Metadata *Type;
1016 
1017   MDNodeKeyImpl(MDString *Name, Metadata *File, unsigned Line,
1018                 MDString *GetterName, MDString *SetterName, unsigned Attributes,
1019                 Metadata *Type)
1020       : Name(Name), File(File), Line(Line), GetterName(GetterName),
1021         SetterName(SetterName), Attributes(Attributes), Type(Type) {}
1022   MDNodeKeyImpl(const DIObjCProperty *N)
1023       : Name(N->getRawName()), File(N->getRawFile()), Line(N->getLine()),
1024         GetterName(N->getRawGetterName()), SetterName(N->getRawSetterName()),
1025         Attributes(N->getAttributes()), Type(N->getRawType()) {}
1026 
1027   bool isKeyOf(const DIObjCProperty *RHS) const {
1028     return Name == RHS->getRawName() && File == RHS->getRawFile() &&
1029            Line == RHS->getLine() && GetterName == RHS->getRawGetterName() &&
1030            SetterName == RHS->getRawSetterName() &&
1031            Attributes == RHS->getAttributes() && Type == RHS->getRawType();
1032   }
1033 
1034   unsigned getHashValue() const {
1035     return hash_combine(Name, File, Line, GetterName, SetterName, Attributes,
1036                         Type);
1037   }
1038 };
1039 
1040 template <> struct MDNodeKeyImpl<DIImportedEntity> {
1041   unsigned Tag;
1042   Metadata *Scope;
1043   Metadata *Entity;
1044   Metadata *File;
1045   unsigned Line;
1046   MDString *Name;
1047 
1048   MDNodeKeyImpl(unsigned Tag, Metadata *Scope, Metadata *Entity, Metadata *File,
1049                 unsigned Line, MDString *Name)
1050       : Tag(Tag), Scope(Scope), Entity(Entity), File(File), Line(Line),
1051         Name(Name) {}
1052   MDNodeKeyImpl(const DIImportedEntity *N)
1053       : Tag(N->getTag()), Scope(N->getRawScope()), Entity(N->getRawEntity()),
1054         File(N->getRawFile()), Line(N->getLine()), Name(N->getRawName()) {}
1055 
1056   bool isKeyOf(const DIImportedEntity *RHS) const {
1057     return Tag == RHS->getTag() && Scope == RHS->getRawScope() &&
1058            Entity == RHS->getRawEntity() && File == RHS->getFile() &&
1059            Line == RHS->getLine() && Name == RHS->getRawName();
1060   }
1061 
1062   unsigned getHashValue() const {
1063     return hash_combine(Tag, Scope, Entity, File, Line, Name);
1064   }
1065 };
1066 
1067 template <> struct MDNodeKeyImpl<DIMacro> {
1068   unsigned MIType;
1069   unsigned Line;
1070   MDString *Name;
1071   MDString *Value;
1072 
1073   MDNodeKeyImpl(unsigned MIType, unsigned Line, MDString *Name, MDString *Value)
1074       : MIType(MIType), Line(Line), Name(Name), Value(Value) {}
1075   MDNodeKeyImpl(const DIMacro *N)
1076       : MIType(N->getMacinfoType()), Line(N->getLine()), Name(N->getRawName()),
1077         Value(N->getRawValue()) {}
1078 
1079   bool isKeyOf(const DIMacro *RHS) const {
1080     return MIType == RHS->getMacinfoType() && Line == RHS->getLine() &&
1081            Name == RHS->getRawName() && Value == RHS->getRawValue();
1082   }
1083 
1084   unsigned getHashValue() const {
1085     return hash_combine(MIType, Line, Name, Value);
1086   }
1087 };
1088 
1089 template <> struct MDNodeKeyImpl<DIMacroFile> {
1090   unsigned MIType;
1091   unsigned Line;
1092   Metadata *File;
1093   Metadata *Elements;
1094 
1095   MDNodeKeyImpl(unsigned MIType, unsigned Line, Metadata *File,
1096                 Metadata *Elements)
1097       : MIType(MIType), Line(Line), File(File), Elements(Elements) {}
1098   MDNodeKeyImpl(const DIMacroFile *N)
1099       : MIType(N->getMacinfoType()), Line(N->getLine()), File(N->getRawFile()),
1100         Elements(N->getRawElements()) {}
1101 
1102   bool isKeyOf(const DIMacroFile *RHS) const {
1103     return MIType == RHS->getMacinfoType() && Line == RHS->getLine() &&
1104            File == RHS->getRawFile() && Elements == RHS->getRawElements();
1105   }
1106 
1107   unsigned getHashValue() const {
1108     return hash_combine(MIType, Line, File, Elements);
1109   }
1110 };
1111 
1112 /// DenseMapInfo for MDNode subclasses.
1113 template <class NodeTy> struct MDNodeInfo {
1114   using KeyTy = MDNodeKeyImpl<NodeTy>;
1115   using SubsetEqualTy = MDNodeSubsetEqualImpl<NodeTy>;
1116 
1117   static inline NodeTy *getEmptyKey() {
1118     return DenseMapInfo<NodeTy *>::getEmptyKey();
1119   }
1120 
1121   static inline NodeTy *getTombstoneKey() {
1122     return DenseMapInfo<NodeTy *>::getTombstoneKey();
1123   }
1124 
1125   static unsigned getHashValue(const KeyTy &Key) { return Key.getHashValue(); }
1126 
1127   static unsigned getHashValue(const NodeTy *N) {
1128     return KeyTy(N).getHashValue();
1129   }
1130 
1131   static bool isEqual(const KeyTy &LHS, const NodeTy *RHS) {
1132     if (RHS == getEmptyKey() || RHS == getTombstoneKey())
1133       return false;
1134     return SubsetEqualTy::isSubsetEqual(LHS, RHS) || LHS.isKeyOf(RHS);
1135   }
1136 
1137   static bool isEqual(const NodeTy *LHS, const NodeTy *RHS) {
1138     if (LHS == RHS)
1139       return true;
1140     if (RHS == getEmptyKey() || RHS == getTombstoneKey())
1141       return false;
1142     return SubsetEqualTy::isSubsetEqual(LHS, RHS);
1143   }
1144 };
1145 
1146 #define HANDLE_MDNODE_LEAF(CLASS) using CLASS##Info = MDNodeInfo<CLASS>;
1147 #include "llvm/IR/Metadata.def"
1148 
1149 /// Map-like storage for metadata attachments.
1150 class MDAttachmentMap {
1151   SmallVector<std::pair<unsigned, TrackingMDNodeRef>, 2> Attachments;
1152 
1153 public:
1154   bool empty() const { return Attachments.empty(); }
1155   size_t size() const { return Attachments.size(); }
1156 
1157   /// Get a particular attachment (if any).
1158   MDNode *lookup(unsigned ID) const;
1159 
1160   /// Set an attachment to a particular node.
1161   ///
1162   /// Set the \c ID attachment to \c MD, replacing the current attachment at \c
1163   /// ID (if anyway).
1164   void set(unsigned ID, MDNode &MD);
1165 
1166   /// Remove an attachment.
1167   ///
1168   /// Remove the attachment at \c ID, if any.
1169   bool erase(unsigned ID);
1170 
1171   /// Copy out all the attachments.
1172   ///
1173   /// Copies all the current attachments into \c Result, sorting by attachment
1174   /// ID.  This function does \em not clear \c Result.
1175   void getAll(SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const;
1176 
1177   /// Erase matching attachments.
1178   ///
1179   /// Erases all attachments matching the \c shouldRemove predicate.
1180   template <class PredTy> void remove_if(PredTy shouldRemove) {
1181     Attachments.erase(llvm::remove_if(Attachments, shouldRemove),
1182                       Attachments.end());
1183   }
1184 };
1185 
1186 /// Multimap-like storage for metadata attachments for globals. This differs
1187 /// from MDAttachmentMap in that it allows multiple attachments per metadata
1188 /// kind.
1189 class MDGlobalAttachmentMap {
1190   struct Attachment {
1191     unsigned MDKind;
1192     TrackingMDNodeRef Node;
1193   };
1194   SmallVector<Attachment, 1> Attachments;
1195 
1196 public:
1197   bool empty() const { return Attachments.empty(); }
1198 
1199   /// Appends all attachments with the given ID to \c Result in insertion order.
1200   /// If the global has no attachments with the given ID, or if ID is invalid,
1201   /// leaves Result unchanged.
1202   void get(unsigned ID, SmallVectorImpl<MDNode *> &Result) const;
1203 
1204   /// Returns the first attachment with the given ID or nullptr if no such
1205   /// attachment exists.
1206   MDNode *lookup(unsigned ID) const;
1207 
1208   void insert(unsigned ID, MDNode &MD);
1209   bool erase(unsigned ID);
1210 
1211   /// Appends all attachments for the global to \c Result, sorting by attachment
1212   /// ID. Attachments with the same ID appear in insertion order. This function
1213   /// does \em not clear \c Result.
1214   void getAll(SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const;
1215 };
1216 
1217 class LLVMContextImpl {
1218 public:
1219   /// OwnedModules - The set of modules instantiated in this context, and which
1220   /// will be automatically deleted if this context is deleted.
1221   SmallPtrSet<Module*, 4> OwnedModules;
1222 
1223   LLVMContext::InlineAsmDiagHandlerTy InlineAsmDiagHandler = nullptr;
1224   void *InlineAsmDiagContext = nullptr;
1225 
1226   std::unique_ptr<DiagnosticHandler> DiagHandler;
1227   bool RespectDiagnosticFilters = false;
1228   bool DiagnosticsHotnessRequested = false;
1229   uint64_t DiagnosticsHotnessThreshold = 0;
1230   std::unique_ptr<yaml::Output> DiagnosticsOutputFile;
1231 
1232   LLVMContext::YieldCallbackTy YieldCallback = nullptr;
1233   void *YieldOpaqueHandle = nullptr;
1234 
1235   using IntMapTy =
1236       DenseMap<APInt, std::unique_ptr<ConstantInt>, DenseMapAPIntKeyInfo>;
1237   IntMapTy IntConstants;
1238 
1239   using FPMapTy =
1240       DenseMap<APFloat, std::unique_ptr<ConstantFP>, DenseMapAPFloatKeyInfo>;
1241   FPMapTy FPConstants;
1242 
1243   FoldingSet<AttributeImpl> AttrsSet;
1244   FoldingSet<AttributeListImpl> AttrsLists;
1245   FoldingSet<AttributeSetNode> AttrsSetNodes;
1246 
1247   StringMap<MDString, BumpPtrAllocator> MDStringCache;
1248   DenseMap<Value *, ValueAsMetadata *> ValuesAsMetadata;
1249   DenseMap<Metadata *, MetadataAsValue *> MetadataAsValues;
1250 
1251   DenseMap<const Value*, ValueName*> ValueNames;
1252 
1253 #define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS)                                    \
1254   DenseSet<CLASS *, CLASS##Info> CLASS##s;
1255 #include "llvm/IR/Metadata.def"
1256 
1257   // Optional map for looking up composite types by identifier.
1258   Optional<DenseMap<const MDString *, DICompositeType *>> DITypeMap;
1259 
1260   // MDNodes may be uniqued or not uniqued.  When they're not uniqued, they
1261   // aren't in the MDNodeSet, but they're still shared between objects, so no
1262   // one object can destroy them.  Keep track of them here so we can delete
1263   // them on context teardown.
1264   std::vector<MDNode *> DistinctMDNodes;
1265 
1266   DenseMap<Type *, std::unique_ptr<ConstantAggregateZero>> CAZConstants;
1267 
1268   using ArrayConstantsTy = ConstantUniqueMap<ConstantArray>;
1269   ArrayConstantsTy ArrayConstants;
1270 
1271   using StructConstantsTy = ConstantUniqueMap<ConstantStruct>;
1272   StructConstantsTy StructConstants;
1273 
1274   using VectorConstantsTy = ConstantUniqueMap<ConstantVector>;
1275   VectorConstantsTy VectorConstants;
1276 
1277   DenseMap<PointerType *, std::unique_ptr<ConstantPointerNull>> CPNConstants;
1278 
1279   DenseMap<Type *, std::unique_ptr<UndefValue>> UVConstants;
1280 
1281   StringMap<ConstantDataSequential*> CDSConstants;
1282 
1283   DenseMap<std::pair<const Function *, const BasicBlock *>, BlockAddress *>
1284     BlockAddresses;
1285   ConstantUniqueMap<ConstantExpr> ExprConstants;
1286 
1287   ConstantUniqueMap<InlineAsm> InlineAsms;
1288 
1289   ConstantInt *TheTrueVal = nullptr;
1290   ConstantInt *TheFalseVal = nullptr;
1291 
1292   std::unique_ptr<ConstantTokenNone> TheNoneToken;
1293 
1294   // Basic type instances.
1295   Type VoidTy, LabelTy, HalfTy, FloatTy, DoubleTy, MetadataTy, TokenTy;
1296   Type X86_FP80Ty, FP128Ty, PPC_FP128Ty, X86_MMXTy;
1297   IntegerType Int1Ty, Int8Ty, Int16Ty, Int32Ty, Int64Ty, Int128Ty;
1298 
1299   /// TypeAllocator - All dynamically allocated types are allocated from this.
1300   /// They live forever until the context is torn down.
1301   BumpPtrAllocator TypeAllocator;
1302 
1303   DenseMap<unsigned, IntegerType*> IntegerTypes;
1304 
1305   using FunctionTypeSet = DenseSet<FunctionType *, FunctionTypeKeyInfo>;
1306   FunctionTypeSet FunctionTypes;
1307   using StructTypeSet = DenseSet<StructType *, AnonStructTypeKeyInfo>;
1308   StructTypeSet AnonStructTypes;
1309   StringMap<StructType*> NamedStructTypes;
1310   unsigned NamedStructTypesUniqueID = 0;
1311 
1312   DenseMap<std::pair<Type *, uint64_t>, ArrayType*> ArrayTypes;
1313   DenseMap<std::pair<Type *, unsigned>, VectorType*> VectorTypes;
1314   DenseMap<Type*, PointerType*> PointerTypes;  // Pointers in AddrSpace = 0
1315   DenseMap<std::pair<Type*, unsigned>, PointerType*> ASPointerTypes;
1316 
1317   /// ValueHandles - This map keeps track of all of the value handles that are
1318   /// watching a Value*.  The Value::HasValueHandle bit is used to know
1319   /// whether or not a value has an entry in this map.
1320   using ValueHandlesTy = DenseMap<Value *, ValueHandleBase *>;
1321   ValueHandlesTy ValueHandles;
1322 
1323   /// CustomMDKindNames - Map to hold the metadata string to ID mapping.
1324   StringMap<unsigned> CustomMDKindNames;
1325 
1326   /// Collection of per-instruction metadata used in this context.
1327   DenseMap<const Instruction *, MDAttachmentMap> InstructionMetadata;
1328 
1329   /// Collection of per-GlobalObject metadata used in this context.
1330   DenseMap<const GlobalObject *, MDGlobalAttachmentMap> GlobalObjectMetadata;
1331 
1332   /// Collection of per-GlobalObject sections used in this context.
1333   DenseMap<const GlobalObject *, StringRef> GlobalObjectSections;
1334 
1335   /// Stable collection of section strings.
1336   StringSet<> SectionStrings;
1337 
1338   /// DiscriminatorTable - This table maps file:line locations to an
1339   /// integer representing the next DWARF path discriminator to assign to
1340   /// instructions in different blocks at the same location.
1341   DenseMap<std::pair<const char *, unsigned>, unsigned> DiscriminatorTable;
1342 
1343   int getOrAddScopeRecordIdxEntry(MDNode *N, int ExistingIdx);
1344   int getOrAddScopeInlinedAtIdxEntry(MDNode *Scope, MDNode *IA,int ExistingIdx);
1345 
1346   /// A set of interned tags for operand bundles.  The StringMap maps
1347   /// bundle tags to their IDs.
1348   ///
1349   /// \see LLVMContext::getOperandBundleTagID
1350   StringMap<uint32_t> BundleTagCache;
1351 
1352   StringMapEntry<uint32_t> *getOrInsertBundleTag(StringRef Tag);
1353   void getOperandBundleTags(SmallVectorImpl<StringRef> &Tags) const;
1354   uint32_t getOperandBundleTagID(StringRef Tag) const;
1355 
1356   /// A set of interned synchronization scopes.  The StringMap maps
1357   /// synchronization scope names to their respective synchronization scope IDs.
1358   StringMap<SyncScope::ID> SSC;
1359 
1360   /// getOrInsertSyncScopeID - Maps synchronization scope name to
1361   /// synchronization scope ID.  Every synchronization scope registered with
1362   /// LLVMContext has unique ID except pre-defined ones.
1363   SyncScope::ID getOrInsertSyncScopeID(StringRef SSN);
1364 
1365   /// getSyncScopeNames - Populates client supplied SmallVector with
1366   /// synchronization scope names registered with LLVMContext.  Synchronization
1367   /// scope names are ordered by increasing synchronization scope IDs.
1368   void getSyncScopeNames(SmallVectorImpl<StringRef> &SSNs) const;
1369 
1370   /// Maintain the GC name for each function.
1371   ///
1372   /// This saves allocating an additional word in Function for programs which
1373   /// do not use GC (i.e., most programs) at the cost of increased overhead for
1374   /// clients which do use GC.
1375   DenseMap<const Function*, std::string> GCNames;
1376 
1377   /// Flag to indicate if Value (other than GlobalValue) retains their name or
1378   /// not.
1379   bool DiscardValueNames = false;
1380 
1381   LLVMContextImpl(LLVMContext &C);
1382   ~LLVMContextImpl();
1383 
1384   /// Destroy the ConstantArrays if they are not used.
1385   void dropTriviallyDeadConstantArrays();
1386 
1387   mutable OptPassGate *OPG = nullptr;
1388 
1389   /// Access the object which can disable optional passes and individual
1390   /// optimizations at compile time.
1391   OptPassGate &getOptPassGate() const;
1392 
1393   /// Set the object which can disable optional passes and individual
1394   /// optimizations at compile time.
1395   ///
1396   /// The lifetime of the object must be guaranteed to extend as long as the
1397   /// LLVMContext is used by compilation.
1398   void setOptPassGate(OptPassGate&);
1399 };
1400 
1401 } // end namespace llvm
1402 
1403 #endif // LLVM_LIB_IR_LLVMCONTEXTIMPL_H
1404