[LLVMdev] What is getTombstoneKey? (original) (raw)

Benjamin Kramer benny.kra at gmail.com
Wed Jul 29 11:12:23 PDT 2015

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.

More information about the llvm-dev mailing list