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