Jeroen Dobbelaere via llvm-dev
2021-Sep-10 06:54 UTC
[llvm-dev] 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
David Blaikie via llvm-dev
2021-Sep-10 07:27 UTC
[llvm-dev] DenseMapInfo::getHashValue() of two sometimes identical pointers
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>