#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

#200634)

#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

…00956)

#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

llvm#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

…vm#200956)

llvm#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

llvm#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

llvm#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

llvm#200595 changed DenseMap to no longer create tombstone buckets, so
DenseMapInfo<T>::getTombstoneKey() is never called. Remove dead
definitions and dead tombstone branches.

… for CTT)

Squash of the landed SmallPtrSet/DenseMap optimization series plus the
IR/Analysis getTombstoneKey/getEmptyKey cleanups, on top of the pre-SmallPtrSet
baseline (parent of llvm#197637), so the compile-time tracker measures the whole
series' cumulative impact as one from->to.

The ADT DenseMapInfo getEmptyKey/getTombstoneKey definitions are intentionally
kept: the primitive/generic specializations have direct callers tree-wide
(e.g. CodeView TypeIndex.h, TableGen), so their removal needs the whole-tree
caller cleanup that is out of scope here.

Includes:
  llvm#197637 [SmallPtrSet] Drop tombstones in large mode
  llvm#198982 Don't assume non-erased DenseMap entries remain valid after erase
  llvm#199369 [DenseMap] Invalidate iterators on erase
  llvm#200540 [IR] Fix PoisoningVH relocation of a poisoned handle
  llvm#200595 [DenseMap] Replace tombstone deletion with TAOCP 6.4 Algorithm R
  llvm#200958 [IR][Analysis] Remove unused DenseMapInfo::getTombstoneKey
  llvm#201281 [DenseMap] Store occupancy in a packed used-bit array
  llvm#201742 [DenseMap] Fix ubsan error after llvm#201281
  llvm#201997 [IR][Analysis] Remove unused DenseMapInfo::getEmptyKey

Not for merge; measurement aid only.

…201755)

DenseMap no longer use in-band sentinel keys. (#200595 and #201281).
Update the GDB pretty printer and LLDB data formatters to test the used
bit rather than comparing keys.

GDB: advancePastEmptyBuckets relied on DenseMapInfo::getEmptyKey(),
which could not be evaluated in GDB and so was disabled, leaving the printer
to emit empty and erased buckets. It now walks bucket indices and skips any
whose used bit is clear.

LLDB: DenseMapSynthetic used a key-uniqueness heuristic to guess which
buckets were live, which mishandled a lone erased bucket (hence the
former tombstones=1 summary note). It now reads the used array directly,
so erased entries are skipped exactly. NumTombstones no longer exists,
so drop it from the summary.

Written by Claude Opus 4.8

---------

Co-authored-by: Dave Lee <[email protected]>

…4 Algorithm R (#202231)

sanitizer_dense_map.h is a fork of llvm/ADT/DenseMap.h, which uses
quadratic probing with lazy deletion: an erased entry becomes a
tombstone, a third bucket state alongside empty and live that every
find/insert must inspect.

Port the upstream #200595 and getTombstoneKey() removal.

Aided by Claude Opus 4.8