[SmallVector] Allow SmallVector<T>

[silvas]

Summary

This patch adds a capability to SmallVector to decide a number of inlined elements automatically. The policy is:

• A minimum of 1 inlined elements, with more as long as sizeof(SmallVector<T>) <= 64.
• If sizeof(T) is "too big", then trigger a static_assert: this dodges the more pathological cases

This is expected to systematically improve SmallVector use in the
LLVM codebase, which has historically been plagued by semi-arbitrary /
cargo culted N parameters, often leading to bad outcomes due to
excessive sizeof(SmallVector<T, N>). This default also makes
programming more convenient by avoiding edit/rebuild cycles due to
forgetting to type the N parameter.

[silvas]

Created mistakenly (bad script). Abandoning.

llvm/docs/ProgrammersManual.rst

 fiddles around with the elements.
 
 This is good for vectors that are "usually small" (e.g. the number of
 predecessors/successors of a block is usually less than 8).  On the other hand,
 this makes the size of the SmallVector itself large, so you don't want to
 allocate lots of them (doing so will waste a lot of space).  As such,
 SmallVectors are most useful when on the stack.
 
+In the absence of a well-motivated choice for the number of
+inlined elements ``N``, it is recommended to use ``SmallVector<T>`` (that is,
+omitting the ``N``). This will automatically choose a reasonable number of
+inlined elements.
+
 SmallVector also provides a nice portable and efficient replacement for
 ``alloca``.
 
 SmallVector has grown a few other minor advantages over std::vector, causing
 ``SmallVector<Type, 0>`` to be preferred over ``std::vector<Type>``.
 
 #. std::vector is exception-safe, and some implementations have pessimizations
    that copy elements when SmallVector would move them.

llvm/include/llvm/ADT/SmallVector.h

struct SmallVectorStorage {
   alignas(T) char InlineElts[N * sizeof(T)];
 };
 
 /// We need the storage to be properly aligned even for small-size of 0 so that
 /// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
 /// well-defined.
 template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {};
 
+/// Forward declaration of SmallVector so that
+/// calculateSmallVectorDefaultInlinedElements can reference
+/// `sizeof(SmallVector<T, 0>)`.
+template <typename T, unsigned N> class LLVM_GSL_OWNER SmallVector;
+
+template <typename T>
+constexpr size_t calculateSmallVectorDefaultInlinedElements() {
+  // Parameter controlling the default number of inlined elements
+  // for `SmallVector<T>`.
+  //
+  // The default number of inlined elements ensures that
+  // 1. There is at least one inlined element.
+  // 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless
+  // it contradicts 1.
+  constexpr size_t kPreferredSmallVectorSizeof = 64;
+
+  // static_assert that sizeof(T) is not "too big".
+  //
+  // Because our policy guarantees at least one inlined element, it is possible
+  // for an arbitrarily large inlined element to allocate an arbitrarily large
+  // amount of inline storage. We generally consider it an antipattern for a
+  // SmallVector to allocate an excessive amount of inline storage, so we want
+  // to call attention to these cases and make sure that users are making an
+  // intentional decision if they request a lot of inline storage.
+  //
+  // We want this assertion to trigger in pathological cases, but otherwise
+  // not be too easy to hit. To accomplish that, the cutoff is actually somewhat
+  // larger than kPreferredSmallVectorSizeof (otherwise,
+  // `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that
+  // pattern seems useful in practice).
+  //
+  // One wrinkle is that this assertion is in theory non-portable, since
+  // sizeof(T) is in general platform-dependent. However, we don't expect this
+  // to be much of an issue, because most LLVM development happens on 64-bit
+  // hosts, and therefore sizeof(T) is expected to *decrease* when compiled for
+  // 32-bit hosts, dodging the issue. The reverse situation, where development
+  // happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a
+  // 64-bit host, is expected to be very rare.
+  static_assert(
+      sizeof(T) <= 256,
+      "You are trying to use a default number of inlined elements for "
+      "`SmallVector<T>` but `sizeof(T)` is really big! Please use an "
+      "explicit number of inlined elements with `SmallVector<T, N>` to make "
+      "sure you really want that much inline storage.");
+
+  // Discount the size of the header itself when calculating the maximum inline
+  // bytes.
+  size_t PreferredInlineBytes =
+      kPreferredSmallVectorSizeof - sizeof(SmallVector<T, 0>);
+  size_t NumElementsThatFit = PreferredInlineBytes / sizeof(T);
+  return NumElementsThatFit == 0 ? 1 : NumElementsThatFit;
+}
+
 /// This is a 'vector' (really, a variable-sized array), optimized
 /// for the case when the array is small.  It contains some number of elements
 /// in-place, which allows it to avoid heap allocation when the actual number of
 /// elements is below that threshold.  This allows normal "small" cases to be
 /// fast without losing generality for large inputs.
 ///
 /// Note that this does not attempt to be exception safe.
 ///
-template <typename T, unsigned N>
+template <typename T,
+          unsigned N = calculateSmallVectorDefaultInlinedElements<T>()>
 class LLVM_GSL_OWNER SmallVector : public SmallVectorImpl<T>,
                                    SmallVectorStorage<T, N> {
 public:
   SmallVector() : SmallVectorImpl<T>(N) {}
 
   ~SmallVector() {
     // Destroy the constructed elements in the vector.
     this->destroy_range(this->begin(), this->end());

llvm/unittests/ADT/SmallVectorTest.cpp

TEST(SmallVectorTest, InitializerList) {
   V2.assign({4});
   EXPECT_TRUE(makeArrayRef(V2).equals({4}));
   V2.append({3, 2});
   EXPECT_TRUE(makeArrayRef(V2).equals({4, 3, 2}));
   V2.insert(V2.begin() + 1, 5);
   EXPECT_TRUE(makeArrayRef(V2).equals({4, 5, 3, 2}));
 }
 
+TEST(SmallVectorTest, DefaultInlinedElements) {
+  SmallVector<int> V;
+  EXPECT_TRUE(V.empty());
+  V.push_back(7);
+  EXPECT_EQ(V[0], 7);
+
+  // Check that at least a couple layers of nested SmallVector<T>'s are allowed
+  // by the default inline elements policy. This pattern happens in practice
+  // with some frequency, and it seems fairly harmless even though each layer of
+  // SmallVector's will grow the total sizeof by a vector header beyond the
+  // "preferred" maximum sizeof.
+  SmallVector<SmallVector<SmallVector<int>>> NestedV;
+  NestedV.emplace_back().emplace_back().emplace_back(42);
+  EXPECT_EQ(NestedV[0][0][0], 42);
+}
+
 } // end namespace