[SmallVector] Optimize move assignment operator for N==0 case

[MaskRay]

Summary

Due to the SmallVector hierarchy, N==0 cannot be leveraged by functions defined
in base classes. This patch special cases N==0 for SmallVector to save code size
and be slightly more efficient.

In a Release build of x86 only clang, .text is -3.34KiB smaller. In lld .text is
7.17KiB smaller.

[lichray]

llvm/include/llvm/ADT/SmallVector.h

1220

Does the idea apply to the assignment operator?

1245

This duplicates some code in SmallVectorImpl<T>::operator=, form a smaller function?

[dexonsmith]

llvm/include/llvm/ADT/SmallVector.h

1252–1253

Seems like inverting the condition with an early return would make this easier to read:

if (N) {
  SmallVectorImpl<T>::operator=(std::move(RHS));
  return *this;
}
// rest of function without nesting.

[MaskRay]

Switch to early return.

@lichray It is unclear how to deduplicate if (!this->isSmall()) free(this->begin()); this->BeginX = ...; this->Size = ..., this portion of code moves this->destroy_range(...) before if (RHS.empty()).

[lichray]

llvm/include/llvm/ADT/SmallVector.h

1044–1046

1244–1255

where assignRemote is your current code. Does that work?

[MaskRay]

llvm/include/llvm/ADT/SmallVector.h

1244–1255

In the generated code, this->destroy_range(this->begin(), this->end()); will be called twice, while the current version calls this function just once...

[MaskRay]

Add assignRemote and use it

[MaskRay]

Thanks:) Will wait a bit and push.

[lanza]

@MaskRay I haven't quite figured why yet, but I'm hitting a runtime assert failure due to this diff in our internal CI builds. I'll try to reduce this, but it's failing on our internal codebase so I can't share right away. But, to summarize:

(gdb) bt
#0  __pthread_kill_internal (signo=6, threadid=<optimized out>) at third-party2/glibc/2.34/src/glibc-2.34/nptl/pthread_kill.c:45
#1  __GI___pthread_kill (threadid=<optimized out>, signo=6) at third-party2/glibc/2.34/src/glibc-2.34/nptl/pthread_kill.c:62
#2  0x00007ffff7a6b4ed in __GI_raise (sig=6) at third-party2/glibc/2.34/src/glibc-2.34/signal/../sysdeps/posix/raise.c:26
#3  0x00007ffff7a53433 in __GI_abort () at third-party2/glibc/2.34/src/glibc-2.34/stdlib/abort.c:79
#4  0x00007ffff7a62c28 in __assert_fail_base (fmt=0x7ffff7c091d8 "%s%s%s:%u: %s%sAssertion `%s' failed.\n%n", assertion=0x5555561efe21 "N <= capacity()", file=0x5555560be0c1 "/data/users/lanza/toolchain-15.x/external/llvm-project/llvm/include/llvm/ADT/SmallVector.h", line=81, function=<optimized out>) at third-party2/glibc/2.34/src/glibc-2.34/assert/assert.c:92
#5  0x00007ffff7a62c93 in __GI___assert_fail (assertion=0x5555561efe21 "N <= capacity()", file=0x5555560be0c1 "/data/users/lanza/toolchain-15.x/external/llvm-project/llvm/include/llvm/ADT/SmallVector.h", line=81, function=0x555555e58ffb "void llvm::SmallVectorBase<unsigned long>::set_size(size_t) [Size_T = unsigned long]") at third-party2/glibc/2.34/src/glibc-2.34/assert/assert.c:101
#6  0x00005555578f9bc2 in llvm::SmallVectorBase<unsigned long>::set_size (this=0x55555a6b6798, N=14) at /data/users/lanza/toolchain-15.x/external/llvm-project/llvm/include/llvm/ADT/SmallVector.h:81
#7  llvm::SmallVectorImpl<char>::append<char const*, void> (this=0x55555a6b6798, in_start=0x5555564aea8f "lto.tmp", in_end=0x5555564aea96 "") at /data/users/lanza/toolchain-15.x/external/llvm-project/llvm/include/llvm/ADT/SmallVector.h:672
#8  0x0000555557a93032 in llvm::SmallVectorImpl<char>::assign<char const*, void> (this=0x55555a6b6798, in_start=0x11816b <error: Cannot access memory at address 0x11816b>, in_end=<optimized out>) at /data/users/lanza/toolchain-15.x/external/llvm-project/llvm/include/llvm/ADT/SmallVector.h:714
#9  llvm::SmallString<0u>::assign (this=0x55555a6b6798, RHS="") at /data/users/lanza/toolchain-15.x/external/llvm-project/llvm/include/llvm/ADT/SmallString.h:52
#10 llvm::SmallString<0u>::operator= (this=0x55555a6b6798, RHS="") at /data/users/lanza/toolchain-15.x/external/llvm-project/llvm/include/llvm/ADT/SmallString.h:278
#11 lld::toString[abi:cxx11](lld::elf::InputFile const*) (f=0x55555a6b6720) at /data/users/lanza/toolchain-15.x/external/llvm-project/lld/ELF/InputFiles.cpp:55
#12 0x0000555557ad3fec in lld::elf::InputSectionBase::getLocation[abi:cxx11](unsigned long) (this=0x55555af734a0, this@entry=0x7fffffff4a58, offset=offset@entry=0) at /data/users/lanza/toolchain-15.x/external/llvm-project/lld/ELF/InputSection.cpp:251
#13 0x0000555557ae0f5d in lld::elf::InputSection::relocateNonAlloc<llvm::object::ELFType<(llvm::support::endianness)1, false>, llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, false> > (this=this@entry=0x55555af734a0, buf=buf@entry=0x7fffe5ebec6c "", rels=...) at /data/users/lanza/toolchain-15.x/external/llvm-project/lld/ELF/InputSection.cpp:910
#14 0x0000555557ad9066 in lld::elf::InputSectionBase::relocate<llvm::object::ELFType<(llvm::support::endianness)1, false> > (this=0x55555af734a0, buf=0x7fffe5ebec6c "", bufEnd=<optimized out>) at /data/users/lanza/toolchain-15.x/external/llvm-project/lld/ELF/InputSection.cpp:973
#15 0x0000555557b180ad in lld::elf::OutputSection::writeTo<llvm::object::ELFType<(llvm::support::endianness)1, false> >(unsigned char*)::{lambda(unsigned long)#2}::operator()(unsigned long) const (this=0x7fffffff4c58, i=3) at /data/users/lanza/toolchain-15.x/external/llvm-project/lld/ELF/OutputSections.cpp:434
#16 0x00005555579c66ab in llvm::function_ref<void (unsigned long)>::operator()(unsigned long) const (this=0x7fffffff4b50, params=3) at /data/users/lanza/toolchain-15.x/external/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:68
#17 llvm::parallelFor(unsigned long, unsigned long, llvm::function_ref<void (unsigned long)>) (Begin=3, Begin@entry=0, End=End@entry=4, Fn=...) at /data/users/lanza/toolchain-15.x/external/llvm-project/llvm/lib/Support/Parallel.cpp:201
#18 0x0000555557b1190d in lld::elf::OutputSection::writeTo<llvm::object::ELFType<(llvm::support::endianness)1, false> > (this=0x55555afc0078, buf=<optimized out>) at /data/users/lanza/toolchain-15.x/external/llvm-project/lld/ELF/OutputSections.cpp:429
#19 0x0000555557bcb296 in (anonymous namespace)::Writer<llvm::object::ELFType<(llvm::support::endianness)1, false> >::writeSections (this=<optimized out>) at /data/users/lanza/toolchain-15.x/external/llvm-project/lld/ELF/Writer.cpp:2920
#20 (anonymous namespace)::Writer<llvm::object::ELFType<(llvm::support::endianness)1, false> >::run (this=0x7fffffff4df0) at /data/users/lanza/toolchain-15.x/external/llvm-project/lld/ELF/Writer.cpp:598
#21 lld::elf::writeResult<llvm::object::ELFType<(llvm::support::endianness)1, false> > () at /data/users/lanza/toolchain-15.x/external/llvm-project/lld/ELF/Writer.cpp:99
#22 0x0000555557a5ad05 in lld::elf::LinkerDriver::link (this=this@entry=0x55555a5664e0, args=...) at /data/users/lanza/toolchain-15.x/external/llvm-project/lld/ELF/Driver.cpp:2843
#23 0x0000555557a4eb2c in lld::elf::LinkerDriver::linkerMain (this=0x55555a5664e0, argsArr=...) at /data/users/lanza/toolchain-15.x/external/llvm-project/lld/ELF/Driver.cpp:596
#24 0x0000555557a4da0b in lld::elf::link (args=llvm::ArrayRef of length 1086 = {...}, stdoutOS=..., stderrOS=..., exitEarly=<optimized out>, disableOutput=<optimized out>) at /data/users/lanza/toolchain-15.x/external/llvm-project/lld/ELF/Driver.cpp:128
#25 0x00005555578f5532 in lldMain (argc=argc@entry=1086, argv=argv@entry=0x7fffffff5f58, stdoutOS=..., stderrOS=..., exitEarly=true) at /data/users/lanza/toolchain-15.x/external/llvm-project/lld/tools/lld/lld.cpp:1
64
#26 0x00005555578f4e0a in main (argc=1086, argv=0x7fffffff5f58) at /data/users/lanza/toolchain-15.x/external/llvm-project/lld/tools/lld/lld.cpp:226

We have an InputFile with toStringCache.emtpy() being true and f->getName() yielding lto.tmp. f->toStringCache = f->getName() ends up causing f->toStringCache to be garbagelto.tmp with size = 7 and capacity = 7 and then set_size(7 + 7) called which we crash on assert(N <= capacity() where N is 14.

This is while linking an armv7 so with FullLTO.

[MaskRay]

No idea from the existing information :)

llvm/include/llvm/ADT/SmallVector.h

 protected:
   using SmallVectorTemplateBase<T>::TakesParamByValue;
   using ValueParamT = typename SuperClass::ValueParamT;
 
   // Default ctor - Initialize to empty.
   explicit SmallVectorImpl(unsigned N)
       : SmallVectorTemplateBase<T>(N) {}
 
+  void assignRemote(SmallVectorImpl &&RHS) {
+    this->destroy_range(this->begin(), this->end());
+    if (!this->isSmall())
+      free(this->begin());
+    this->BeginX = RHS.BeginX;
+    this->Size = RHS.Size;
+    this->Capacity = RHS.Capacity;
+    RHS.resetToSmall();
+  }
+
 public:
   SmallVectorImpl(const SmallVectorImpl &) = delete;
 
   ~SmallVectorImpl() {
     // Subclass has already destructed this vector's elements.
     // If this wasn't grown from the inline copy, deallocate the old space.
     if (!this->isSmall())
       free(this->begin());

 }
 
 template <typename T>
 SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
   // Avoid self-assignment.
   if (this == &RHS) return *this;
 
   // If the RHS isn't small, clear this vector and then steal its buffer.
   if (!RHS.isSmall()) {
-    this->destroy_range(this->begin(), this->end());
-    if (!this->isSmall()) free(this->begin());
-    this->BeginX = RHS.BeginX;
-    this->Size = RHS.Size;
-    this->Capacity = RHS.Capacity;
-    RHS.resetToSmall();
+    this->assignRemote(std::move(RHS));
     return *this;
   }
 
   // If we already have sufficient space, assign the common elements, then
   // destroy any excess.
   size_t RHSSize = RHS.size();
   size_t CurSize = this->size();
   if (CurSize >= RHSSize) {
     // Assign common elements.
SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
     this->assign(IL);
   }
 
   SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
     if (!RHS.empty())
       SmallVectorImpl<T>::operator=(RHS);
   }
 
   SmallVector &operator=(const SmallVector &RHS) {
     SmallVectorImpl<T>::operator=(RHS);
     return *this;
   }
 
   SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
     if (!RHS.empty())
       SmallVectorImpl<T>::operator=(::std::move(RHS));
   }
 
   SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
     if (!RHS.empty())
       SmallVectorImpl<T>::operator=(::std::move(RHS));
   }
 
   SmallVector &operator=(SmallVector &&RHS) {
+    if (N) {
       SmallVectorImpl<T>::operator=(::std::move(RHS));
       return *this;
     }
+    // SmallVectorImpl<T>::operator= does not leverage N==0. Optimize the
+    // case.
+    if (this == &RHS)
+      return *this;
+    if (RHS.empty()) {
+      this->destroy_range(this->begin(), this->end());
+      this->Size = 0;
+    } else {
+      this->assignRemote(std::move(RHS));
+    }
+    return *this;
+  }
 
   SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
     SmallVectorImpl<T>::operator=(::std::move(RHS));
     return *this;
   }
 
   SmallVector &operator=(std::initializer_list<T> IL) {
     this->assign(IL);
     return *this;
   }
 };