Add an assertion in SmallVector::push_back()

[mehdi_amini]

Summary

This assertion ensures the input value isn't part of the vector when
growing is required. In such cases the vector will grow and the input
value is invalidated before being read from.

This found 14 failed Tests.

[bkramer]

Thanks!

[mehdi_amini]

llvm/include/llvm/MC/MCInst.h

187

Actually this is working around the assertion, but not fixing it.
The reference passed as input is invalidated by the reserve I think.

[silvas]

llvm/include/llvm/MC/MCInst.h

187

Could we switch this to take MCOperand by value? A copy is going to be made in the push_back anyway.

[dexonsmith]

FYI, there's also now https://reviews.llvm.org/D87326. I'd be in favour of landing this patch (with Sean's fix) while we wait for that one.

[njames93]

This assert should probably also be used (albeit some in a modified way) for:

• resize(size_type, const T&)
• append(size_type, const T&)
• insert(iterator, const T&)
• insert(iterator, T &&)
• insert(iterator, size_type, const T&)

As all these functions can grow and invalidate the reference.

[mehdi_amini]

Update with Sean's suggestion

[aartbik]

llvm/include/llvm/ADT/SmallVector.h

143

nit: s/enough/sufficient

[mehdi_amini]

llvm/include/llvm/MC/MCInst.h

187

Ah good point, MCOperand is cheap anyway.

[mehdi_amini]

Fix one clang instance failing this assertion

[njames93]

clang/lib/CodeGen/CGBuiltin.cpp

10811–10813 ↗

(On Diff #305279)

Probably a little off topic, but shouldn't this be refactored as a rotate. Has the advantage that it will never allocate.

[mehdi_amini]

clang/lib/CodeGen/CGBuiltin.cpp

10811–10813 ↗

(On Diff #305279)

Well spotted! I didn't even think about what the code was doing and fixed it mechanically...

I pushed this separately: https://github.com/llvm/llvm-project/commit/42e88bd6b185

llvm/include/llvm/ADT/SmallVector.h

protected:
   bool isSmall() const { return this->BeginX == getFirstEl(); }
 
   /// Put this vector in a state of being small.
   void resetToSmall() {
     this->BeginX = getFirstEl();
     this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
   }
 
+  void assertSafeToPush(const void *Elt) {
+    assert(
+        (Elt < begin() || Elt >= end() || this->size() < this->capacity()) &&
+        "Attempting to push_back to the vector an element of the vector without"
+        " enough space reserved");
+  }
+
 public:
   using size_type = size_t;
   using difference_type = ptrdiff_t;
   using value_type = T;
   using iterator = T *;
   using const_iterator = const T *;
 
   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
protected:
 
   /// Grow the allocated memory (without initializing new elements), doubling
   /// the size of the allocated memory. Guarantees space for at least one more
   /// element, or MinSize more elements if specified.
   void grow(size_t MinSize = 0);
 
 public:
   void push_back(const T &Elt) {
+    this->assertSafeToPush(&Elt);
     if (LLVM_UNLIKELY(this->size() >= this->capacity()))
       this->grow();
     ::new ((void*) this->end()) T(Elt);
     this->set_size(this->size() + 1);
   }
 
   void push_back(T &&Elt) {
+    this->assertSafeToPush(&Elt);
     if (LLVM_UNLIKELY(this->size() >= this->capacity()))
       this->grow();
     ::new ((void*) this->end()) T(::std::move(Elt));
     this->set_size(this->size() + 1);
   }
 
   void pop_back() {
     this->set_size(this->size() - 1);
protected:
   }
 
   /// Double the size of the allocated memory, guaranteeing space for at
   /// least one more element or MinSize if specified.
   void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
 
 public:
   void push_back(const T &Elt) {
+    this->assertSafeToPush(&Elt);
     if (LLVM_UNLIKELY(this->size() >= this->capacity()))
       this->grow();
     memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
     this->set_size(this->size() + 1);
   }
 
   void pop_back() { this->set_size(this->size() - 1); }
 };

llvm/include/llvm/MC/MCInst.h

public:
 
   void setLoc(SMLoc loc) { Loc = loc; }
   SMLoc getLoc() const { return Loc; }
 
   const MCOperand &getOperand(unsigned i) const { return Operands[i]; }
   MCOperand &getOperand(unsigned i) { return Operands[i]; }
   unsigned getNumOperands() const { return Operands.size(); }
 
-  void addOperand(const MCOperand &Op) { Operands.push_back(Op); }
+  void addOperand(const MCOperand Op) { Operands.push_back(Op); }
 
   using iterator = SmallVectorImpl<MCOperand>::iterator;
   using const_iterator = SmallVectorImpl<MCOperand>::const_iterator;
 
   void clear() { Operands.clear(); }
   void erase(iterator I) { Operands.erase(I); }
   void erase(iterator First, iterator Last) { Operands.erase(First, Last); }
   size_t size() const { return Operands.size(); }
   iterator begin() { return Operands.begin(); }
   const_iterator begin() const { return Operands.begin(); }
   iterator end() { return Operands.end(); }