DenseMapInfo::getHashValue() of two sometimes identical pointers

Hi all,

is there a recommended way to implement a 'DenseMapInfo<..>::getHashValue()'
for a class that contains multiple pointers of which some are potentially identical ?

The standard used xor (^) is canceling out the hash contribution of those identical pointers.

More concrete: I am adding a 'PtrProvenance' member to MemoryLocation. When I add
the member to the hash computation in the way it seems intended,

I would do:

  static unsigned getHashValue(const MemoryLocation &Val) {
      return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^
           DenseMapInfo<const Value *>::getHashValue(Val.PtrProvenance) ^ // Handle new member
           DenseMapInfo<LocationSize>::getHashValue(Val.Size) ^

But, in the initial case, it is very likely that Val.Ptr == Val.PtrProvenance.

Is there a recommended (standard) way to fix this ?


Jeroen Dobbelaere

straight up ^ isn’t a very good hash algorithm, as you’re seeing - my understanding was even a rudimentary hash algorithm multiplied the previous value by a prime before combining it

But I think we have a library in llvm for hashing that probably does something pretty good, whatever it is - llvm/ADT/Hashing.h - probably use that? (hash_combine(x, y, z), I guess?)

There’s also llvm/Support/xxhash.h if the other one falls short.