contrib/llvm/lib/IR/LLVMContextImpl.h

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