[llvm] Split out DenseMapInfo<variant> specialization

[IncludeGuardian]

Summary

Remove the DenseMapInfo<std::variant<Ts...>> variant out from
llvm/ADT/DenseMapInfo.h into a separate header
llvm/ADT/DenseMapInfoVariant.h

This allows us to remove the <variant> include, which is being
transitively and unncessary included in all translation units that
include llvm/ADT/DenseMap.h.

There have been similar changes to move out specializations for

• APInt.h fd7e309e02fd226b0390888388ed732608e52c73 and
• StringRef.h/ArrayRef.h 983565a6fe4a9f40c7caf82b65c650c20dbcc104

to reduce the compilation time. As we are unable to move the
specialization into <variant>, we create a separate
DenseMapInfoVariant.h header that can be used by anyone who needs this
specialization.

This reduces the total number of preprocessing tokens across the LLVM
source files in lib from (roughly) 1,964,876,961 to 1,936,551,496 - a
reduction of ~1.44%. This should result in a small improvement in
compilation time.

[IncludeGuardian]

I couldn't actually find a user of this specialization in llvm or clang. If the CI doesn't pick up any user then perhaps we would want to remove this specialization completely?

The implementation of isEqual is incorrect as it doesn't defer to other isEqual specializations, instead relying on operator==. If this component is needed then I can follow up with a fix + tests.

[IncludeGuardian]

The runs of IncludeGuardian for before and after this change.

This was suggested in the analysis before on this line. Suggesting a reduction in 1.42% preprocessing token count across all translation units in llvm/lib and we ended up getting 1.44%. It's a bit higher because not only was the include directive removed, but we removed the specialization itself from the header.

[nikic]

It looks like you forgot to git add the new file maybe?

This was added in https://reviews.llvm.org/D133200, maybe @kadircet can comment on what this was intended for.

[IncludeGuardian]

Fix one missing <variant> include in tools and add DenseMapInfoVariant.h, which I forgot previously

[IncludeGuardian]

llvm/include/llvm/ADT/DenseMapInfo.h

321–336

Regardless of this change, I think the equality here needs to be fixed in the future to delegate to DenseMapInfo for checking equality of the contents of the std::variant

[nikic]

The pre-merge checks have a build failure in clang-tools-extra.

[IncludeGuardian]

Add missing specialization for clang-include-cleaner/Types.h

[lattner]

Awesome, this makes a lot of sense and is a great pattern to make these more modular.

[IncludeGuardian]

flang/include/flang/Optimizer/HLFIR/HLFIROps.h

22

I wasn't sure if it is possible to include <vector> within HLFIROps.td so it has been included here instead.

[barannikov88]

flang/include/flang/Optimizer/HLFIR/HLFIROps.h

22

That's fine, we do that everywhere :)

[kadircet]

In D150997#4357589, @nikic wrote:

It looks like you forgot to git add the new file maybe?

This was added in https://reviews.llvm.org/D133200, maybe @kadircet can comment on what this was intended for.

It was already pointed out by you :) this is used by clang-tools-extra/include-cleaner/include/clang-include-cleaner/Types.h, and your changes there LG.
You should also update llvm/unittests/ADT/DenseMapTest.cpp, you can see build breakage information at the top (search for pre-merge checks).

Also, thanks for pointing out the discrepancy in implementation of isEqual. Sent out https://reviews.llvm.org/D151079. Happy to land it before or after your change.

[kadircet]

This comment was removed by kadircet.

[IncludeGuardian]

@kadircet Thanks I will run this through the formatter.

Thanks for fixing isEqual. I am currently on holiday for a few weeks so cannot guarantee when I'll be able to update this PR. I say go ahead with your fix and I'll incorporate those changes into this review when I am back.

[nikic]

(Moving this off the review queue per above comments. There is a missing include in a unit test.)

[IncludeGuardian]

Fix missing includes in test, fix formatting, and rebase on top of https://reviews.llvm.org/D151557

[IncludeGuardian]

Run clang-format over patch

[IncludeGuardian]

This is good to review now. Phabricator has become a bit confused after rebasing on top of https://reviews.llvm.org/D151557, I don't know whether it's worth creating a new, cleaner review and close this on?

[nikic]

LGTM. The diff looks weird for some reason, but the downloadable .diff file looks fine.

clang-tools-extra/include-cleaner/include/clang-include-cleaner/Types.h

 
 #ifndef CLANG_INCLUDE_CLEANER_TYPES_H
 #define CLANG_INCLUDE_CLEANER_TYPES_H
 
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseMapInfoVariant.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include <memory>
 #include <utility>
+#include <variant>
 #include <vector>
 
 namespace llvm {
 class raw_ostream;
 } // namespace llvm
 namespace clang {
 class Decl;
 class FileEntry;

flang/include/flang/Optimizer/HLFIR/HLFIROps.h

 #include "flang/Optimizer/Dialect/FIROps.h"
 #include "flang/Optimizer/Dialect/FIRType.h"
 #include "flang/Optimizer/Dialect/FortranVariableInterface.h"
 #include "flang/Optimizer/HLFIR/HLFIRDialect.h"
 #include "mlir/Dialect/Arith/IR/Arith.h"
 #include "mlir/IR/PatternMatch.h"
 #include "mlir/Interfaces/InferTypeOpInterface.h"
 #include "mlir/Interfaces/SideEffectInterfaces.h"
+#include <variant>
 
 #include "flang/Optimizer/HLFIR/HLFIROpInterfaces.h.inc"
 #define GET_OP_CLASSES
 #include "flang/Optimizer/HLFIR/HLFIROps.h.inc"
 
 #endif // FORTRAN_OPTIMIZER_HLFIR_HLFIROPS_H

llvm/include/llvm/ADT/DenseMapInfo.h

 #define LLVM_ADT_DENSEMAPINFO_H
 
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <tuple>
 #include <type_traits>
 #include <utility>
-#include <variant>
 
 namespace llvm {
 
 namespace detail {
 
 /// Simplistic combination of 32-bit hash values into 32-bit hash values.
 static inline unsigned combineHashValue(unsigned a, unsigned b) {
   uint64_t key = (uint64_t)a << 32 | (uint64_t)b;
return std::make_pair(FirstInfo::getTombstoneKey(),
                           SecondInfo::getTombstoneKey());
   }
 
   static unsigned getHashValue(const Pair& PairVal) {
     return detail::combineHashValue(FirstInfo::getHashValue(PairVal.first),
                                     SecondInfo::getHashValue(PairVal.second));
   }
 
+  // Expose an additional function intended to be used by other
+  // specializations of DenseMapInfo without needing to know how
+  // to combine hash values manually
+  static unsigned getHashValuePiecewise(const T &First, const U &Second) {
+    return detail::combineHashValue(FirstInfo::getHashValue(First),
+                                    SecondInfo::getHashValue(Second));
+  }
+
   static bool isEqual(const Pair &LHS, const Pair &RHS) {
     return FirstInfo::isEqual(LHS.first, RHS.first) &&
            SecondInfo::isEqual(LHS.second, RHS.second);
   }
 };
 
 // Provide DenseMapInfo for all tuples whose members have info.
 template <typename... Ts> struct DenseMapInfo<std::tuple<Ts...>> {
template <typename... Ts> struct DenseMapInfo<std::tuple<Ts...>> {
   }
 
   static bool isEqual(const Tuple &lhs, const Tuple &rhs) {
     std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd;
     return isEqualImpl<0>(lhs, rhs, atEnd);
   }
 };
 
-// Provide DenseMapInfo for variants whose all alternatives have DenseMapInfo.
-template <typename... Ts> struct DenseMapInfo<std::variant<Ts...>> {
-  using Variant = std::variant<Ts...>;
-  using FirstT = std::variant_alternative_t<0, Variant>;
-
-  static inline Variant getEmptyKey() {
-    return Variant(std::in_place_index<0>, DenseMapInfo<FirstT>::getEmptyKey());
-  }
-
-  static inline Variant getTombstoneKey() {
-    return Variant(std::in_place_index<0>,
-                   DenseMapInfo<FirstT>::getTombstoneKey());
-  }
-
-  static unsigned getHashValue(const Variant &Val) {
-    return std::visit(
-        [&Val](auto &&Alternative) {
-          using T = std::decay_t<decltype(Alternative)>;
-          // Include index in hash to make sure same value as different
-          // alternatives don't collide.
-          return detail::combineHashValue(
-              DenseMapInfo<size_t>::getHashValue(Val.index()),
-              DenseMapInfo<T>::getHashValue(Alternative));
-        },
-        Val);
-  }
-
-  static bool isEqual(const Variant &LHS, const Variant &RHS) {
-    if (LHS.index() != RHS.index())
-      return false;
-    if (LHS.valueless_by_exception())
-      return true;
-    // We want to dispatch to DenseMapInfo<T>::isEqual(LHS.get(I), RHS.get(I))
-    // We know the types are the same, but std::visit(V, LHS, RHS) doesn't.
-    // We erase the type held in LHS to void*, and dispatch over RHS.
-    const void *ErasedLHS =
-        std::visit([](const auto &LHS) -> const void * { return &LHS; }, LHS);
-    return std::visit(
-        [&](const auto &RHS) -> bool {
-          using T = std::remove_cv_t<std::remove_reference_t<decltype(RHS)>>;
-          return DenseMapInfo<T>::isEqual(*static_cast<const T *>(ErasedLHS),
-                                          RHS);
-        },
-        RHS);
-  }
-};
 } // end namespace llvm
 
 #endif // LLVM_ADT_DENSEMAPINFO_H

llvm/include/llvm/ADT/DenseMapInfoVariant.h

+//===- DenseMapInfoVariant.h - Type traits for DenseMap<variant> *- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This file defines DenseMapInfo traits for DenseMap<std::variant<Ts...>>.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_DENSEMAPINFOVARIANT_H
+#define LLVM_ADT_DENSEMAPINFOVARIANT_H
+
+#include "llvm/ADT/DenseMapInfo.h"
+#include <utility>
+#include <variant>
+
+namespace llvm {
+
+// Provide DenseMapInfo for variants whose all alternatives have DenseMapInfo.
+template <typename... Ts> struct DenseMapInfo<std::variant<Ts...>> {
+  using Variant = std::variant<Ts...>;
+  using FirstT = std::variant_alternative_t<0, Variant>;
+
+  static inline Variant getEmptyKey() {
+    return Variant(std::in_place_index<0>, DenseMapInfo<FirstT>::getEmptyKey());
+  }
+
+  static inline Variant getTombstoneKey() {
+    return Variant(std::in_place_index<0>,
+                   DenseMapInfo<FirstT>::getTombstoneKey());
+  }
+
+  static unsigned getHashValue(const Variant &Val) {
+    return std::visit(
+        [&Val](auto &&Alternative) {
+          using T = std::decay_t<decltype(Alternative)>;
+          // Include index in hash to make sure same value as different
+          // alternatives don't collide.
+          return DenseMapInfo<std::pair<size_t, T>>::getHashValuePiecewise(
+              Val.index(), Alternative);
+        },
+        Val);
+  }
+
+  static bool isEqual(const Variant &LHS, const Variant &RHS) {
+    if (LHS.index() != RHS.index())
+      return false;
+    if (LHS.valueless_by_exception())
+      return true;
+    // We want to dispatch to DenseMapInfo<T>::isEqual(LHS.get(I), RHS.get(I))
+    // We know the types are the same, but std::visit(V, LHS, RHS) doesn't.
+    // We erase the type held in LHS to void*, and dispatch over RHS.
+    const void *ErasedLHS =
+        std::visit([](const auto &LHS) -> const void * { return &LHS; }, LHS);
+    return std::visit(
+        [&](const auto &RHS) -> bool {
+          using T = std::remove_cv_t<std::remove_reference_t<decltype(RHS)>>;
+          return DenseMapInfo<T>::isEqual(*static_cast<const T *>(ErasedLHS),
+                                          RHS);
+        },
+        RHS);
+  }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_DENSEMAPINFOVARIANT_H

llvm/include/llvm/CodeGen/CallingConvLower.h

 #ifndef LLVM_CODEGEN_CALLINGCONVLOWER_H
 #define LLVM_CODEGEN_CALLINGCONVLOWER_H
 
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/CodeGen/Register.h"
 #include "llvm/CodeGen/TargetCallingConv.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/Support/Alignment.h"
+#include <variant>
+#include <vector>
 
 namespace llvm {
 
 class CCState;
 class MachineFunction;
 class MVT;
 class TargetRegisterInfo;
 

llvm/include/llvm/ExecutionEngine/Orc/LLJIT.h

 #include "llvm/ExecutionEngine/Orc/CompileUtils.h"
 #include "llvm/ExecutionEngine/Orc/ExecutionUtils.h"
 #include "llvm/ExecutionEngine/Orc/IRCompileLayer.h"
 #include "llvm/ExecutionEngine/Orc/IRTransformLayer.h"
 #include "llvm/ExecutionEngine/Orc/JITTargetMachineBuilder.h"
 #include "llvm/ExecutionEngine/Orc/ThreadSafeModule.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ThreadPool.h"
+#include <variant>
 
 namespace llvm {
 namespace orc {
 
 class LLJITBuilderState;
 class LLLazyJITBuilderState;
 class ObjectTransformLayer;
 class ExecutorProcessControl;

llvm/include/llvm/Object/DXContainer.h

 #define LLVM_OBJECT_DXCONTAINER_H
 
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/BinaryFormat/DXContainer.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/MemoryBufferRef.h"
 #include "llvm/TargetParser/Triple.h"
+#include <variant>
 
 namespace llvm {
 namespace object {
 
 namespace DirectX {
 class PSVRuntimeInfo {
 
   // This class provides a view into the underlying resource array. The Resource

llvm/include/llvm/Transforms/Scalar/SROA.h

 #define LLVM_TRANSFORMS_SCALAR_SROA_H
 
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/ValueHandle.h"
+#include <variant>
 #include <vector>
 
 namespace llvm {
 
 class AllocaInst;
 class LoadInst;
 class StoreInst;
 class AssumptionCache;

llvm/unittests/ADT/DenseMapTest.cpp

 //===- llvm/unittest/ADT/DenseMapMap.cpp - DenseMap unit tests --*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/DenseMapInfoVariant.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <map>
 #include <set>
 #include <utility>
 #include <variant>
 
 using namespace llvm;

mlir/include/mlir/IR/AsmState.h

 #define MLIR_IR_ASMSTATE_H_
 
 #include "mlir/IR/OperationSupport.h"
 #include "mlir/Support/LLVM.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/StringMap.h"
 
 #include <memory>
+#include <variant>
 
 namespace mlir {
 class AsmResourcePrinter;
 class AsmDialectResourceHandle;
 class Operation;
 
 namespace detail {
 class AsmStateImpl;

mlir/include/mlir/Transforms/SROA.h

 //===-- SROA.h - Scalar Replacement Of Aggregates ---------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_TRANSFORMS_SROA_H
 #define MLIR_TRANSFORMS_SROA_H
 
 #include "mlir/IR/PatternMatch.h"
 #include "mlir/Interfaces/MemorySlotInterfaces.h"
 #include "mlir/Support/LogicalResult.h"
 #include "llvm/ADT/Statistic.h"
+#include <variant>
 
 namespace mlir {
 
 /// Statistics collected while applying SROA.
 struct SROAStatistics {
   /// Total amount of memory slots destructured.
   llvm::Statistic *destructuredAmount = nullptr;
   /// Total amount of memory slots in which the destructured size was smaller