[LLVMdev] What is getTombstoneKey?

[Lawrence]

Thanks a lot, Benjamin.

Regards

Lawrence Hu

-----Original Message-----
From: Benjamin Kramer [mailto:benny.kra at gmail.com] 
Sent: Wednesday, July 29, 2015 11:12 AM
To: Lawrence
Cc: llvmdev at cs.uiuc.edu
Subject: Re: [LLVMdev] What is getTombstoneKey?

On Wed, Jul 29, 2015 at 7:51 PM, Lawrence <lawrence at codeaurora.org> wrote:
> Hi, All:
>
>
>
> I am trying to extend EarlyCSE.cpp to do more commoning of GEP 
> instruction, it requires a hashtable with two keys, I defined
>
>
>
> typedef ScopedHashTable<DoubleKey, std::pair<Value *, unsigned>,
>
>                           DenseMapInfo<Value *>, LoadMapAllocator> 
> LoadHTType;
>
>
>
> I declared a DoubleKey struct similar to CallValue but with two Value 
> * member,  However I have problem to implement getTombstoneKey() 
> because I don’t know what it is, could anyone tell me what it is about?

The tombstone is simply a key value that
  1. cannot occur as a key in the map (inserting EmptyKey or TombstoneKey will trigger an assertion)
  2. does not compare equal to any other value

We usually use something like ~0 for the empty key and ~1 for tombstones. See DenseMapInfo.h for some examples.

For the data structure background:
DenseMap is a quadratically probed hash map so when a collision occurs it will pick another slot in the table. If we would delete the first colliding item and simply empty out the slot it would become impossible to find any other colliding item. That's why DenseMap writes a special tombstone value into the slot on deletion which when performing a lookup will advance to the next slot for this hash value.

- Ben