diff --git a/clang-tools-extra/include-cleaner/include/clang-include-cleaner/Types.h b/clang-tools-extra/include-cleaner/include/clang-include-cleaner/Types.h
--- a/clang-tools-extra/include-cleaner/include/clang-include-cleaner/Types.h
+++ b/clang-tools-extra/include-cleaner/include/clang-include-cleaner/Types.h
@@ -64,9 +64,11 @@
   struct Macro macro() const { return std::get<Macro>(Storage); }
 
 private:
-  // FIXME: Add support for macros.
   // Order must match Kind enum!
   std::variant<const Decl *, struct Macro> Storage;
+
+  Symbol(decltype(Storage) Sentinel) : Storage(std::move(Sentinel)) {}
+  friend llvm::DenseMapInfo<Symbol>;
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Symbol &);
 
@@ -137,4 +139,36 @@
 } // namespace include_cleaner
 } // namespace clang
 
+namespace llvm {
+
+template <> struct DenseMapInfo<clang::include_cleaner::Symbol> {
+  using Outer = clang::include_cleaner::Symbol;
+  using Base = DenseMapInfo<decltype(Outer::Storage)>;
+
+  static inline Outer getEmptyKey() { return {Base::getEmptyKey()}; }
+  static inline Outer getTombstoneKey() { return {Base::getTombstoneKey()}; }
+  static unsigned getHashValue(const Outer &Val) {
+    return Base::getHashValue(Val.Storage);
+  }
+  static bool isEqual(const Outer &LHS, const Outer &RHS) {
+    return Base::isEqual(LHS.Storage, RHS.Storage);
+  }
+};
+template <> struct DenseMapInfo<clang::include_cleaner::Macro> {
+  using Outer = clang::include_cleaner::Macro;
+  using Base = DenseMapInfo<decltype(Outer::Definition)>;
+
+  static inline Outer getEmptyKey() { return {nullptr, Base::getEmptyKey()}; }
+  static inline Outer getTombstoneKey() {
+    return {nullptr, Base::getTombstoneKey()};
+  }
+  static unsigned getHashValue(const Outer &Val) {
+    return Base::getHashValue(Val.Definition);
+  }
+  static bool isEqual(const Outer &LHS, const Outer &RHS) {
+    return Base::isEqual(LHS.Definition, RHS.Definition);
+  }
+};
+} // namespace llvm
+
 #endif