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

[Alexandre Ganea via llvm-dev]

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

De : llvm-dev <llvm-dev-bounces at lists.llvm.org> De la part de David Blaikie via llvm-dev
Envoyé : September 10, 2021 3:28 AM
À : Jeroen Dobbelaere <Jeroen.Dobbelaere at synopsys.com>
Cc : llvm-dev at lists.llvm.org
Objet : Re: [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<mailto: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<https://can01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fllvm%2Fllvm-project%2Fblob%2Fmain%2Fllvm%2Finclude%2Fllvm%2FAnalysis%2FMemoryLocation.h%23L340-L344&data=04%7C01%7Calexandre.ganea%40ubisoft.com%7Cdf96dd5e086d45c8e7d708d9742c8365%7Ce01bd386fa514210a2a429e5ab6f7ab1%7C0%7C0%7C637668556806959902%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=mPYakZcvSfRQy9ikkdJXev04gORdd1obhlpJGnG4d9E%3D&reserved=0>

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<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<https://can01.safelinks.protection.outlook.com/?url=https%3A%2F%2Flists.llvm.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fllvm-dev&data=04%7C01%7Calexandre.ganea%40ubisoft.com%7Cdf96dd5e086d45c8e7d708d9742c8365%7Ce01bd386fa514210a2a429e5ab6f7ab1%7C0%7C0%7C637668556806959902%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=yT0s9nCIFCLOjrMxwElDfXQ0FUMb0RUDEDXMLkz8GLw%3D&reserved=0>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210910/2f3c0736/attachment.html>