[llvm-dev] DenseMapInfo::getHashValue() of two sometimes identical pointers

[David Blaikie via llvm-dev]

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>