LCOV - code coverage report
Current view: top level - lib/IR - LLVMContextImpl.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 359 359 100.0 %
Date: 2017-09-14 15:23:50 Functions: 69 69 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13