[i386] Assertion failed: (Elements + Grow <= Nodes * Capacity && "Not enough room for elements"), function distribute, file llvm/lib/Support/IntervalMap.cpp, line 123.

[Quuxplusone]

Bugzilla Link	PR47359
Status	RESOLVED FIXED
Importance	P normal
Reported by	Dimitry Andric (dimitry@andric.com)
Reported on	2020-08-30 08:26:38 -0700
Last modified on	2021-05-11 18:50:14 -0700
Version	11.0
Hardware	PC All
CC	aprantl@apple.com, brad@comstyle.com, chris.jackson@sony.com, hans@chromium.org, htmldeveloper@gmail.com, jeremy.morse.llvm@gmail.com, llvm-bugs@lists.llvm.org, llvm-dev@redking.me.uk, teqdruid@gmail.com, vsk@apple.com
Fixed by commit(s)
Attachments	pr47359-full.tar.xz (901044 bytes, application/octet-stream)
Blocks	PR46725
Blocked by
See also

Building the FreeBSD x11-toolkits/py-wxPython40 port on a i386 host (i.e. 32-
bit x86, not x86_64) fails with an assertion [1]:

Assertion failed: (Elements + Grow <= Nodes * Capacity && "Not enough room for
elements"), function distribute, file /usr/src/contrib/llvm-
project/llvm/lib/Support/IntervalMap.cpp, line 123.
PLEASE submit a bug report to https://bugs.freebsd.org/submit/ and include the
crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: clang -cc1 -triple i386-unknown-freebsd13.0 -emit-
obj -disable-free -main-file-name sip_ribbonwxRibbonMSWArtProvider.cpp -
mrelocation-model pic -pic-level 2 -mframe-pointer=all -relaxed-aliasing -fno-
rounding-math -mconstructor-aliases -munwind-tables -target-cpu i686 -fno-split-
dwarf-inlining -debug-info-kind=standalone -dwarf-version=4 -debugger-
tuning=gdb -U NDEBUG -D SIP_MODULE_NAME=wx.siplib -D SIP_MODULE_BASENAME=siplib
-D PYTHONDIR="/usr/local/lib/python3.8/site-packages" -D
PYTHONARCHDIR="/usr/local/lib/python3.8/site-packages" -D HAVE_PYEXT=1 -D
HAVE_PYTHON_H=1 -D HAVE_WX=1 -D HAVE_WXADV=1 -D HAVE_WXSTC=1 -D HAVE_WXHTML=1 -
D HAVE_WXGL=1 -D HAVE_WXWEBVIEW=1 -D HAVE_WXXML=1 -D HAVE_WXXRC=1 -D
HAVE_WXRICHTEXT=1 -D HAVE_WXMEDIA=1 -D HAVE_WXRIBBON=1 -D HAVE_WXPROPGRID=1 -D
HAVE_WXAUI=1 -D _FILE_OFFSET_BITS=64 -D WXUSINGDLL -D __WXGTK__ -D _THREAD_SAFE
-O2 -fdeprecated-macro -ferror-limit 19 -pthread -stack-protector 2 -fgnuc-
version=4.2.1 -fcxx-exceptions -fexceptions -vectorize-loops -vectorize-slp -
faddrsig -x c++ sip_ribbonwxRibbonMSWArtProvider-c1d103.cpp
1.      <eof> parser at end of file
2.      Code generation
3.      Running pass 'Function Pass Manager' on module
'sip_ribbonwxRibbonMSWArtProvider-c1d103.cpp'.
4.      Running pass 'Live DEBUG_VALUE analysis' on function
'@_ZN22wxRibbonMSWArtProvideraSERKS_'

I have tried to reproduce this on one of my regular x86_64 hosts, but
unfortunately it *only* occurs with a 32-bit version of clang 11.0!

Minimized test case:

// clang -cc1 -triple i386-- -S -mframe-pointer=all -debug-info-kind=standalone
-O2 sip_ribbonwxRibbonMSWArtProvider-min.cpp
class g {
public:
  void operator=(g &h) {
    if (this != &h)
      i(h);
  }
  void i(g &);
};
struct j : g {};
struct k : j {};
struct l : g {};
struct aa : l {};
struct ad : g {};
struct J : ad {};
struct cw : g {};
struct cx : cw {};
struct cy : g {};
struct da : cy {};
struct m {
  J n;
  J o;
  J b;
  aa p;
  aa c;
  aa q;
  aa r;
  aa s;
  aa t;
  aa ab;
  aa u;
  aa v;
  aa w;
  aa x;
  aa y;
  aa z;
  aa e;
  aa ac;
  aa d;
  aa ae;
  aa af;
  aa ag;
  aa ah;
  aa ai;
  aa aj;
  aa ak;
  aa al;
  aa am;
  aa an;
  aa ao;
  aa ap;
  aa aq;
  aa ar;
  aa as;
  aa at;
  aa au;
  aa av;
  aa aw;
  aa a;
  aa ax;
  aa ay;
  aa az;
  aa ba;
  aa bb;
  aa bc;
  aa bd;
  aa be;
  aa bf;
  aa bg;
  aa bh;
  aa bi;
  aa bj;
  aa bk;
  aa bl;
  aa bm;
  aa bn;
  aa bo;
  aa bp;
  aa bq;
  aa br;
  aa bs;
  aa bt;
  aa bu;
  aa bv;
  aa bw;
  aa bx;
  aa by;
  da bz;
  da ca;
  da f;
  da cb;
  da cc;
  da cd;
  da ce;
  da cf;
  da cg;
  da ch;
  k ci;
  k cj;
  k ck;
  cx cl;
  cx cq;
  cx cm;
  cx cn;
  cx co;
  cx cp;
  cx cv;
  cx cr;
  cx cs;
  cx ct;
  cx cu;
  int cz;
} * a;
void db() { a[0] = *reinterpret_cast<m *>(0); }

It seems that something is going wrong in llvm::IntervalMapImpl::distribute(),
but I'm still digging around. The first thing I tried is a 32-bit build of
clang with -fsanitize=undefined, but it did not trigger on any undefined
behavior, unfortunately.

[1] (IPv6-only) http://beefy17.nyi.freebsd.org/data/head-i386-
default/p546309_s364850/logs/errors/py37-wxPython40-4.0.7_1.log

[Quuxplusone]

Some further notes about this bug.

It seems to have something to do with debug information. In the command line for the minimized test case:

clang -cc1 -triple i386-- -S -mframe-pointer=all -debug-info-kind=standalone -O2 sip_ribbonwxRibbonMSWArtProvider-min.cpp

both the -mframe-pointer=all and -debug-info-kind=standalone flags are required for the assertion to trigger.

Bisection shows that https://reviews.llvm.org/D79863 / https://github.com/llvm/llvm-project/commit/4707bc217780895207a9dc7467495a92eb0106a5 ("[DebugInfo] Refactor SalvageDebugInfo and SalvageDebugInfoForDbgValues") seems to be the first commit where the assertion is triggered, at least for the minimized test case.

However, I also have the full un-preprocessed test case, and that still triggers the assertion with commits before the above, so I am bisecting some more. Maybe we're overshooting some sort of internal limits...

[Quuxplusone]

More bisection on the original test case shows the assertion is being
introduced by https://reviews.llvm.org/D74986 /
https://reviews.llvm.org/rGa993720397ea ("[LiveDebugValues] Encode register
location within VarLoc IDs [3/3]").

This is part of a series of commits by Vedant Kumar to address (I think)
performance issues in LiveDebugValues:

https://reviews.llvm.org/D74984 ("[ADT] Add CoalescingBitVector, implemented
using IntervalMap [1/3]")
https://reviews.llvm.org/D74985 ("[LiveDebugValues] Encode a location in VarLoc
IDs, NFC [2/3]")
https://reviews.llvm.org/D74986 ("[LiveDebugValues] Encode register location
within VarLoc IDs [3/3]")

Apparently the last of these triggers some edge case in IntervalMap, which
maybe only happens on hosts where pointers (and/or longs) are 32 bits?

[Quuxplusone]

Attached pr47359-full.tar.xz (901044 bytes, application/octet-stream): tarball with original full testcase

[Quuxplusone]

I can also reproduce this on Linux, in this case Debian 11/i386. It gives a
nicer stack trace there, but unfortunately due to the limited address space it
is not possible to link clang with debug info:

Starting program: /home/dim/llvm/llvmorg-12-init-4674-g9e7e1b2d4b1-linux5-i686-
ninja-rel-1/bin/clang -cc1 -triple i386-- -S -mframe-pointer=all -debug-info-
kind=standalone -O2 sip_ribbonwxRibbonMSWArtProvider-min.cpp
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/i386-linux-gnu/libthread_db.so.1".
sip_ribbonwxRibbonMSWArtProvider-min.cpp:113:20: warning: binding dereferenced
null pointer to reference has undefined behavior [-Wnull-dereference]
void db() { a[0] = *reinterpret_cast<m *>(0); }
                   ^~~~~~~~~~~~~~~~~~~~~~~~~
clang: /home/dim/src/llvm/llvm-project/llvm/lib/Support/IntervalMap.cpp:123:
llvm::IntervalMapImpl::IdxPair llvm::IntervalMapImpl::distribute(unsigned int,
unsigned int, unsigned int, const unsigned int*, unsigned int*, unsigned int,
bool): Assertion `Elements + Grow <= Nodes * Capacity && "Not enough room for
elements"' failed.

Program received signal SIGABRT, Aborted.
0xb7fd41cd in __kernel_vsyscall ()
(gdb) bt
#0  0xb7fd41cd in __kernel_vsyscall ()
#1  0xb7ae0e32 in __libc_signal_restore_set (set=0xbfffba6c) at
../sysdeps/unix/sysv/linux/internal-signals.h:86
#2  __GI_raise (sig=6) at ../sysdeps/unix/sysv/linux/raise.c:48
#3  0xb7ac9306 in __GI_abort () at abort.c:79
#4  0xb7ac91d1 in __assert_fail_base (fmt=0xb7c3c080 "%s%s%s:%u: %s%sAssertion
`%s' failed.\n%n", assertion=0x5f069cc "Elements + Grow <= Nodes * Capacity &&
\"Not enough room for elements\"", file=0x5f06700 "/home/dim/src/llvm/llvm-
project/llvm/lib/Support/IntervalMap.cpp", line=123, function=0x5f06928
"llvm::IntervalMapImpl::IdxPair llvm::IntervalMapImpl::distribute(unsigned int,
unsigned int, unsigned int, const unsigned int*, unsigned int*, unsigned int,
bool)") at assert.c:92
#5  0xb7ad8d09 in __GI___assert_fail (assertion=0x5f069cc "Elements + Grow <=
Nodes * Capacity && \"Not enough room for elements\"", file=0x5f06700
"/home/dim/src/llvm/llvm-project/llvm/lib/Support/IntervalMap.cpp", line=123,
function=0x5f06928 "llvm::IntervalMapImpl::IdxPair
llvm::IntervalMapImpl::distribute(unsigned int, unsigned int, unsigned int,
const unsigned int*, unsigned int*, unsigned int, bool)") at assert.c:101
#6  0x022d28c9 in llvm::IntervalMapImpl::distribute(unsigned int, unsigned int,
unsigned int, unsigned int const*, unsigned int*, unsigned int, bool) ()
#7  0x0191cccf in llvm::IntervalMap<unsigned long long, char, 16u,
llvm::IntervalMapInfo<unsigned long long> >::splitRoot(unsigned int) ()
#8  0x0191f077 in llvm::IntervalMap<unsigned long long, char, 16u,
llvm::IntervalMapInfo<unsigned long long> >::iterator::insertNode(unsigned int,
llvm::IntervalMapImpl::NodeRef, unsigned long long) ()
#9  0x0191facf in llvm::IntervalMap<unsigned long long, char, 16u,
llvm::IntervalMapInfo<unsigned long long> >::iterator::treeInsert(unsigned long
long, unsigned long long, char) ()
#10 0x019222f5 in llvm::CoalescingBitVector<unsigned long long,
16u>::set(llvm::CoalescingBitVector<unsigned long long, 16u> const&) ()
#11 0x0192a647 in (anonymous
namespace)::VarLocBasedLDV::ExtendRanges(llvm::MachineFunction&,
llvm::TargetPassConfig*) [clone .part.0] ()
#12 0x0190b738 in LiveDebugValues::runOnMachineFunction(llvm::MachineFunction&)
()
#13 0x017252ef in llvm::MachineFunctionPass::runOnFunction(llvm::Function&) ()
#14 0x01c2053b in llvm::FPPassManager::runOnFunction(llvm::Function&) ()
#15 0x01c20f7e in llvm::FPPassManager::runOnModule(llvm::Module&) ()
#16 0x01c1f4b0 in llvm::legacy::PassManagerImpl::run(llvm::Module&) ()
#17 0x01c1f6cf in llvm::legacy::PassManager::run(llvm::Module&) ()
#18 0x02618979 in clang::EmitBackendOutput(clang::DiagnosticsEngine&,
clang::HeaderSearchOptions const&, clang::CodeGenOptions const&,
clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout
const&, llvm::Module*, clang::BackendAction,
std::unique_ptr<llvm::raw_pwrite_stream,
std::default_delete<llvm::raw_pwrite_stream> >) ()
#19 0x0339d82a in
clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) ()
#20 0x0405e549 in clang::ParseAST(clang::Sema&, bool, bool) ()
#21 0x02c7ca5a in clang::ASTFrontendAction::ExecuteAction() ()
#22 0x0339c2b9 in clang::CodeGenAction::ExecuteAction() ()
#23 0x02c85d69 in clang::FrontendAction::Execute() ()
#24 0x02c37e9d in
clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) ()
#25 0x02d4213c in clang::ExecuteCompilerInvocation(clang::CompilerInstance*) ()
#26 0x00aeeefc in cc1_main(llvm::ArrayRef<char const*>, char const*, void*) ()
#27 0x00aeb18a in ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) ()
#28 0x00a6da34 in main ()

I also tried a few other 32 bit triples, like arm--, mips-- and powerpc--, but
none of these seem to trigger the assertion.

[Quuxplusone]

Interestingly, applying the following diff "fixes" the assertion for me, as I
was assuming there was simply not enough room in the IntervalMap for
CoalescingBitVector?

diff --git a/llvm/include/llvm/ADT/CoalescingBitVector.h
b/llvm/include/llvm/ADT/CoalescingBitVector.h
index f8c8fec0ec9..16921c56705 100644
--- a/llvm/include/llvm/ADT/CoalescingBitVector.h
+++ b/llvm/include/llvm/ADT/CoalescingBitVector.h
@@ -35,7 +35,7 @@ namespace llvm {
 ///
 /// \tparam IndexT - The type of the index into the bitvector.
 /// \tparam N - The first N coalesced intervals of set bits are stored in-place.
-template <typename IndexT, unsigned N = 16> class CoalescingBitVector {
+template <typename IndexT, unsigned N = 32> class CoalescingBitVector {
   static_assert(std::is_unsigned<IndexT>::value,
                 "Index must be an unsigned integer.");

That said, this may only be applicable to i386, or only seem to work around the
actual root cause.

[Quuxplusone]

What also helps is to simply eliminate the N template parameter from
CoalescingBitVector, and let IntervalMap sort out the correct value (which it
does via N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize):

diff --git a/llvm/include/llvm/ADT/CoalescingBitVector.h
b/llvm/include/llvm/ADT/CoalescingBitVector.h
index f8c8fec0ec9..0a7dcfe2263 100644
--- a/llvm/include/llvm/ADT/CoalescingBitVector.h
+++ b/llvm/include/llvm/ADT/CoalescingBitVector.h
@@ -34,15 +34,14 @@ namespace llvm {
 /// performance for non-sequential find() operations.
 ///
 /// \tparam IndexT - The type of the index into the bitvector.
-/// \tparam N - The first N coalesced intervals of set bits are stored in-
place.
-template <typename IndexT, unsigned N = 16> class CoalescingBitVector {
+template <typename IndexT> class CoalescingBitVector {
   static_assert(std::is_unsigned<IndexT>::value,
                 "Index must be an unsigned integer.");

-  using ThisT = CoalescingBitVector<IndexT, N>;
+  using ThisT = CoalescingBitVector<IndexT>;

   /// An interval map for closed integer ranges. The mapped values are unused.
-  using MapT = IntervalMap<IndexT, char, N>;
+  using MapT = IntervalMap<IndexT, char>;

   using UnderlyingIterator = typename MapT::const_iterator;

I'm unsure why the N parameter was added to CoalescingBitVector anyway, since
it never seems to be used.

[Quuxplusone]

This has now been fixed via https://reviews.llvm.org/D87044 / https://reviews.llvm.org/rGf26fc568402f ("Eliminate the sizing template parameter N from CoalescingBitVector").

Hans, after this has baked for a little, can you please merge it into the 11.0 branch?

[Quuxplusone]

Pushed to 11.x as 919f9c291508217c697220b87a33406b9b685202. Thanks!

[Quuxplusone]

I got an assertion with the same signature recently. I don't think I'm using IntervalMap incorrectly. Here's the minimal testcase:

#include "llvm/ADT/IntervalMap.h"

int main(int argc, char **argv) {
  llvm::IntervalMap<uint64_t, void *, 16>::Allocator allocator;
  llvm::IntervalMap<uint64_t, void *, 16> segment(allocator);

  for (unsigned i = 0; i < 2000; i += 9)
    segment.insert(i, i + 7, nullptr);
  printf("Passed\n");
  return 0;
}

llvm/lib/Support/IntervalMap.cpp:123: llvm::IntervalMapImpl::IdxPair llvm::IntervalMapImpl::distribute(unsigned int, unsigned int, unsigned int, const unsigned int , unsigned int , unsigned int, bool): Assertion `Elements + Grow <= Nodes * Capacity && "Not enough room for elements"' failed. Aborted

If I remove the "16" template parameter, it doesn't assert. (So I have a mitigation.)

I'm building against a recent git commit: 39bbfb77264a4a7a216921c2b70a30ba0f27eb56 from Thu Apr 30 17:01:28 2020 -0400.