[DenseMapInfo] Add implementation for SmallVector of pointers.

[dexonsmith]

I'm concerned about propagating this pattern. DenseSet, like DenseMap, is tuned for small keys and values. SmallVector<void*,4> is not exactly small, at 48B. And this patch makes it easy to throw much larger SmallVectors into these containers.

I wonder, could these be replaced by TinyPtrVector? They're only 8B.

[fhahn]

In D52312#1240764, @dexonsmith wrote:

I'm concerned about propagating this pattern. DenseSet, like DenseMap, is tuned for small keys and values. SmallVector<void*,4> is not exactly small, at 48B. And this patch makes it easy to throw much larger SmallVectors into these containers.

Agreed, having this generally available makes it more likely to be misused unfortunately. If we end up going with SmallVector, we should definitely limit the number of elements.

I wonder, could these be replaced by TinyPtrVector? They're only 8B.

Interesting, I'll have a look. My only worry with this is that in the LSR and SLP use cases, it is very likely that the vector contains more than 1 element.

[dexonsmith]

In D52312#1241110, @fhahn wrote:

In D52312#1240764, @dexonsmith wrote:

I wonder, could these be replaced by TinyPtrVector? They're only 8B.

Interesting, I'll have a look. My only worry with this is that in the LSR and SLP use cases, it is very likely that the vector contains more than 1 element.

Sure, might be worth profiling compile time.

[fhahn]

Thanks for the comments. For now, I added a custom DenseMapInfo to D49491, but I hope I can revisit this once I have more time!

include/llvm/ADT/DenseMapInfo.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_DENSEMAPINFO_H
 #define LLVM_ADT_DENSEMAPINFO_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/PointerLikeTypeTraits.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <utility>
 
 namespace llvm {
 

 
 template <> struct DenseMapInfo<hash_code> {
   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; }
   static bool isEqual(hash_code LHS, hash_code RHS) { return LHS == RHS; }
 };
 
+template <class T, unsigned S> struct DenseMapInfo<SmallVector<T, S>> {
+    static SmallVector<T, S> getEmptyKey() {
+      return {reinterpret_cast<T>(-1)};
+    }
+
+    static SmallVector<T, S> getTombstoneKey() {
+      return {reinterpret_cast<T>(-2)};
+    }
+
+    static unsigned getHashValue(const SmallVector<T, S> &V) {
+      return static_cast<unsigned>(hash_combine_range(V.begin(), V.end()));
+    }
+
+    static bool isEqual(const SmallVector<T, S> &LHS,
+                        const SmallVector<T, S> &RHS) {
+      return LHS == RHS;
+    }
+  };
 } // end namespace llvm
 
 #endif // LLVM_ADT_DENSEMAPINFO_H

lib/Transforms/Scalar/LoopStrengthReduce.cpp

struct LSRFixup {
   LSRFixup() = default;
 
   bool isUseFullyOutsideLoop(const Loop *L) const;
 
   void print(raw_ostream &OS) const;
   void dump() const;
 };
 
-/// A DenseMapInfo implementation for holding DenseMaps and DenseSets of sorted
-/// SmallVectors of const SCEV*.
-struct UniquifierDenseMapInfo {
-  static SmallVector<const SCEV *, 4> getEmptyKey() {
-    SmallVector<const SCEV *, 4>  V;
-    V.push_back(reinterpret_cast<const SCEV *>(-1));
-    return V;
-  }
-
-  static SmallVector<const SCEV *, 4> getTombstoneKey() {
-    SmallVector<const SCEV *, 4> V;
-    V.push_back(reinterpret_cast<const SCEV *>(-2));
-    return V;
-  }
-
-  static unsigned getHashValue(const SmallVector<const SCEV *, 4> &V) {
-    return static_cast<unsigned>(hash_combine_range(V.begin(), V.end()));
-  }
-
-  static bool isEqual(const SmallVector<const SCEV *, 4> &LHS,
-                      const SmallVector<const SCEV *, 4> &RHS) {
-    return LHS == RHS;
-  }
-};
-
 /// This class holds the state that LSR keeps for each use in IVUsers, as well
 /// as uses invented by LSR itself. It includes information about what kinds of
 /// things can be folded into the user, information about the user itself, and
 /// information about how the use may be satisfied.  TODO: Represent multiple
 /// users of the same expression in common?
 class LSRUse {
-  DenseSet<SmallVector<const SCEV *, 4>, UniquifierDenseMapInfo> Uniquifier;
+  DenseSet<SmallVector<const SCEV *, 4>> Uniquifier;
 
 public:
   /// An enum for a kind of use, indicating what types of scaled and immediate
   /// operands it might support.
   enum KindType {
     Basic,   ///< A normal use, with no folding.
     Special, ///< A special case of basic, allowing -1 scales.
     Address, ///< An address use; folding according to TargetLowering
void LSRInstance::FilterOutUndesirableDedicatedRegisters() {
   SmallPtrSet<const SCEV *, 16> LoserRegs;
 #ifndef NDEBUG
   bool ChangedFormulae = false;
 #endif
 
   // Collect the best formula for each unique set of shared registers. This
   // is reset for each use.
   using BestFormulaeTy =
-      DenseMap<SmallVector<const SCEV *, 4>, size_t, UniquifierDenseMapInfo>;
+      DenseMap<SmallVector<const SCEV *, 4>, size_t>;
 
   BestFormulaeTy BestFormulae;
 
   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
     LSRUse &LU = Uses[LUIdx];
     LLVM_DEBUG(dbgs() << "Filtering for use "; LU.print(dbgs());
                dbgs() << '\n');