Make SmallPtrSet count and find able to take const PtrType's

[• dberlin]

Summary

For our set/map types, count/find normally take const references.
This works well for non-pointer types, but can suck for pointer
types.

DenseSet<int *> foo;
const int *b = nullptr;
foo.count(b) does not work

but the equivalent reference version does work
(patch to fix DenseSet/DenseMap coming up)
For SmallPtrSet, you have no such option.

The following will not work right now:
SmallPtrSet<int *> foo;
const int *b = nullptr;
foo.count(b);

This makes const correctness hard in some cases.
Example:
SmallPtrSet<Instruction *> InstructionsToErase;

You can't make this SmallPtrSet<const Instruction *> because then you
can't erase the instruction. If I want to see if something is in the
set, I may only have a const Instruction *. Given that count and find
are non-mutating, this should just work.

The places in our code base that do this resort to const_cast :(.

This patch makes count and find able to be used with const Instruction

• in the above SmallPtrSet examples.

This is a bit annoying because of where C++ applies the const, so we
have to remove the pointer type from the passed-in-type and rebuild it
with const.

[• dberlin]

• What do you mean we've already got one?

[• dberlin]

• Add PointerLikeTypeTraits for const things, as long as there is one for the non-const version.

Clang and other users have a number of types they use as pointers and
put in SmallPtrSet, and this avoids having to define both const and
non-const versions of PointerLikeTraits for about 5 types.

(Note: You can't easily merge the const T and const T * versions of
these that i can see).

[dblaikie]

Looks reasonable - Needs a unit test or two, though.

include/llvm/ADT/SmallPtrSet.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_SMALLPTRSET_H
 #define LLVM_ADT_SMALLPTRSET_H
 
 #include "llvm/Config/abi-breaking.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/PointerLikeTypeTraits.h"
+#include "llvm/Support/type_traits.h"
 #include <cassert>
 #include <cstddef>
 #include <cstring>
 #include <cstdlib>
 #include <initializer_list>
 #include <iterator>
 #include <utility>
 

 
 /// \brief A templated base class for \c SmallPtrSet which provides the
 /// typesafe interface that is common across all small sizes.
 ///
 /// This is particularly useful for passing around between interface boundaries
 /// to avoid encoding a particular small size in the interface boundary.
 template <typename PtrType>
 class SmallPtrSetImpl : public SmallPtrSetImplBase {
+  using ConstPtrType = typename add_const_past_pointer<PtrType>::type;
   typedef PointerLikeTypeTraits<PtrType> PtrTraits;
+  typedef PointerLikeTypeTraits<ConstPtrType> ConstPtrTraits;
 
 protected:
   // Constructors that forward to the base.
   SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl &that)
       : SmallPtrSetImplBase(SmallStorage, that) {}
   SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize,
                   SmallPtrSetImpl &&that)
       : SmallPtrSetImplBase(SmallStorage, SmallSize, std::move(that)) {}
std::pair<iterator, bool> insert(PtrType Ptr) {
     return std::make_pair(iterator(p.first, EndPointer()), p.second);
   }
 
   /// erase - If the set contains the specified pointer, remove it and return
   /// true, otherwise return false.
   bool erase(PtrType Ptr) {
     return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
   }
-
   /// count - Return 1 if the specified pointer is in the set, 0 otherwise.
-  size_type count(PtrType Ptr) const {
+  size_type count(ConstPtrType Ptr) const {
     return find(Ptr) != endPtr() ? 1 : 0;
   }
-  iterator find(PtrType Ptr) const {
-    auto *P = find_imp(PtrTraits::getAsVoidPointer(Ptr));
+  iterator find(ConstPtrType Ptr) const {
+    auto *P = find_imp(ConstPtrTraits::getAsVoidPointer(Ptr));
     return iterator(P, EndPointer());
   }
 
   template <typename IterT>
   void insert(IterT I, IterT E) {
     for (; I != E; ++I)
       insert(*I);
   }

include/llvm/Support/PointerLikeTypeTraits.h

public:
   /// wrong, or pointers may be from something other than malloc. In this case,
   /// you should specify a real typed pointer or avoid this template.
   ///
   /// All clients should use assertions to do a run-time check to ensure that
   /// this is actually true.
   enum { NumLowBitsAvailable = 2 };
 };
 
+// Provide PointerLikeTypeTraits for const things.
+template <typename T> class PointerLikeTypeTraits<const T> {
+  typedef PointerLikeTypeTraits<T> NonConst;
+
+public:
+  static inline const void *getAsVoidPointer(const T P) {
+    return NonConst::getAsVoidPointer(P);
+  }
+  static inline const T getFromVoidPointer(const void *P) {
+    return NonConst::getFromVoidPointer(const_cast<void *>(P));
+  }
+  enum { NumLowBitsAvailable = NonConst::NumLowBitsAvailable };
+};
+
 // Provide PointerLikeTypeTraits for const pointers.
 template <typename T> class PointerLikeTypeTraits<const T *> {
   typedef PointerLikeTypeTraits<T *> NonConst;
 
 public:
   static inline const void *getAsVoidPointer(const T *P) {
     return NonConst::getAsVoidPointer(const_cast<T *>(P));
   }