[LLVMdev] What is getTombstoneKey?

[Benjamin Kramer]

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