ADT: Remove misaligned pointeres from DenseMapInfo

[majnemer]

Summary

C++ requires that pointers point to sufficiently well aligned addresses.
getEmptyKey() and getTombstoneKey() would cast -1 and -2 to arbitrary
pointer types which would violate this requirement.

In an ideal world, we would query the alignment of the pointee type;
however, the pointee type might be incomplete (this is often the case in
LLVM/Clang). Instead, assume that no type is more aligned than 16383
bytes.

[samsonov]

FTR, this is the last remaining major problem which keeps "check-llvm" command broken under UBSan bootstrap. This patch looks good to me, but I'm not sure if I can sign this off.

[hfinkel]

In D5428#104058, @samsonov wrote:

FTR, this is the last remaining major problem which keeps "check-llvm" command broken under UBSan bootstrap. This patch looks good to me, but I'm not sure if I can sign this off.

IIRC, the problem was that this is not actually undefined behavior. The resulting pointer value might be a "trap representation", but that's implementation-defined behavior, not undefined behavior. UBSan might need to be fixed here.

[samsonov]

In D5428#104174, @hfinkel wrote:

In D5428#104058, @samsonov wrote:

FTR, this is the last remaining major problem which keeps "check-llvm" command broken under UBSan bootstrap. This patch looks good to me, but I'm not sure if I can sign this off.

IIRC, the problem was that this is not actually undefined behavior. The resulting pointer value might be a "trap representation", but that's implementation-defined behavior, not undefined behavior. UBSan might need to be fixed here.

What fix do you suggest? UBSan prints an error report when the unaligned pointer T* is actually used, not when it's created. In LLVM, this "use" is usually an upcast to Value *. So, you may treat UBSan as the tool implementing this trapping behavior.

[chandlerc]

My memory is that this got fixed differently, but re-ping if needed.

include/llvm/ADT/DenseMapInfo.h

struct DenseMapInfo {
   //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*> {
   static inline T* getEmptyKey() {
-    uintptr_t Val = static_cast<uintptr_t>(-1);
-    Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
+    uintptr_t Val = static_cast<uintptr_t>(-1) - 0x3fff;
     return reinterpret_cast<T*>(Val);
   }
   static inline T* getTombstoneKey() {
-    uintptr_t Val = static_cast<uintptr_t>(-2);
-    Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
+    uintptr_t Val = static_cast<uintptr_t>(-1) - 0x7fff;
     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; }
 };