Fix -fsanitize=alignment reports on DenseMap empty/tombstone keys.

[samsonov]

Summary

Use large alignment when calculating empty/tombstone keys
for T*. We can't use alignof(T), as T may be forward-declared at
this point, and PointerLikeTypeTraits<T*>::NumLowBitsAvailable may
be too small.

[chandlerc]

I'm curious why we need to support forward declared types. It seems really
brittle. Have you looked into this much? If not, I can.

[majnemer]

I had a similar patch here: http://reviews.llvm.org/D5428

I went with a different approach to handle global objects which were massively over-aligned (unlikely, but possible).

include/llvm/ADT/DenseMapInfo.h

38–47

Would using std::max make this more readable?

[samsonov]

In D6768#103892, @chandlerc wrote:

I'm curious why we need to support forward declared types. It seems really
brittle. Have you looked into this much? If not, I can.

If your class has a member llvm::DenseMap<llvm::AllocaInst *, Foo>, it's a common practice to forward-declare llvm::AllocaInst.

In D6768#103896, @majnemer wrote:

I had a similar patch here: http://reviews.llvm.org/D5428

I went with a different approach to handle global objects which were massively over-aligned (unlikely, but possible).

Right, your patch looks slightly better. I'd be happy to see either of these commited :)

include/llvm/ADT/DenseMapInfo.h

38–47

This header is included by almost every LLVM source. I didn't want to #include <algorithm> here.

include/llvm/ADT/DenseMapInfo.h

struct DenseMapInfo {
   //static inline T getTombstoneKey();
   //static unsigned getHashValue(const T &Val);
   //static bool isEqual(const T &LHS, const T &RHS);
 };
 
 // Provide DenseMapInfo for all pointers.
 template<typename T>
 struct DenseMapInfo<T*> {
+  // Objects of types T may require large alignment, which we might not know (if
+  // T is forward-declared). Generate empty/tombstone keys to account for that.
+  enum { MaxAlignmentLog = 5 };
   static inline T* getEmptyKey() {
     uintptr_t Val = static_cast<uintptr_t>(-1);
-    Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
+    Val <<= PointerLikeTypeTraits<T *>::NumLowBitsAvailable < MaxAlignmentLog
+                ? MaxAlignmentLog
+                : PointerLikeTypeTraits<T *>::NumLowBitsAvailable;
     return reinterpret_cast<T*>(Val);
   }
   static inline T* getTombstoneKey() {
     uintptr_t Val = static_cast<uintptr_t>(-2);
-    Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
+    Val <<= PointerLikeTypeTraits<T *>::NumLowBitsAvailable < MaxAlignmentLog
+                ? MaxAlignmentLog
+                : PointerLikeTypeTraits<T *>::NumLowBitsAvailable;
     return reinterpret_cast<T*>(Val);
   }
   static unsigned getHashValue(const T *PtrVal) {
     return (unsigned((uintptr_t)PtrVal) >> 4) ^
            (unsigned((uintptr_t)PtrVal) >> 9);
   }
   static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
 };