diff --git a/clang/include/clang/AST/TypeOrdering.h b/clang/include/clang/AST/TypeOrdering.h --- a/clang/include/clang/AST/TypeOrdering.h +++ b/clang/include/clang/AST/TypeOrdering.h @@ -34,7 +34,6 @@ } namespace llvm { - template struct DenseMapInfo; template<> struct DenseMapInfo { static inline clang::QualType getEmptyKey() { return clang::QualType(); } diff --git a/clang/include/clang/Basic/SourceLocation.h b/clang/include/clang/Basic/SourceLocation.h --- a/clang/include/clang/Basic/SourceLocation.h +++ b/clang/include/clang/Basic/SourceLocation.h @@ -23,8 +23,6 @@ namespace llvm { -template struct DenseMapInfo; - class FoldingSetNodeID; template struct FoldingSetTrait; @@ -467,7 +465,7 @@ /// Define DenseMapInfo so that FileID's can be used as keys in DenseMap and /// DenseSets. template <> - struct DenseMapInfo { + struct DenseMapInfo { static clang::FileID getEmptyKey() { return {}; } @@ -488,7 +486,7 @@ /// Define DenseMapInfo so that SourceLocation's can be used as keys in /// DenseMap and DenseSet. This trait class is eqivalent to /// DenseMapInfo which uses SourceLocation::ID is used as a key. - template <> struct DenseMapInfo { + template <> struct DenseMapInfo { static clang::SourceLocation getEmptyKey() { constexpr clang::SourceLocation::UIntTy Zero = 0; return clang::SourceLocation::getFromRawEncoding(~Zero); diff --git a/clang/include/clang/Sema/Sema.h b/clang/include/clang/Sema/Sema.h --- a/clang/include/clang/Sema/Sema.h +++ b/clang/include/clang/Sema/Sema.h @@ -74,7 +74,6 @@ namespace llvm { class APSInt; - template struct DenseMapInfo; template class DenseSet; class SmallBitVector; struct InlineAsmIdentifierInfo; diff --git a/lldb/include/lldb/Utility/ConstString.h b/lldb/include/lldb/Utility/ConstString.h --- a/lldb/include/lldb/Utility/ConstString.h +++ b/lldb/include/lldb/Utility/ConstString.h @@ -409,7 +409,7 @@ static size_t StaticMemorySize(); protected: - template friend struct ::llvm::DenseMapInfo; + template friend struct ::llvm::DenseMapInfo; /// Only used by DenseMapInfo. static ConstString FromStringPoolPointer(const char *ptr) { ConstString s; diff --git a/llvm/include/llvm/ADT/APInt.h b/llvm/include/llvm/ADT/APInt.h --- a/llvm/include/llvm/ADT/APInt.h +++ b/llvm/include/llvm/ADT/APInt.h @@ -31,7 +31,7 @@ template class SmallVectorImpl; template class ArrayRef; template class Optional; -template struct DenseMapInfo; +template struct DenseMapInfo; class APInt; @@ -1817,7 +1817,7 @@ unsigned BitWidth; ///< The number of bits in this APInt. - friend struct DenseMapInfo; + friend struct DenseMapInfo; friend class APSInt; /// This constructor is used only internally for speed of construction of @@ -2251,7 +2251,7 @@ void LoadIntFromMemory(APInt &IntVal, const uint8_t *Src, unsigned LoadBytes); /// Provide DenseMapInfo for APInt. -template <> struct DenseMapInfo { +template <> struct DenseMapInfo { static inline APInt getEmptyKey() { APInt V(nullptr, 0); V.U.VAL = 0; diff --git a/llvm/include/llvm/ADT/APSInt.h b/llvm/include/llvm/ADT/APSInt.h --- a/llvm/include/llvm/ADT/APSInt.h +++ b/llvm/include/llvm/ADT/APSInt.h @@ -344,17 +344,17 @@ } /// Provide DenseMapInfo for APSInt, using the DenseMapInfo for APInt. -template <> struct DenseMapInfo { +template <> struct DenseMapInfo { static inline APSInt getEmptyKey() { - return APSInt(DenseMapInfo::getEmptyKey()); + return APSInt(DenseMapInfo::getEmptyKey()); } static inline APSInt getTombstoneKey() { - return APSInt(DenseMapInfo::getTombstoneKey()); + return APSInt(DenseMapInfo::getTombstoneKey()); } static unsigned getHashValue(const APSInt &Key) { - return DenseMapInfo::getHashValue(Key); + return DenseMapInfo::getHashValue(Key); } static bool isEqual(const APSInt &LHS, const APSInt &RHS) { diff --git a/llvm/include/llvm/ADT/ArrayRef.h b/llvm/include/llvm/ADT/ArrayRef.h --- a/llvm/include/llvm/ADT/ArrayRef.h +++ b/llvm/include/llvm/ADT/ArrayRef.h @@ -26,8 +26,6 @@ namespace llvm { - template struct DenseMapInfo; - /// ArrayRef - Represent a constant reference to an array (0 or more elements /// consecutively in memory), i.e. a start pointer and a length. It allows /// various APIs to take consecutive elements easily and conveniently. @@ -572,7 +570,7 @@ } // Provide DenseMapInfo for ArrayRefs. - template struct DenseMapInfo> { + template struct DenseMapInfo, void> { static inline ArrayRef getEmptyKey() { return ArrayRef( reinterpret_cast(~static_cast(0)), size_t(0)); diff --git a/llvm/include/llvm/ADT/DenseMapInfo.h b/llvm/include/llvm/ADT/DenseMapInfo.h --- a/llvm/include/llvm/ADT/DenseMapInfo.h +++ b/llvm/include/llvm/ADT/DenseMapInfo.h @@ -39,7 +39,12 @@ } // end namespace detail -template +/// An information struct used to provide DenseMap with the various necessary +/// components for a given value type `T`. `Enable` is an optional additional +/// parameter that is used to support SFINAE (generally using std::enable_if_t) +/// in derived DenseMapInfo specializations; in non-SFINAE use cases this should +/// just be `void`. +template struct DenseMapInfo { //static inline T getEmptyKey(); //static inline T getTombstoneKey(); diff --git a/llvm/include/llvm/ADT/Hashing.h b/llvm/include/llvm/ADT/Hashing.h --- a/llvm/include/llvm/ADT/Hashing.h +++ b/llvm/include/llvm/ADT/Hashing.h @@ -56,7 +56,7 @@ #include namespace llvm { -template struct DenseMapInfo; +template struct DenseMapInfo; /// An opaque object representing a hash code. /// @@ -678,7 +678,7 @@ return hash_combine_range(arg.begin(), arg.end()); } -template <> struct DenseMapInfo { +template <> struct DenseMapInfo { static inline hash_code getEmptyKey() { return hash_code(-1); } static inline hash_code getTombstoneKey() { return hash_code(-2); } static unsigned getHashValue(hash_code val) { return val; } diff --git a/llvm/include/llvm/ADT/ImmutableList.h b/llvm/include/llvm/ADT/ImmutableList.h --- a/llvm/include/llvm/ADT/ImmutableList.h +++ b/llvm/include/llvm/ADT/ImmutableList.h @@ -220,8 +220,7 @@ // Partially-specialized Traits. //===----------------------------------------------------------------------===// -template struct DenseMapInfo; -template struct DenseMapInfo> { +template struct DenseMapInfo, void> { static inline ImmutableList getEmptyKey() { return reinterpret_cast*>(-1); } diff --git a/llvm/include/llvm/ADT/PointerIntPair.h b/llvm/include/llvm/ADT/PointerIntPair.h --- a/llvm/include/llvm/ADT/PointerIntPair.h +++ b/llvm/include/llvm/ADT/PointerIntPair.h @@ -22,7 +22,7 @@ namespace llvm { -template struct DenseMapInfo; +template struct DenseMapInfo; template struct PointerIntPairInfo; @@ -192,7 +192,7 @@ // Provide specialization of DenseMapInfo for PointerIntPair. template -struct DenseMapInfo> { +struct DenseMapInfo, void> { using Ty = PointerIntPair; static Ty getEmptyKey() { diff --git a/llvm/include/llvm/ADT/StringRef.h b/llvm/include/llvm/ADT/StringRef.h --- a/llvm/include/llvm/ADT/StringRef.h +++ b/llvm/include/llvm/ADT/StringRef.h @@ -35,7 +35,6 @@ class APInt; class hash_code; template class SmallVectorImpl; - template struct DenseMapInfo; class StringRef; /// Helper functions for StringRef::getAsInteger. @@ -949,7 +948,7 @@ hash_code hash_value(StringRef S); // Provide DenseMapInfo for StringRefs. - template <> struct DenseMapInfo { + template <> struct DenseMapInfo { static inline StringRef getEmptyKey() { return StringRef( reinterpret_cast(~static_cast(0)), 0); diff --git a/llvm/include/llvm/BinaryFormat/WasmTraits.h b/llvm/include/llvm/BinaryFormat/WasmTraits.h --- a/llvm/include/llvm/BinaryFormat/WasmTraits.h +++ b/llvm/include/llvm/BinaryFormat/WasmTraits.h @@ -18,10 +18,8 @@ namespace llvm { -template struct DenseMapInfo; - // Traits for using WasmSignature in a DenseMap. -template <> struct DenseMapInfo { +template <> struct DenseMapInfo { static wasm::WasmSignature getEmptyKey() { wasm::WasmSignature Sig; Sig.State = wasm::WasmSignature::Empty; @@ -47,7 +45,7 @@ }; // Traits for using WasmGlobalType in a DenseMap -template <> struct DenseMapInfo { +template <> struct DenseMapInfo { static wasm::WasmGlobalType getEmptyKey() { return wasm::WasmGlobalType{1, true}; } @@ -64,7 +62,7 @@ }; // Traits for using WasmLimits in a DenseMap -template <> struct DenseMapInfo { +template <> struct DenseMapInfo { static wasm::WasmLimits getEmptyKey() { return wasm::WasmLimits{0xff, 0xff, 0xff}; } @@ -86,19 +84,19 @@ }; // Traits for using WasmTableType in a DenseMap -template <> struct DenseMapInfo { +template <> struct DenseMapInfo { static wasm::WasmTableType getEmptyKey() { - return wasm::WasmTableType{0, - DenseMapInfo::getEmptyKey()}; + return wasm::WasmTableType{ + 0, DenseMapInfo::getEmptyKey()}; } static wasm::WasmTableType getTombstoneKey() { return wasm::WasmTableType{ - 1, DenseMapInfo::getTombstoneKey()}; + 1, DenseMapInfo::getTombstoneKey()}; } static unsigned getHashValue(const wasm::WasmTableType &TableType) { return hash_combine( TableType.ElemType, - DenseMapInfo::getHashValue(TableType.Limits)); + DenseMapInfo::getHashValue(TableType.Limits)); } static bool isEqual(const wasm::WasmTableType &LHS, const wasm::WasmTableType &RHS) { diff --git a/llvm/include/llvm/CodeGen/SelectionDAGNodes.h b/llvm/include/llvm/CodeGen/SelectionDAGNodes.h --- a/llvm/include/llvm/CodeGen/SelectionDAGNodes.h +++ b/llvm/include/llvm/CodeGen/SelectionDAGNodes.h @@ -58,7 +58,6 @@ class APInt; class Constant; -template struct DenseMapInfo; class GlobalValue; class MachineBasicBlock; class MachineConstantPoolValue; diff --git a/llvm/include/llvm/IR/Attributes.h b/llvm/include/llvm/IR/Attributes.h --- a/llvm/include/llvm/IR/Attributes.h +++ b/llvm/include/llvm/IR/Attributes.h @@ -37,7 +37,6 @@ class AttributeImpl; class AttributeListImpl; class AttributeSetNode; -template struct DenseMapInfo; class FoldingSetNodeID; class Function; class LLVMContext; @@ -266,7 +265,7 @@ /// and removing string or integer attributes involves a FoldingSet lookup. class AttributeSet { friend AttributeListImpl; - template friend struct DenseMapInfo; + template friend struct DenseMapInfo; // TODO: Extract AvailableAttrs from AttributeSetNode and store them here. // This will allow an efficient implementation of addAttribute and @@ -367,7 +366,7 @@ //===----------------------------------------------------------------------===// /// \class /// Provide DenseMapInfo for AttributeSet. -template <> struct DenseMapInfo { +template <> struct DenseMapInfo { static AttributeSet getEmptyKey() { auto Val = static_cast(-1); Val <<= PointerLikeTypeTraits::NumLowBitsAvailable; @@ -409,7 +408,7 @@ friend class AttributeListImpl; friend class AttributeSet; friend class AttributeSetNode; - template friend struct DenseMapInfo; + template friend struct DenseMapInfo; /// The attributes that we are managing. This can be null to represent /// the empty attributes list. @@ -899,7 +898,7 @@ //===----------------------------------------------------------------------===// /// \class /// Provide DenseMapInfo for AttributeList. -template <> struct DenseMapInfo { +template <> struct DenseMapInfo { static AttributeList getEmptyKey() { auto Val = static_cast(-1); Val <<= PointerLikeTypeTraits::NumLowBitsAvailable; diff --git a/llvm/include/llvm/Support/TypeSize.h b/llvm/include/llvm/Support/TypeSize.h --- a/llvm/include/llvm/Support/TypeSize.h +++ b/llvm/include/llvm/Support/TypeSize.h @@ -249,7 +249,7 @@ //===----------------------------------------------------------------------===// // LinearPolySize - base class for fixed- or scalable sizes. -// ^ ^ +// ^ ^ // | | // | +----- ElementCount - Leaf class to represent an element count // | (vscale x unsigned) @@ -499,8 +499,7 @@ return OS; } -template struct DenseMapInfo; -template <> struct DenseMapInfo { +template <> struct DenseMapInfo { static inline ElementCount getEmptyKey() { return ElementCount::getScalable(~0U); } diff --git a/llvm/lib/Support/APInt.cpp b/llvm/lib/Support/APInt.cpp --- a/llvm/lib/Support/APInt.cpp +++ b/llvm/lib/Support/APInt.cpp @@ -569,7 +569,7 @@ hash_combine_range(Arg.U.pVal, Arg.U.pVal + Arg.getNumWords())); } -unsigned DenseMapInfo::getHashValue(const APInt &Key) { +unsigned DenseMapInfo::getHashValue(const APInt &Key) { return static_cast(hash_value(Key)); } diff --git a/llvm/unittests/ADT/DenseMapTest.cpp b/llvm/unittests/ADT/DenseMapTest.cpp --- a/llvm/unittests/ADT/DenseMapTest.cpp +++ b/llvm/unittests/ADT/DenseMapTest.cpp @@ -655,4 +655,47 @@ EXPECT_EQ(Map.find(K2), Map.end()); EXPECT_EQ(Map.find(K3), Map.end()); } +} // namespace + +namespace { +struct A { + A(int value) : value(value) {} + int value; +}; +struct B : public A { + using A::A; +}; +} // namespace + +namespace llvm { +template +struct DenseMapInfo::value>> { + static inline T getEmptyKey() { return {static_cast(~0)}; } + static inline T getTombstoneKey() { return {static_cast(~0U - 1)}; } + static unsigned getHashValue(const T &Val) { return Val.value; } + static bool isEqual(const T &LHS, const T &RHS) { + return LHS.value == RHS.value; + } +}; +} // namespace llvm + +namespace { +TEST(DenseMapCustomTest, SFINAEMapInfo) { + // Test that we can use a pointer to an incomplete type as a DenseMap key. + // This is an important build time optimization, since many classes have + // DenseMap members. + DenseMap Map; + B Keys[3] = {{0}, {1}, {2}}; + Map.insert({Keys[0], 1}); + Map.insert({Keys[1], 2}); + Map.insert({Keys[2], 3}); + EXPECT_EQ(Map.count(Keys[0]), 1u); + EXPECT_EQ(Map[Keys[0]], 1); + EXPECT_EQ(Map[Keys[1]], 2); + EXPECT_EQ(Map[Keys[2]], 3); + Map.clear(); + EXPECT_EQ(Map.find(Keys[0]), Map.end()); + EXPECT_EQ(Map.find(Keys[1]), Map.end()); + EXPECT_EQ(Map.find(Keys[2]), Map.end()); } +} // namespace diff --git a/mlir/include/mlir/Dialect/SPIRV/IR/SPIRVOps.h b/mlir/include/mlir/Dialect/SPIRV/IR/SPIRVOps.h --- a/mlir/include/mlir/Dialect/SPIRV/IR/SPIRVOps.h +++ b/mlir/include/mlir/Dialect/SPIRV/IR/SPIRVOps.h @@ -40,25 +40,6 @@ namespace llvm { -/// spirv::Function ops hash just like pointers. -template <> -struct DenseMapInfo { - static mlir::spirv::FuncOp getEmptyKey() { - auto pointer = llvm::DenseMapInfo::getEmptyKey(); - return mlir::spirv::FuncOp::getFromOpaquePointer(pointer); - } - static mlir::spirv::FuncOp getTombstoneKey() { - auto pointer = llvm::DenseMapInfo::getTombstoneKey(); - return mlir::spirv::FuncOp::getFromOpaquePointer(pointer); - } - static unsigned getHashValue(mlir::spirv::FuncOp val) { - return hash_value(val.getAsOpaquePointer()); - } - static bool isEqual(mlir::spirv::FuncOp LHS, mlir::spirv::FuncOp RHS) { - return LHS == RHS; - } -}; - /// Allow stealing the low bits of spirv::Function ops. template <> struct PointerLikeTypeTraits { diff --git a/mlir/include/mlir/IR/Attributes.h b/mlir/include/mlir/IR/Attributes.h --- a/mlir/include/mlir/IR/Attributes.h +++ b/mlir/include/mlir/IR/Attributes.h @@ -201,6 +201,19 @@ return LHS == RHS; } }; +template +struct DenseMapInfo< + T, std::enable_if_t::value>> + : public DenseMapInfo { + static T getEmptyKey() { + const void *pointer = llvm::DenseMapInfo::getEmptyKey(); + return T::getFromOpaquePointer(pointer); + } + static T getTombstoneKey() { + const void *pointer = llvm::DenseMapInfo::getTombstoneKey(); + return T::getFromOpaquePointer(pointer); + } +}; /// Allow LLVM to steal the low bits of Attributes. template <> struct PointerLikeTypeTraits { diff --git a/mlir/include/mlir/IR/BuiltinOps.h b/mlir/include/mlir/IR/BuiltinOps.h --- a/mlir/include/mlir/IR/BuiltinOps.h +++ b/mlir/include/mlir/IR/BuiltinOps.h @@ -49,23 +49,6 @@ } // end namespace mlir namespace llvm { -// Functions hash just like pointers. -template <> -struct DenseMapInfo { - static mlir::FuncOp getEmptyKey() { - auto *pointer = llvm::DenseMapInfo::getEmptyKey(); - return mlir::FuncOp::getFromOpaquePointer(pointer); - } - static mlir::FuncOp getTombstoneKey() { - auto *pointer = llvm::DenseMapInfo::getTombstoneKey(); - return mlir::FuncOp::getFromOpaquePointer(pointer); - } - static unsigned getHashValue(mlir::FuncOp val) { - return hash_value(val.getAsOpaquePointer()); - } - static bool isEqual(mlir::FuncOp lhs, mlir::FuncOp rhs) { return lhs == rhs; } -}; - /// Allow stealing the low bits of FuncOp. template <> struct PointerLikeTypeTraits { diff --git a/mlir/include/mlir/IR/OpDefinition.h b/mlir/include/mlir/IR/OpDefinition.h --- a/mlir/include/mlir/IR/OpDefinition.h +++ b/mlir/include/mlir/IR/OpDefinition.h @@ -1906,4 +1906,25 @@ } // namespace impl } // end namespace mlir +namespace llvm { + +template +struct DenseMapInfo< + T, std::enable_if_t::value>> { + static inline T getEmptyKey() { + auto *pointer = llvm::DenseMapInfo::getEmptyKey(); + return T::getFromOpaquePointer(pointer); + } + static inline T getTombstoneKey() { + auto *pointer = llvm::DenseMapInfo::getTombstoneKey(); + return T::getFromOpaquePointer(pointer); + } + static unsigned getHashValue(T val) { + return hash_value(val.getAsOpaquePointer()); + } + static bool isEqual(T lhs, T rhs) { return lhs == rhs; } +}; + +} // end namespace llvm + #endif diff --git a/mlir/include/mlir/IR/Types.h b/mlir/include/mlir/IR/Types.h --- a/mlir/include/mlir/IR/Types.h +++ b/mlir/include/mlir/IR/Types.h @@ -269,6 +269,18 @@ static unsigned getHashValue(mlir::Type val) { return mlir::hash_value(val); } static bool isEqual(mlir::Type LHS, mlir::Type RHS) { return LHS == RHS; } }; +template +struct DenseMapInfo::value>> + : public DenseMapInfo { + static T getEmptyKey() { + const void *pointer = llvm::DenseMapInfo::getEmptyKey(); + return T::getFromOpaquePointer(pointer); + } + static T getTombstoneKey() { + const void *pointer = llvm::DenseMapInfo::getTombstoneKey(); + return T::getFromOpaquePointer(pointer); + } +}; /// We align TypeStorage by 8, so allow LLVM to steal the low bits. template <> struct PointerLikeTypeTraits { diff --git a/mlir/include/mlir/Support/LLVM.h b/mlir/include/mlir/Support/LLVM.h --- a/mlir/include/mlir/Support/LLVM.h +++ b/mlir/include/mlir/Support/LLVM.h @@ -46,7 +46,7 @@ } // namespace detail template class DenseMap; -template struct DenseMapInfo; +template struct DenseMapInfo; template class DenseSet; class MallocAllocator; template class MutableArrayRef; @@ -90,7 +90,8 @@ // // Containers. using llvm::ArrayRef; -using llvm::DenseMapInfo; +template +using DenseMapInfo = llvm::DenseMapInfo; template , typename BucketT = llvm::detail::DenseMapPair>