llvm dev - Sep 2021 - 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,

https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/Analysis/MemoryLocation.h#L340-L344

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) ^
           DenseMapInfo<AAMDNodes>::getHashValue(Val.AATags);
  }


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

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

Thanks,

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?)

On Thu, Sep 9, 2021 at 11:54 PM Jeroen Dobbelaere via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> 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,
>
>
>
https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/Analysis/MemoryLocation.h#L340-L344
>
> 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) ^
>            DenseMapInfo<AAMDNodes>::getHashValue(Val.AATags);
>   }
>
>
> But, in the initial case, it is very likely that Val.Ptr =>
Val.PtrProvenance.
>
> Is there a recommended (standard) way to fix this ?
>
> Thanks,
>
> Jeroen Dobbelaere
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210910/b3e5812b/attachment.html>