[ADT] Fix SmallDenseMap assertion with large InlineBuckets
authorNikita Popov <nikita.ppv@gmail.com>
Wed, 11 Dec 2019 20:17:29 +0000 (21:17 +0100)
committerNikita Popov <nikita.ppv@gmail.com>
Wed, 11 Dec 2019 20:41:14 +0000 (21:41 +0100)
commitfe593fe15f780517a703c4c108fc162028f180bb
treea90fc62232dfc72e36c1731913676accd35b069c
parentd23c61490c282a7a8f29aaa5c021cbfdaf87fb6f
[ADT] Fix SmallDenseMap assertion with large InlineBuckets

Fixes issue encountered in D56362, where I tried to use a
SmallSetVector<Instruction*, 128> with an excessively large number
of inline elements. This triggers an "Must allocate more buckets
than are inline" assertion inside allocateBuckets() under certain
usage patterns.

The issue is as follows: The grow() method is used either to grow
the map, or to rehash it and remove tombstones. The latter is done
if the fraction of empty (non-used, non-tombstone) elements is
below 1/8. In this case grow() is invoked with the current number
of buckets.

This is currently incorrectly handled for dense maps using the small
rep. The current implementation will switch them over to the large
rep, which violates the invariant that the large rep is only used
if there are more than InlineBuckets buckets.

This patch fixes the issue by staying in the small rep and only
moving the buckets. An alternative, if we do want to switch to the
large rep in this case, would be to relax the assertion in
allocateBuckets().

Differential Revision: https://reviews.llvm.org/D56455
llvm/include/llvm/ADT/DenseMap.h
llvm/unittests/ADT/DenseMapTest.cpp