[SmallPtrSet] Don't leave tombstones in small mode (#96762)

When erasing elements in small mode, we currently leave behind
tombstones. This means that insertion into the SmallPtrSet also has to
check for these, making the operation more expensive than it really
should be.

We don't really need the tombstones in small mode, because we can just
replace with the last element in the set instead. This changes the
order, but SmallPtrSet order is fundamentally unstable anyway.

However, not leaving tombstones means that the erase() operation now
invalidates iterators. This means that consumers that want to remove
elements while iterating over the set have to use remove_if() instead.
If they fail to do so, there will be an assertion failure thanks to
debug epochs, so any such cases are easy to detect (and I have already
fixed all cases inside llvm at least).

1 files changed, 4 insertions, 2 deletions

diff --git a/llvm/docs/ProgrammersManual.rst b/llvm/docs/ProgrammersManual.rst
index f4a16c4..e00165c 100644
--- a/llvm/docs/ProgrammersManual.rst
+++ b/llvm/docs/ProgrammersManual.rst
@@ -2066,8 +2066,10 @@ insertion/deleting/queries with low constant factors) and is very stingy with
 malloc traffic.
 
 Note that, unlike :ref:`std::set <dss_set>`, the iterators of ``SmallPtrSet``
-are invalidated whenever an insertion occurs.  Also, the values visited by the
-iterators are not visited in sorted order.
+are invalidated whenever an insertion or erasure occurs. The ``remove_if``
+method can be used to remove elements while iterating over the set.
+
+Also, the values visited by the iterators are not visited in sorted order.
 
 .. _dss_stringset: