[NFC] Add llvm::StaticVector ADT

[jplayer-nv]

Summary

I have implemented llvm::StaticVector, which is a fixed-capacity vector class. Think llvm::SmallVector without the ability to grow beyond its inline storage capacity. The llvm::StaticVector is lower overhead than an llvm::SmallVector with similar inline storage capacity:

Class storage savings:

1. There is no data pointer; only the inline storage.
2. The Size member can have its type scaled back depending on the stated capacity to save a few bytes. For example: sizeof(StaticVector<char,200>) == 201 since a uint8_t is sufficient to track the max number of elements.

Host generated code size savings:

1. Heap buffer growth related code is not generated; thus eliminating control-flow + code size on common member functions.

If the user knows the required capacity at compile-time, then a StaticVector would be a more efficient choice than the jack-of-all-trades SmallVector. Compared to a std::array, there are nice properties to exploit as well. For example, not elements are constructed when an empty StaticVector object is instantiated (compared to a std::array, which constructs all its elements when instantiated).

[mehdi_amini]

Related discussion FYI: https://llvm.discourse.group/t/adt-staticvector-implementation/4543/

[tschuett]

could fallible operations ala push_back return an llvm::error?

[jplayer-nv]

In D112175#3076343, @tschuett wrote:

could fallible operations ala push_back return an llvm::error?

I would think it better to return an llvm::Expected<reference> in that case so we can still return the newly inserted reference to the user. It would also break API compatibility with llvm::SmallVector, requiring more refactoring than simply changing the container type.

Additionally seems like unwanted overhead in a class which is meant to be a leaned version of SmallVector when we know the max capacity at host compile time.

If we follow through on this, I'd prefer add to the API rather than change the existing member functions (i.e. add member function push_back_fallible(), so users can opt-in to llvm::Expected return).

Relevant statements from the proposed std::static_vector spec:

Exception Safety
Two main answers were explored in the prototype implementation:

1. Throw an exception.
2. Make this a precondition violation.

Throwing an exception is appealing because it makes the interface slightly more similar to that of std::vector. However, which exception should be thrown? It cannot be std::bad_alloc, because nothing is being allocated. It could throw either std::out_of_bounds or std::logic_error but in any case the interface does not end up being equal to that of std::vector.

The alternative is to make not exceeding the capacity a precondition on the static_vector's methods. This approach allows implementations to provide good run-time diagnostics if they so desired, e.g., on debug builds by means of an assertion, and makes implementation that avoid run-time checks conforming as well. Since the mutating methods have a precondition, they have narrow contracts, and are not conditionally noexcept.

This proposal chooses this path and makes exceeding the static_vector's capacity a precondition violation that results in undefined behavior. Throwing checked_xxx methods can be provided in a backwards compatible way.

I subscribe to the checked_push_back() addition mentioned above.

[jplayer-nv]

Reverse include order of ArrayRef.h and StaticVector.h in unit test code to address pre-merge check failure.

[tschuett]

If the unit test is the only user, then you are bringing dead code. Do you have a real user?

[dblaikie]

In D112175#3078438, @tschuett wrote:

If the unit test is the only user, then you are bringing dead code. Do you have a real user?

+1 to this, basically - might be worth deferring reviewing/committing this until some use-case is confirmed? (I realize it creates somewhat of a chicken-or-egg problem - reviewing a dependent patch before the underlying one, but that might be beneficial to review the use case without having to worry about all these implementation details (knowing they're there, though, in terms of evaluating the total cost of the feature - so it's good to have this accessible for reference/high level understanding))

[craig.topper]

In D112175#3079311, @dblaikie wrote:

In D112175#3078438, @tschuett wrote:

If the unit test is the only user, then you are bringing dead code. Do you have a real user?

+1 to this, basically - might be worth deferring reviewing/committing this until some use-case is confirmed? (I realize it creates somewhat of a chicken-or-egg problem - reviewing a dependent patch before the underlying one, but that might be beneficial to review the use case without having to worry about all these implementation details (knowing they're there, though, in terms of evaluating the total cost of the feature - so it's good to have this accessible for reference/high level understanding))

Off the top of my head, I know there are a bunch of SmallVectors in X86ISelLowering with inline size equal to the maximum size that will occur. For example, there's one in LowerVectorCTLZInRegLUT with inline size of 64. 64 is the maximum number of elements on AVX512.

[jplayer-nv]

I don't see too many simple substitutions in target independent code, although this class has a SmallVector which never exceeds the inline storage (drop-in type substitution + with YAML binding works):

include\llvm\DebugInfo\CodeView\TypeRecord.h:

// LF_BUILDINFO
class BuildInfoRecord : public TypeRecord {
public:
  BuildInfoRecord() = default;
  explicit BuildInfoRecord(TypeRecordKind Kind) : TypeRecord(Kind) {}
  BuildInfoRecord(ArrayRef<TypeIndex> ArgIndices)
      : TypeRecord(TypeRecordKind::BuildInfo),
        ArgIndices(ArgIndices.begin(), ArgIndices.end()) {}

  ArrayRef<TypeIndex> getArgs() const { return ArgIndices; }

  /// Indices of known build info arguments.
  enum BuildInfoArg {
    CurrentDirectory, ///< Absolute CWD path
    BuildTool,        ///< Absolute compiler path
    SourceFile,       ///< Path to main source file, relative or absolute
    TypeServerPDB,    ///< Absolute path of type server PDB (/Fd)
    CommandLine,      ///< Full canonical command line (maybe -cc1)
    MaxArgs
  };

  StaticVector<TypeIndex, MaxArgs> ArgIndices;
};

Is the above substitution sufficient to move forward with a review? Or would you like to see more wide-spread usage?

I suspect this container is going to be more attractive in target-specific code (as is my interest). Is it appropriate for me to modify target-specific code to roll out a container like this?

could fallible operations ala push_back return an llvm::error?

I implemented a subset of checked_XXX versions of fallible member functions this morning. If this is an attractive feature, I can work on a complete set of them and add them to the patch.

[dblaikie]

In D112175#3079442, @jplayer-nv wrote:

I don't see too many simple substitutions in target independent code, although this class has a SmallVector which never exceeds the inline storage (drop-in type substitution + with YAML binding works):

include\llvm\DebugInfo\CodeView\TypeRecord.h:

// LF_BUILDINFO
class BuildInfoRecord : public TypeRecord {
public:
  BuildInfoRecord() = default;
  explicit BuildInfoRecord(TypeRecordKind Kind) : TypeRecord(Kind) {}
  BuildInfoRecord(ArrayRef<TypeIndex> ArgIndices)
      : TypeRecord(TypeRecordKind::BuildInfo),
        ArgIndices(ArgIndices.begin(), ArgIndices.end()) {}

  ArrayRef<TypeIndex> getArgs() const { return ArgIndices; }

  /// Indices of known build info arguments.
  enum BuildInfoArg {
    CurrentDirectory, ///< Absolute CWD path
    BuildTool,        ///< Absolute compiler path
    SourceFile,       ///< Path to main source file, relative or absolute
    TypeServerPDB,    ///< Absolute path of type server PDB (/Fd)
    CommandLine,      ///< Full canonical command line (maybe -cc1)
    MaxArgs
  };

  StaticVector<TypeIndex, MaxArgs> ArgIndices;
};

Is the above substitution sufficient to move forward with a review? Or would you like to see more wide-spread usage?

Not sure - what's your take, @craig.topper / @tschuett

It's still quite a bit of code, not sure what the tipping point in adding all that compared to what benefits would justify it? (whether there's a "this much code size" or "this much performance", etc, that would justify this)

I suspect this container is going to be more attractive in target-specific code (as is my interest). Is it appropriate for me to modify target-specific code to roll out a container like this?

could fallible operations ala push_back return an llvm::error?

I implemented a subset of checked_XXX versions of fallible member functions this morning. If this is an attractive feature, I can work on a complete set of them and add them to the patch.

[jplayer-nv]

• Define the MSVC visualizer for StaticVector.
• Bind StaticVector a simple yaml sequence.
• Change StaticVector::Capacity to an enum to make it available from the visualizer.
• Substitute some SmallVectors which never grow beyond inline storage.

[mehdi_amini]

llvm/lib/Target/X86/X86ISelLowering.cpp

27958 ↗

(On Diff #381414)

I'm really not convinced that this is a good use of this data structure: the invariant that makes 64 value enough is non trivial and hard to validate.
The code above is:

int NumElts = VT.getVectorNumElements();
int NumBytes = NumElts * (VT.getScalarSizeInBits() / 8);

It isn't clear from there where the 64 comes from and what guarantee we have it'll be enough "always".
More importantly: I'm not convinced that this is the kind of situation where we would want "by construction" to never exceed the SmallVector or if instead it just isn't best to continue to "just" have SmallVector as an optimization without change in the overall "behavior contract" that usual with vectors.

On the other hand, I find the YAML example more convincing.

[mgorny]

I'd grep for std::array<llvm::Optional<...>, ...> — I suppose this would be a good replacement for at least some instances of that.

[jplayer-nv]

In D112175#3080023, @mgorny wrote:

I'd grep for std::array<llvm::Optional<...>, ...> — I suppose this would be a good replacement for at least some instances of that.

I only found one instance of this construct in DWARF code. As far as I could tell, the array was being accessed at ad-hoc indexes and therefore isn't ideal for a conversion to StaticVector (i.e. you don't get to drop the Optional on the value_type). If you know of any more specific examples of above, let me know!

I'm not giving up here... but it doesn't seem like there are many more obvious + simple conversions. Unfortunately, the common construct I've converted in other code bases in the past is a C-array with a separate variable tracking the number of valid elements in that array. This is difficult / if not impossible to grep for.

My hope is that developers would run with this container if made available. So maybe this patch can just sit here until a suitable use is identified.

[jplayer-nv]

Here's another example of a possible StaticVector conversion:

llvm/lib/MC/WinCOFFObjectWriter.cpp

void WinCOFFObjectWriter::SetSectionName(COFFSection &S) {
...
  uint64_t StringTableEntry = Strings.getOffset(S.Name);
  if (StringTableEntry <= Max7DecimalOffset) {
    SmallVector<char, COFF::NameSize> Buffer;
    Twine('/').concat(Twine(StringTableEntry)).toVector(Buffer);
    assert(Buffer.size() <= COFF::NameSize && Buffer.size() >= 2);
    std::memcpy(S.Header.Name, Buffer.data(), Buffer.size());
    return;
  }
...
}

It's not as simple as a container type substitution since I haven't defined a raw_pwrite_stream for StaticVector. Assuming that's done, this shouldn't be a problem.

One nice benefit is that the container implicitly enforces:

assert(Buffer.size() <= COFF::NameSize);

Will keep searching.

[mehdi_amini]

In D112175#3091114, @jplayer-nv wrote:

Here's another example of a possible StaticVector conversion:

llvm/lib/MC/WinCOFFObjectWriter.cpp
...

Yeah that seems like the perfect case! (I don't think it's common in the compiler world though, but happy to be proven wrong).

[jplayer-nv]

Resurrecting this review for the following:

1. I defined checked_ versions of member functions which may grow the container beyond its buffer capacity. All checked_ member functions return an llvm::Error or llvm::Expected.

2. I found a more compelling potential use of the StaticVector as the llvm::SmallSet's underlying small storage.

[jplayer-nv]

Call llvm::consumeError() when an Error is returned in the StaticVector unit test.

Also minor formatting + parameter type name consistency changes.

[dblaikie]

In D112175#3092225, @mehdi_amini wrote:

In D112175#3091114, @jplayer-nv wrote:

Here's another example of a possible StaticVector conversion:

llvm/lib/MC/WinCOFFObjectWriter.cpp
...

Yeah that seems like the perfect case! (I don't think it's common in the compiler world though, but happy to be proven wrong).

Yeah, even here it seems like an assert after populating the vector isn't especially costly/problematic - for me even a bunch of those across the codebase seems hard for me to justify the several thousands of lines similar vector code/testing/etc. That's my gut feeling at the moment at least.

[jplayer-nv]

Just to give a concrete example of what I believe to be the benefit behind StaticVector, I ran this contrived test pitting SmallVector<uint64_t,N> vs StaticVector<uint64_t,N> (with a few tweaks to ensure the push_back param is passsed by value like in SmallVector):

TYPED_TEST(StaticVsSmall, TimedStaticVector) {
  const size_t N = this->NumBuiltinElts(this->TheStaticVector);
  for (int I = 0; I < OutterLimit; ++I) {
    this->TheStaticVector.clear();
    for (int J = 0; J < N; ++J) {
      this->TheStaticVector.push_back(I + J);
    }
  }
}

TYPED_TEST(StaticVsSmall, TimedSmallVector) {
  const size_t N = this->NumBuiltinElts(this->TheSmallVector);
  for (int I = 0; I < OutterLimit; ++I) {
    this->TheSmallVector.clear();
    for (int J = 0; J < N; ++J) {
      this->TheSmallVector.push_back(I + J);
    }
  }
}

My local results are:

[ RUN      ] StaticVsSmall/0.TimedStaticVector
[       OK ] StaticVsSmall/0.TimedStaticVector (371 ms)
[ RUN      ] StaticVsSmall/0.TimedSmallVector
[       OK ] StaticVsSmall/0.TimedSmallVector (596 ms)

Which demonstrates that simple insertions are significantly faster (almost 38%) with the StaticVector compared to a SmallVector which stays within its small buffer limit.

I would think it interesting to speed up SmallSet insertions by retargeting the small storage to a StaticVector.

[jplayer-nv]

[ RUN      ] StaticVsSmall/0.TimedStaticVector
[       OK ] StaticVsSmall/0.TimedStaticVector (371 ms)
[ RUN      ] StaticVsSmall/0.TimedSmallVector
[       OK ] StaticVsSmall/0.TimedSmallVector (596 ms)

Which demonstrates that simple insertions are significantly faster (almost 38%) with the StaticVector compared to a SmallVector which stays within its small buffer limit.

Let me amend this a bit... it looks like the reason SmallVector::push_back is slower in this case is because of insufficient specialization. Here's the trivially copyable version:

void push_back(ValueParamT Elt) {
  const T *EltPtr = reserveForParamAndGetAddress(Elt);
  memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));
  this->set_size(this->size() + 1);
}

When Elt is passed by value, reserveForParamAndGetAddress() is unnecessary since the parameter will not alias with the SmallVector's buffer. This inhibits host compiler optimization. If we were to SFINAE split this function, we can match my StaticVector::push_back perf. The following SmallVector change works for me locally:

  template <typename RetT = std::enable_if_t<TakesParamByValue>>
  RetT push_back_impl(value_type Elt) {
    if (LLVM_UNLIKELY(this->size() >= this->capacity()))
      this->grow();
    memcpy(reinterpret_cast<void *>(this->end()), std::addressof(Elt),
           sizeof(T));
    this->set_size(this->size() + 1);
  }

  template <typename RetT = std::enable_if_t<!TakesParamByValue>>
  RetT push_back_impl(const_reference Elt) {
    const T *EltPtr = reserveForParamAndGetAddress(Elt);
    memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));
    this->set_size(this->size() + 1);
  }

public:
  void push_back(ValueParamT Elt) { push_back_impl(Elt); }

[dexonsmith]

In D112175#3481680, @jplayer-nv wrote:

[ RUN      ] StaticVsSmall/0.TimedStaticVector
[       OK ] StaticVsSmall/0.TimedStaticVector (371 ms)
[ RUN      ] StaticVsSmall/0.TimedSmallVector
[       OK ] StaticVsSmall/0.TimedSmallVector (596 ms)

Which demonstrates that simple insertions are significantly faster (almost 38%) with the StaticVector compared to a SmallVector which stays within its small buffer limit.

Let me amend this a bit... it looks like the reason SmallVector::push_back is slower in this case is because of insufficient specialization. Here's the trivially copyable version:

void push_back(ValueParamT Elt) {
  const T *EltPtr = reserveForParamAndGetAddress(Elt);
  memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));
  this->set_size(this->size() + 1);
}

When Elt is passed by value, reserveForParamAndGetAddress() is unnecessary since the parameter will not alias with the SmallVector's buffer. This inhibits host compiler optimization. If we were to SFINAE split this function, we can match my StaticVector::push_back perf. The following SmallVector change works for me locally:

  template <typename RetT = std::enable_if_t<TakesParamByValue>>
  RetT push_back_impl(value_type Elt) {
    if (LLVM_UNLIKELY(this->size() >= this->capacity()))
      this->grow();
    memcpy(reinterpret_cast<void *>(this->end()), std::addressof(Elt),
           sizeof(T));
    this->set_size(this->size() + 1);
  }

  template <typename RetT = std::enable_if_t<!TakesParamByValue>>
  RetT push_back_impl(const_reference Elt) {
    const T *EltPtr = reserveForParamAndGetAddress(Elt);
    memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));
    this->set_size(this->size() + 1);
  }

public:
  void push_back(ValueParamT Elt) { push_back_impl(Elt); }

Nice find.

When we added this assertion, we checked the compile time suite and didn't get regressions. The theory being that the optimizer *should* have enough info to get to the same place on its own since it has this code reserveForParamAndGetAddress:

size_t NewSize = This->size() + N;
if (LLVM_LIKELY(NewSize <= This->capacity()))
  return &Elt;

bool ReferencesStorage = false;
int64_t Index = -1;
if (!U::TakesParamByValue) {
  if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))) {
    ReferencesStorage = true;
    Index = &Elt - This->begin();
  }
}
This->grow(NewSize);
return ReferencesStorage ? This->begin() + Index : &Elt;

Ideally the outer if would be if constexpr(!U::TakesParamByValue) but that needs to wait for C++17.

The current implementation is easy to verify since the check is just in one place. Is it just a synthetic benchmark where it's causing a slowdown? Or, can we help the optimizer along somehow without changing the layering? (I don't feel strongly attached to exact design of the current thing, but IIRC it took some compromise at the time to make everyone happy. But I could be remembering the patch series incorrectly.)

[dexonsmith]

If your host toolchain has C++17, I'd be curious if the regression goes away when you switch to that mode and use if constexpr.

I'd also be curious how this performs on your benchmark (after you fix the compiler errors / etc.):

template <class U, std::enable_if_t<U::TakesParamByValue, bool> = false>
static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
                                                 size_t N) {
  size_t NewSize = This->size() + N;
  if (LLVM_LIKELY(NewSize <= This->capacity()))
    return &Elt;

  This->grow(NewSize);
  return &Elt;
}
template <class U, std::enable_if_t<!U::TakesParamByValue, bool> = false>
static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
                                                 size_t N) {
  size_t NewSize = This->size() + N;
  if (LLVM_LIKELY(NewSize <= This->capacity()))
    return &Elt;

  bool ReferencesStorage = false;
  int64_t Index = -1;
  if (!U::TakesParamByValue) {
    if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))) {
      ReferencesStorage = true;
      Index = &Elt - This->begin();
    }
  }
  This->grow(NewSize);
  return ReferencesStorage ? This->begin() + Index : &Elt;
}

Seems like it should be mostly equivalent to your solution, but the specialization is at a lower level where it's easy to verify the logic is equivalent... and it's also still obvious how if constexpr would apply once we have it.

[tschuett]

You could use __cplusplus to determine the C++ version.

Or check __cpp_if_constexpr == 201606.

[jplayer-nv]

In D112175#3481996, @dexonsmith wrote:

Ideally the outer if would be if constexpr(!U::TakesParamByValue) but that needs to wait for C++17.

The current implementation is easy to verify since the check is just in one place. Is it just a synthetic benchmark where it's causing a slowdown? Or, can we help the optimizer along somehow without changing the layering? (I don't feel strongly attached to exact design of the current thing, but IIRC it took some compromise at the time to make everyone happy. But I could be remembering the patch series incorrectly.)

Just tried compiling for C++20 and added the constexpr. No improvement in runtime. FYI I'm building on nearly the latest MSVC 2022 (just one update behind).

My benchmark is just a contrived loop of push_back calls to the small storage.

My time is a bit fragmented today... I'll give your suggested reserveForParamAndGetAddressImpl() changes a whirl later and report back.

[jplayer-nv]

In D112175#3482069, @dexonsmith wrote:

If your host toolchain has C++17, I'd be curious if the regression goes away when you switch to that mode and use if constexpr.

I'd also be curious how this performs on your benchmark (after you fix the compiler errors / etc.):

template <class U, std::enable_if_t<U::TakesParamByValue, bool> = false>
static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
                                                 size_t N) {
  size_t NewSize = This->size() + N;
  if (LLVM_LIKELY(NewSize <= This->capacity()))
    return &Elt;

  This->grow(NewSize);
  return &Elt;
}
template <class U, std::enable_if_t<!U::TakesParamByValue, bool> = false>
static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
                                                 size_t N) {
  size_t NewSize = This->size() + N;
  if (LLVM_LIKELY(NewSize <= This->capacity()))
    return &Elt;

  bool ReferencesStorage = false;
  int64_t Index = -1;
  if (!U::TakesParamByValue) {
    if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))) {
      ReferencesStorage = true;
      Index = &Elt - This->begin();
    }
  }
  This->grow(NewSize);
  return ReferencesStorage ? This->begin() + Index : &Elt;
}

Seems like it should be mostly equivalent to your solution, but the specialization is at a lower level where it's easy to verify the logic is equivalent... and it's also still obvious how if constexpr would apply once we have it.

The above change does improve the results, but not quite as much as specializing at the push_back level.

For my toy benchmark, I'm seeing:

Change	Time (ms)	% Reduction
TOT	1190	-
specialized reserveForParamAndGetAddressImpl	750	37.0%
specialized push_back	695	41.6%

I tried a couple minor variations of my benchmark and all generate similar results.

[dexonsmith]

Thanks for running that. I just pushed https://github.com/dexonsmith/llvm-project/tree/perf/small-vector-specialize-reserveForParamAndGetAddressImpl, which should cause compile-time results to show up at http://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions&remote=dexonsmith eventually, and we can see if there's a meaningful impact outside of the benchmark. Not sure whether it's worth changing push_back() since even on the toy benchmark it's not a big difference.

[dexonsmith]

In D112175#3489247, @dexonsmith wrote:

Thanks for running that. I just pushed https://github.com/dexonsmith/llvm-project/tree/perf/small-vector-specialize-reserveForParamAndGetAddressImpl, which should cause compile-time results to show up at http://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions&remote=dexonsmith eventually, and we can see if there's a meaningful impact outside of the benchmark. Not sure whether it's worth changing push_back() since even on the toy benchmark it's not a big difference.

Also, it'd be interesting to look at what is different about the CodeGen, and hunt down why the optimizations are missed. Seems better to fix the optimizer than to add redundant specializations all over the place.

[dexonsmith]

In D112175#3489247, @dexonsmith wrote:

Thanks for running that. I just pushed https://github.com/dexonsmith/llvm-project/tree/perf/small-vector-specialize-reserveForParamAndGetAddressImpl, which should cause compile-time results to show up at http://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions&remote=dexonsmith eventually, and we can see if there's a meaningful impact outside of the benchmark. Not sure whether it's worth changing push_back() since even on the toy benchmark it's not a big difference.

Results here:
http://llvm-compile-time-tracker.com/compare.php?from=c1e17c7dfedd27b95c8c2fba2b6473c7348f0e77&to=0be905f5dec8ebc4bd0fc2ec498db88a617884fc&stat=instructions

Almost within the noise. One thing is "light green". @dblaikie , thoughts on whether it's worth landing? (I can send a Phab review)

[dblaikie]

In D112175#3489258, @dexonsmith wrote:

In D112175#3489247, @dexonsmith wrote:

Thanks for running that. I just pushed https://github.com/dexonsmith/llvm-project/tree/perf/small-vector-specialize-reserveForParamAndGetAddressImpl, which should cause compile-time results to show up at http://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions&remote=dexonsmith eventually, and we can see if there's a meaningful impact outside of the benchmark. Not sure whether it's worth changing push_back() since even on the toy benchmark it's not a big difference.

Also, it'd be interesting to look at what is different about the CodeGen, and hunt down why the optimizations are missed. Seems better to fix the optimizer than to add redundant specializations all over the place.

Yeah, it seems unfortunate that that produces any different code with or without the specialization, given it's one trivial/compile-time-constant condition & then a follow-on conditional operator.

In D112175#3492649, @dexonsmith wrote:

In D112175#3489247, @dexonsmith wrote:

Thanks for running that. I just pushed https://github.com/dexonsmith/llvm-project/tree/perf/small-vector-specialize-reserveForParamAndGetAddressImpl, which should cause compile-time results to show up at http://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions&remote=dexonsmith eventually, and we can see if there's a meaningful impact outside of the benchmark. Not sure whether it's worth changing push_back() since even on the toy benchmark it's not a big difference.

Results here:
http://llvm-compile-time-tracker.com/compare.php?from=c1e17c7dfedd27b95c8c2fba2b6473c7348f0e77&to=0be905f5dec8ebc4bd0fc2ec498db88a617884fc&stat=instructions

Almost within the noise. One thing is "light green". @dblaikie , thoughts on whether it's worth landing? (I can send a Phab review)

My gut would be probably not worth it - but if it's important to you/someone I could live with it. Though, yeah, would prefer to see the long-term fix, at least a comment near the specialization pointing to a bug that, once resolved, could then motivate removing the specialization agian.

llvm/include/llvm/ADT/STLExtras.h

 };
 
 template <typename T> struct make_const_ref {
   using type = typename std::add_lvalue_reference<
       typename std::add_const<T>::type>::type;
 };
 
 namespace detail {
-template <typename...> using void_t = void;
 template <class, template <class...> class Op, class... Args> struct detector {
   using value_t = std::false_type;
 };
 template <template <class...> class Op, class... Args>
 struct detector<void_t<Op<Args...>>, Op, Args...> {
   using value_t = std::true_type;
 };
 } // end namespace detail

llvm/include/llvm/ADT/STLForwardCompat.h

 };
 
 template <std::size_t I>
 struct in_place_index_t // NOLINT(readability-identifier-naming)
 {
   explicit in_place_index_t() = default;
 };
 
+template <typename...>
+using void_t = void; // NOLINT(readability-identifier-naming)
+
 //===----------------------------------------------------------------------===//
 //     Features from C++20
 //===----------------------------------------------------------------------===//
 
 template <typename T>
 struct remove_cvref // NOLINT(readability-identifier-naming)
 {
   using type = std::remove_cv_t<std::remove_reference_t<T>>;

llvm/include/llvm/ADT/StaticVector.h

+//===- StaticVector.h - Fixed-sized vector implementation ----------C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file StaticVector.h
+/// `llvm::StaticVector` class definition.
+///
+//===----------------------------------------------------------------------===//
+
+#pragma once
+#ifndef LLVM_ADT_STATICVECTOR_H
+#define LLVM_ADT_STATICVECTOR_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/STLForwardCompat.h"
+#include "llvm/Support/MathExtras.h"
+
+#include <cassert>
+#include <initializer_list>
+#include <iterator>
+#include <limits>
+#include <memory>
+#include <type_traits>
+#include <utility>
+
+namespace llvm {
+
+namespace detail {
+template <typename T, typename = void>
+class is_iterator : public std::false_type {};
+
+template <typename T>
+class is_iterator<T, void_t<typename std::iterator_traits<
+                         llvm::remove_cvref_t<T>>::iterator_category>>
+    : public std::true_type {};
+} // namespace detail
+
+/// Determine whether a type is an iterator (i.e. belongs to any iterator
+/// category).
+template <typename T> using is_iterator = detail::is_iterator<T>;
+
+/// Determine whether a type belongs to the specified iterator category.
+///
+/// @tparam T    Iterator type to query.
+/// @tparam Cat  Iterator category `T` must belong to.
+template <typename I, typename Cat, bool = is_iterator<I>::value>
+class is_iterator_category : public std::false_type {};
+
+template <typename I, typename Cat>
+class is_iterator_category<I, Cat, true>
+    : public // clang-format off
+  std::is_base_of<
+    Cat,
+    typename std::iterator_traits<
+      std::remove_reference_t<I>
+    >::iterator_category
+  > // clang-format on
+{};
+
+template <typename T>
+using is_input_iterator = is_iterator_category<T, std::input_iterator_tag>;
+
+namespace detail {
+template <typename T, typename = void>
+class has_begin_member : public std::false_type {};
+
+template <typename T>
+class has_begin_member<T, void_t<decltype(std::declval<T>().begin())>>
+    : public std::true_type {};
+
+template <typename T, typename = void>
+class has_begin_adl : public std::false_type {};
+
+template <typename T>
+class has_begin_adl<T, void_t<decltype(begin(std::declval<T>()))>>
+    : public std::true_type {};
+
+template <typename T, typename = void>
+class has_begin_std : public std::false_type {};
+
+template <typename T>
+class has_begin_std<T, void_t<decltype(std::begin(std::declval<T>()))>>
+    : public std::true_type {};
+
+template <typename T, typename = void>
+class has_end_member : public std::false_type {};
+
+template <typename T>
+class has_end_member<T, void_t<decltype(std::declval<T>().end())>>
+    : public std::true_type {};
+
+template <typename T, typename = void>
+class has_end_adl : public std::false_type {};
+
+template <typename T>
+class has_end_adl<T, void_t<decltype(end(std::declval<T>()))>>
+    : public std::true_type {};
+
+template <typename T, typename = void>
+class has_end_std : public std::false_type {};
+
+template <typename T>
+class has_end_std<T, void_t<decltype(std::end(std::declval<T>()))>>
+    : public std::true_type {};
+} // namespace detail
+
+template <typename T>
+using has_begin =
+    llvm::disjunction<detail::has_begin_member<T>, detail::has_begin_adl<T>,
+                      detail::has_begin_std<T>>;
+
+template <typename T>
+using has_end =
+    llvm::disjunction<detail::has_end_member<T>, detail::has_end_adl<T>,
+                      detail::has_end_std<T>>;
+
+namespace detail {
+/// Determine the return type of the `begin` function associated with a
+/// container type.
+///
+/// The type evaluates to `void` if no `begin` function is available.
+template <typename ContainerT, bool MEM = has_begin_member<ContainerT>::value,
+          bool ADL = has_begin_adl<ContainerT>::value,
+          bool STL = has_begin_std<ContainerT>::value>
+struct get_begin_type {
+  using type = void;
+};
+
+template <typename ContainerT, bool ADL, bool STL>
+struct get_begin_type<ContainerT, true, ADL, STL> {
+  using type = decltype(std::declval<ContainerT &>().begin());
+};
+
+template <typename ContainerT, bool STL>
+struct get_begin_type<ContainerT, false, true, STL> {
+  using type = decltype(begin(std::declval<ContainerT &>()));
+};
+
+template <typename ContainerT>
+struct get_begin_type<ContainerT, false, false, true> {
+  using type = decltype(std::begin(std::declval<ContainerT &>()));
+};
+
+/// Determine the return type of the `end` function associated with a
+/// container type.
+///
+/// The type evaluates to `void` if no `end` function is available.
+template <typename ContainerT, bool MEM = has_end_member<ContainerT>::value,
+          bool ADL = has_end_adl<ContainerT>::value,
+          bool STL = has_end_std<ContainerT>::value>
+struct get_end_type {
+  using type = void;
+};
+
+template <typename ContainerT, bool ADL, bool STL>
+struct get_end_type<ContainerT, true, ADL, STL> {
+  using type = decltype(std::declval<ContainerT &>().end());
+};
+
+template <typename ContainerT, bool STL>
+struct get_end_type<ContainerT, false, true, STL> {
+  using type = decltype(end(std::declval<ContainerT &>()));
+};
+
+template <typename ContainerT>
+struct get_end_type<ContainerT, false, false, true> {
+  using type = decltype(std::end(std::declval<ContainerT &>()));
+};
+} // namespace detail
+
+template <typename ContainerT>
+using get_begin_type = detail::get_begin_type<ContainerT>;
+
+template <typename ContainerT>
+using get_begin_type_t = typename get_begin_type<ContainerT>::type;
+
+template <typename ContainerT>
+using get_end_type = detail::get_end_type<ContainerT>;
+
+template <typename ContainerT>
+using get_end_type_t = typename get_end_type<ContainerT>::type;
+
+/// Determine whether a presumed container type can be iterated in the forward
+/// direction.
+///
+/// The container type must have begin + end functions that return the same
+/// type, and both those return types must belong to the input iterator
+/// category.
+template <typename ContainerT>
+using is_forward_iterable = // clang-format off
+  llvm::conjunction<
+    std::is_same<get_begin_type_t<ContainerT>, get_end_type_t<ContainerT>>,
+    is_input_iterator<
+      get_begin_type_t<ContainerT>
+    >
+  >; // clang-format on
+
+namespace detail {
+template <typename T, typename = void>
+class is_dereferenceable : public std::false_type {};
+
+template <typename T>
+class is_dereferenceable<T, void_t<decltype(*std::declval<T>())>>
+    : public std::true_type {};
+} // namespace detail
+template <typename T> using is_dereferenceable = detail::is_dereferenceable<T>;
+
+namespace detail {
+template <typename From, typename To, bool = is_input_iterator<From>::value>
+class is_convertible_input_iterator : public std::false_type {};
+
+template <typename From, typename To>
+class is_convertible_input_iterator<From, To, true>
+    : public std::is_convertible<decltype(*std::declval<From &>()), To> {};
+} // namespace detail
+template <typename From, typename To>
+using is_convertible_input_iterator =
+    detail::is_convertible_input_iterator<From, To>;
+
+template <typename ContainerT, typename To>
+using is_forward_iterable_and_convertible = // clang-format off
+  llvm::conjunction<
+    is_forward_iterable<ContainerT>,
+    is_convertible_input_iterator<get_begin_type_t<ContainerT>,To>
+  >; // clang-format on
+
+namespace static_vector_detail {
+
+template <size_t NArgs, typename... ArgsT> class EmplaceImplSelector;
+
+} // namespace static_vector_detail
+
+template <typename T, size_t C> class StaticVectorStorage {
+public:
+  using value_type = T;
+  using pointer = T *;
+  using reference = T &;
+  using const_pointer = T const *;
+  using const_reference = T const &;
+  using size_type = size_t;
+
+  static constexpr size_type Capacity = C;
+
+private:
+  // Choose the minmally sized unsigned integer which can represent the capacity
+  // of the StaticVector.
+  // clang-format off
+  using MinSizeStorageT =
+    std::conditional_t<isInt<8>(Capacity), uint8_t,
+      std::conditional_t<isInt<16>(Capacity), uint16_t,
+        std::conditional_t<isInt<32>(Capacity), uint32_t,
+          size_type
+        >
+      >
+    >;
+  // clang-format on
+
+  // Determine whether 'l' < 'r' at compile-time.
+  //
+  // Only defined because you can't use a '<' in a template argument without
+  // triggering a parse error.
+  static constexpr bool lessThan(size_t L, size_t R) { return L < R; }
+
+  // Only use the minimal storage size if it will actually reduce sizeof(*this).
+  using SizeStorageT =
+      std::conditional_t<lessThan(alignof(value_type), sizeof(size_type)),
+                         MinSizeStorageT, size_type>;
+
+private:
+  SizeStorageT Size;
+  std::aligned_storage_t<sizeof(T), alignof(T)> Data[Capacity];
+
+public:
+  constexpr StaticVectorStorage(size_t S = 0) : Size(S) {}
+
+  class ZeroInitTag {};
+  constexpr StaticVectorStorage(ZeroInitTag, size_t S = 0) : Size(S), Data{0} {}
+
+  pointer data() { return reinterpret_cast<pointer>(Data); }
+
+  constexpr const_pointer data() const {
+    return reinterpret_cast<const_pointer>(Data);
+  }
+
+  constexpr size_type size() const { return Size; }
+  constexpr size_type capacity() const { return Capacity; }
+
+  constexpr SizeStorageT rawSize() const { return Size; }
+
+  void setSize(size_type NewSize) {
+    assert(NewSize <= capacity());
+    Size = static_cast<SizeStorageT>(NewSize);
+  }
+};
+
+template <typename T> class StaticVectorStorage<T, 0> {
+public:
+  using value_type = T;
+  using pointer = T *;
+  using reference = T &;
+  using const_pointer = T const *;
+  using const_reference = T const &;
+  using size_type = size_t;
+
+  static constexpr size_type Capacity = 0;
+
+  constexpr StaticVectorStorage(size_type S = 0) {}
+
+  class ZeroInitTag {};
+  constexpr StaticVectorStorage(ZeroInitTag) {}
+
+  pointer data() { return nullptr; }
+  constexpr const_pointer data() const { return nullptr; }
+
+  constexpr size_type size() const { return 0; }
+  constexpr size_type capacity() const { return 0; }
+
+  constexpr size_type rawSize() const { return 0; }
+  void setSize(size_type NewSize) { assert(NewSize == 0); }
+};
+
+///
+///  Implements a version of the `vector` container with capacity fixed at
+///  compile-time.
+///
+///  Mostly follows the spec at:
+///   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0843r2.html
+///
+/// @tparam T  Type of data to be stored in the `StaticVector`.
+/// @tparam C  Capacity of the `StaticVector` container in number of elements.
+///
+/// @warning A large `C` implies a large `sizeof(StaticVector)`.  Be mindful
+///  of this relationship when declaring this container on the stack.
+///
+///  This container will not heap-allocate any storage.  All the storage is
+///  determined up-front at compile-time and resides within this container.
+///
+///  Essentially this container implements the `vector` API over top of a
+///  C-array with some special care taken to ensure that `T` need not be default
+///  constructible.
+///
+///  You can emplace elements on the back at low cost, and the container will
+///  track the number of valid elements for you.
+///
+template <typename T, size_t C>
+class StaticVector : private StaticVectorStorage<T, C> {
+  using StorageT = StaticVectorStorage<T, C>;
+
+public:
+  /// @name Basic container types
+  /// @{
+
+  /// Type of values stored in `StaticVector`.
+  using value_type = typename StorageT::value_type;
+
+  /// Pointer type of values stored in `StaticVector`.
+  using pointer = typename StorageT::pointer;
+
+  /// Reference type of values stored in `StaticVector`.
+  using reference = typename StorageT::reference;
+
+  /// const-qualified pointer type of values stored in `StaticVector`.
+  using const_pointer = typename StorageT::const_pointer;
+
+  /// const-qualified reference type of values stored in `StaticVector`.
+  using const_reference = typename StorageT::const_reference;
+
+  /// Integer type used to represent size.
+  using size_type = typename StorageT::size_type;
+  /// @}
+
+  /// @name Iterator types.
+  /// @{
+
+  /// Forward iterator for the `StaticVector` class.
+  using iterator = pointer;
+
+  /// Forward const-iterator for the `StaticVector` class.
+  using const_iterator = const_pointer;
+
+  /// Reverse iterator for the `StaticVector` class.
+  using reverse_iterator = std::reverse_iterator<iterator>;
+
+  /// Reverse const-iterator for the `StaticVector` class.
+  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+
+  /// @}
+
+  static constexpr size_type Capacity = C;
+
+private:
+  /// True if it's cheap enough to take parameters by value. Doing so avoids
+  /// overhead related to mitigations for reference invalidation.
+  static constexpr bool TakesParamByValue =
+      std::is_trivially_copyable<T>::value && sizeof(T) <= 2 * sizeof(void *);
+
+  /// Either const T& or T, depending on whether it's cheap enough to take
+  /// parameters by value.
+  using ValueParamT = typename std::conditional<TakesParamByValue, value_type,
+                                                const_reference>::type;
+
+public:
+  /// @name Constructors
+  /// @{
+  constexpr StaticVector() = default;
+
+  StaticVector(StaticVector const &Other);
+
+  StaticVector(StaticVector &&Other);
+
+  explicit StaticVector(size_type N);
+
+  StaticVector(size_type N, ValueParamT Val);
+
+  template <typename InputIt,
+            std::enable_if_t<is_convertible_input_iterator<InputIt, T>::value>
+                * = nullptr>
+  StaticVector(InputIt First, InputIt Last);
+
+  // clang-format off
+  template <
+    typename ContainerT,
+    std::enable_if_t<
+      llvm::conjunction<
+        negation<std::is_same<StaticVector,ContainerT>>,
+        is_forward_iterable_and_convertible<ContainerT, T>
+      >::value
+    > * = nullptr
+  > // clang-format on
+  StaticVector(ContainerT &&Container);
+
+  template <typename U,
+            std::enable_if_t<std::is_constructible<T, U>::value> * = nullptr>
+  StaticVector(std::initializer_list<U> IL);
+  /// @}
+
+  /// @name Destructor
+  /// @{
+  ~StaticVector();
+  /// @}
+
+  /// @name Assignment operators and methods
+  /// @{
+  auto operator=(StaticVector const &Other) -> StaticVector &;
+  auto operator=(StaticVector &&Other) -> StaticVector &;
+
+  template < // clang-format off
+    typename ContainerT,
+    std::enable_if_t<
+      conjunction<
+        negation<std::is_same<StaticVector,ContainerT>>,
+        is_forward_iterable_and_convertible<ContainerT, T>
+      >::value
+    > * = nullptr
+  > // clang-format on
+  auto operator=(ContainerT &&Container) -> StaticVector &;
+
+  template <typename InputIt,
+            std::enable_if_t<is_convertible_input_iterator<InputIt, T>::value>
+                * = nullptr>
+  auto assign(InputIt First, InputIt Last) -> StaticVector &;
+
+  auto assign(size_type N, ValueParamT Val) -> StaticVector &;
+
+  template <typename U,
+            std::enable_if_t<std::is_convertible<U, T>::value> * = nullptr>
+  auto assign(std::initializer_list<U> IL) -> StaticVector &;
+
+  template < // clang-format off
+    typename ContainerT,
+    std::enable_if_t<
+      is_forward_iterable_and_convertible<ContainerT, T>::value
+    > * = nullptr
+  > // clang-format on
+  auto assign(ContainerT &&Container) -> StaticVector &;
+
+  /// @}
+
+  /// @name Begin & End methods
+  /// @{
+  auto begin() -> iterator;
+  auto end() -> iterator;
+  constexpr auto begin() const -> const_iterator;
+  constexpr auto end() const -> const_iterator;
+  constexpr auto cbegin() const -> const_iterator;
+  constexpr auto cend() const -> const_iterator;
+
+  auto rbegin() -> reverse_iterator;
+  auto rend() -> reverse_iterator;
+  constexpr auto rbegin() const -> const_reverse_iterator;
+  constexpr auto rend() const -> const_reverse_iterator;
+  constexpr auto crbegin() const -> const_reverse_iterator;
+  constexpr auto crend() const -> const_reverse_iterator;
+  /// @}
+
+  /// @name Element access methods
+  /// @{
+  auto operator[](size_type Offs) -> reference;
+  auto operator[](size_type Offs) const -> const_reference;
+
+  auto front() -> reference;
+  auto front() const -> const_reference;
+
+  auto back() -> reference;
+  auto back() const -> const_reference;
+
+  auto data() -> pointer;
+  constexpr auto data() const -> const_pointer;
+  /// @}
+
+  /// @name Container queries
+  /// @{
+  constexpr auto size() const -> size_type;
+  constexpr auto capacity() const -> size_type;
+  constexpr bool empty() const;
+  /// @}
+
+  /// @name Container content manipulation methods
+  /// @{
+  void resize(size_type NewSize);
+  void resize_for_overwrite( // NOLINT(readability-identifier-naming)
+      size_type NewSize);
+
+  void resize(size_type, ValueParamT Val);
+
+  template <typename... ArgsT>
+  void resize_emplace(size_type NewSize,
+                      ArgsT &&...Args); // NOLINT(readability-identifier-naming)
+
+  auto push_back(value_type &&Val)
+      -> reference; // NOLINT(readability-identifier-naming)
+  auto push_back(const_reference Val)
+      -> reference; // NOLINT(readability-identifier-naming)
+
+  template <typename... ArgsT>
+  auto emplace_back(ArgsT &&...Args)
+      -> reference; // NOLINT(readability-identifier-naming)
+
+  template <typename... ArgsT>
+  auto emplace(const_iterator Pos, ArgsT &&...Args) -> iterator;
+
+  auto append(size_type N, ValueParamT Val) -> iterator;
+
+  template <typename InputIt,
+            std::enable_if_t<is_convertible_input_iterator<InputIt, T>::value>
+                * = nullptr>
+  auto append(InputIt First, InputIt Last) -> iterator;
+
+  template <typename U,
+            std::enable_if<std::is_convertible<U, T>::value> * = nullptr>
+  auto append(std::initializer_list<U> IL) -> iterator;
+
+  template < // clang-format off
+    typename ContainerT,
+    std::enable_if_t<
+      is_forward_iterable_and_convertible<ContainerT, T>::value
+    > * = nullptr
+  > // clang-format on
+  auto append(ContainerT &&Container) -> iterator;
+
+  auto insert(const_iterator Pos, const_reference Val) -> iterator;
+  auto insert(const_iterator Pos, value_type &&Val) -> iterator;
+  auto insert(const_iterator Pos, size_type N, ValueParamT Val) -> iterator;
+
+  template <typename InputIt,
+            std::enable_if_t<is_convertible_input_iterator<InputIt, T>::value>
+                * = nullptr>
+  auto insert(const_iterator Pos, InputIt First, InputIt Last) -> iterator;
+
+  template < // clang-format off
+    typename ContainerT,
+    std::enable_if_t<
+      is_forward_iterable_and_convertible<ContainerT, T>::value
+    > * = nullptr
+  > // clang-format on
+  auto insert(const_iterator Pos, ContainerT &&Container) -> iterator;
+
+  void clear();
+
+  void pop_back();                   // NOLINT(readability-identifier-naming)
+  void pop_back_n(size_type N);      // NOLINT(readability-identifier-naming)
+  auto pop_back_val() -> value_type; // NOLINT(readability-identifier-naming)
+
+  auto erase(const_iterator Pos) -> iterator;
+  auto erase(const_iterator First, const_iterator Last) -> iterator;
+  /// @}
+
+  /// @name Comparison operators
+  /// @{
+  bool operator==(StaticVector const &RHS) const;
+  bool operator!=(StaticVector const &RHS) const;
+  bool operator<(StaticVector const &RHS) const;
+  bool operator>(StaticVector const &RHS) const;
+  bool operator<=(StaticVector const &RHS) const;
+  bool operator>=(StaticVector const &RHS) const;
+  /// @}
+
+  operator ArrayRef<value_type>() const { return {data(), size()}; }
+  operator MutableArrayRef<value_type>() { return {data(), size()}; }
+
+private:
+  using StorageT::setSize;
+
+  template <typename ArgT>
+  auto emplaceSingleArgImpl(const_iterator Pos, ArgT &&Args) -> iterator;
+
+  template <typename... ArgsT>
+  auto emplaceImpl(const_iterator Pos, ArgsT &&...Args) -> iterator;
+
+  template <size_t NArgs, typename... ArgsT>
+  friend class static_vector_detail::EmplaceImplSelector;
+
+  template <typename U, typename... ArgsT>
+  static void construct(U *Ptr, ArgsT &&...Args) {
+    ::new ((void *)Ptr) U(std::forward<ArgsT>(Args)...);
+  }
+
+  template <typename... ArgsT>
+  static void constructRange(iterator B, iterator E, ArgsT &&...Args) {
+    for (; B != E; ++B) {
+      construct(B, std::forward<ArgsT>(Args)...);
+    }
+  }
+
+  template <typename U> static void destroy(U *Ptr);
+
+  static void destroyRange(iterator B, iterator E);
+
+  template <typename... ArgsT>
+  static bool aliases(pointer B, pointer E, ArgsT &&...Args);
+};
+
+namespace static_vector_detail {
+
+template <typename T, bool = std::is_trivially_destructible<T>::value>
+class Destroy {
+public:
+  void operator()(T *P) const { P->~T(); }
+
+  void operator()(T *B, T *E) const {
+    for (auto *P = E - 1; P >= B; --P)
+      P->~T();
+  }
+};
+
+// Trivial specialization.
+template <typename T> class Destroy<T, true> {
+public:
+  void operator()(T *P) const {}
+  void operator()(T *B, T *E) const {}
+};
+
+template <typename T, typename ArgT>
+constexpr int aliasesSingle(T *B, T *E, bool &Result, ArgT &&Arg) {
+  return (Result |= std::addressof(Arg) >= B && std::addressof(Arg) <= E, 0);
+}
+
+template <typename... Tn> constexpr void eval(Tn &&...) {}
+
+// Emplace implementation selector template.
+//
+// Special case implementation to deal with aliased copy insertion if the size
+// of the parameter pack == 1.
+template <size_t NArgs, typename... ArgsT> class EmplaceImplSelector {
+public:
+  template <typename StaticVecT>
+  typename StaticVecT::iterator
+  operator()(StaticVecT &Vec, typename StaticVecT::const_iterator Pos,
+             ArgsT &&...Args) {
+    return Vec.emplaceImpl(Pos, std::forward<ArgsT>(Args)...);
+  }
+};
+
+template <typename... ArgsT> class EmplaceImplSelector<1, ArgsT...> {
+public:
+  template <typename StaticVecT>
+  typename StaticVecT::iterator
+  operator()(StaticVecT &Vec, typename StaticVecT::const_iterator Pos,
+             ArgsT &&...Args) {
+    return Vec.emplaceSingleArgImpl(Pos, std::forward<ArgsT>(Args)...);
+  }
+};
+
+template <typename... ArgsT>
+using GetEmplaceSelector = EmplaceImplSelector<sizeof...(ArgsT), ArgsT...>;
+
+} // namespace static_vector_detail
+
+///
+/// Destroy the object at the specified location.
+///
+/// This function will generate no code if `T` is trivially destructible.
+///
+/// @param Ptr  Pointer to the object to destroy.
+///
+template <typename T, size_t C>
+template <typename U>
+inline void StaticVector<T, C>::destroy(U *Ptr) {
+  static_vector_detail::Destroy<U>()(Ptr);
+}
+
+///
+/// Destroy elements in a specified range.
+///
+/// This function will generate no code if `T` is trivially destructible.
+///
+/// @param B  Beginning of the range of elements to destroy.
+/// @param E  End of the range of elements to destroy.
+///
+template <typename T, size_t C>
+inline void StaticVector<T, C>::destroyRange(iterator First, iterator Last) {
+  static_vector_detail::Destroy<T>()(First, Last);
+}
+
+///
+/// Determine whether any of the references in the parameter pack alias with the
+/// specified range.
+///
+/// @param B     Beginning of the range to check for aliasing
+/// @param E     End of the range to check for aliasing.
+/// @param Args  Parameter pack to check for aliasing range `[B,E)`.
+///
+/// @return `true` if any reference in the parameter pack aliases `[B,E)`;
+/// `false` otherwise.
+///
+template <typename T, size_t C>
+template <typename... ArgsT>
+inline bool StaticVector<T, C>::aliases(pointer B, pointer E, ArgsT &&...Args) {
+  bool Result = false;
+  // evaluation order does not matter, so use a dummy function.
+  static_vector_detail::eval(static_vector_detail::aliasesSingle(
+      B, E, Result, std::forward<ArgsT>(Args))...);
+  return Result;
+}
+
+///
+/// Constructor with initial size specifier.
+///
+/// @param N  Number of default-constructed elements to add during
+///  construction.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+inline StaticVector<T, C>::StaticVector(size_type N) : StorageT(N) {
+  constructRange(begin(), end());
+}
+
+///
+/// Constructor with initial size + value specifiers.
+///
+/// @param N    Number of elements to add during construction.
+/// @param Val  Value to copy while adding elements.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+inline StaticVector<T, C>::StaticVector(size_type N, ValueParamT Val)
+    : StorageT(N) {
+  std::uninitialized_fill_n(begin(), N, Val);
+}
+
+///
+/// Copy constructor.
+///
+///  Copy contents of another `StaticVector`.
+///
+/// @param Other  `StaticVector` object to copy.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+inline StaticVector<T, C>::StaticVector(StaticVector const &Other)
+    : StorageT(Other.size()) {
+  std::uninitialized_copy(Other.begin(), Other.end(), begin());
+}
+
+///
+/// Move constructor.
+///
+///  Move all the elements from another `StaticVector` into this one.
+///
+/// @param Other  `StaticVector` object to copy.
+///
+///  Notice that a move construction is not as fast as if the container were
+///  heap allocated.  We do need to visit all elements in `Other`.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+inline StaticVector<T, C>::StaticVector(StaticVector &&Other)
+    : StorageT(Other.size()) {
+  auto *First = Other.begin();
+  auto *Last = Other.end();
+  std::uninitialized_copy(std::make_move_iterator(First),
+                          std::make_move_iterator(Last), begin());
+}
+
+///
+/// Copy range constructor
+///
+///  Copy all the elements in the range `[first, Last).
+///
+/// @param First  First element to copy.
+/// @param Last   One-past the last element to copy.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+template <typename InputIt,
+          std::enable_if_t<is_convertible_input_iterator<InputIt, T>::value> *>
+inline StaticVector<T, C>::StaticVector(InputIt First, InputIt Last)
+    : StorageT(static_cast<size_type>(std::distance(First, Last))) {
+  std::uninitialized_copy(First, Last, begin());
+}
+
+///
+/// Copy from an unknown container type which is input iterable.
+///
+/// @param Container  The container to copy from.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+template < // clang-format off
+  typename ContainerT,
+  std::enable_if_t<
+    llvm::conjunction<
+      negation<std::is_same<StaticVector<T, C>,ContainerT>>,
+      is_forward_iterable_and_convertible<ContainerT, T>
+    >::value
+  > *
+> // clang-format on
+inline StaticVector<T, C>::StaticVector(ContainerT &&Container)
+    : StaticVector(adl_begin(Container), adl_end(Container)) {}
+
+///
+/// Initializer list constructor.
+///
+///  Initialize the `StaticVector` to contain copies of elements in the
+///  specified `initializer_list`.
+///
+/// @param IL  Initializer list to copy elements from.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+template <typename U, std::enable_if_t<std::is_constructible<T, U>::value> *>
+inline StaticVector<T, C>::StaticVector(std::initializer_list<U> IL)
+    : StaticVector(IL.begin(), IL.end()) {}
+
+///
+/// Destructor.
+///
+///  Destroy all currently valid elements in the container.  This code will
+///  evaluate to nothing if `ValueType` is trivially destructrible.
+///
+/// @note Complexity = O(n) if `T` is non-trivially destructible; O(1)
+/// otherwise.
+///
+template <typename T, size_t C> inline StaticVector<T, C>::~StaticVector() {
+  destroyRange(begin(), end());
+}
+
+///
+/// Copy assignment operator.
+///
+///  Clear current contents and then copy elements from another `StaticVector`.
+///
+/// @param Other  `StaticVector` to copy contents from.
+///
+/// @return A reference to this `StaticVector`.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::operator=(StaticVector const &Other)
+    -> StaticVector & {
+  assign(Other.begin(), Other.end());
+  return *this;
+}
+
+///
+/// Move assignment operator.
+///
+///  Clear current contents and then move elements from another `StaticVector`.
+///
+/// @param Other  `StaticVector` to move contents from.
+///
+///  Notice that a move assignment is not as fast as if the container were heap
+///  allocated.  We do need to visit all elements in `Other`.
+///
+/// @return A reference to this `StaticVector`.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::operator=(StaticVector &&Other)
+    -> StaticVector & {
+
+  size_type OtherSize = Other.size();
+  size_type ThisSize = size();
+
+  if (ThisSize >= OtherSize) {
+    // assign common elements.
+    iterator NewEnd = begin();
+    if (OtherSize)
+      NewEnd = std::move(Other.begin(), Other.end(), NewEnd);
+
+    // Destroy extra elements.
+    destroyRange(NewEnd, end());
+  } else {
+    // Move assign over current elements.
+    if (ThisSize) {
+      std::move(Other.begin(), Other.begin() + ThisSize, begin());
+    }
+    // Move construct the new elements in place.
+    std::uninitialized_copy(std::make_move_iterator(Other.begin() + ThisSize),
+                            std::make_move_iterator(Other.end()),
+                            begin() + ThisSize);
+  }
+  setSize(OtherSize);
+  return *this;
+}
+
+///
+/// Container assignment operator.
+///
+/// Clear current contents and then copy elements from another container.
+///
+/// This operator is only enabled when the `ContainerT` is forward iterable and
+/// the type obtained from dereferencing the iterator is convertible to `T`.
+///
+/// @return A reference to this `StaticVector`.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+template < // clang-format off
+  typename ContainerT,
+  std::enable_if_t<
+    llvm::conjunction<
+      negation<std::is_same<StaticVector<T, C>, ContainerT>>,
+      is_forward_iterable_and_convertible<ContainerT, T>
+    >::value
+  > *
+> // clang-format on
+inline auto StaticVector<T, C>::operator=(ContainerT &&Container)
+    -> StaticVector & {
+  assign(Container);
+  return *this;
+}
+
+///
+/// Assign contents between specified input iterators.
+///
+/// @param First  iterator referring to the first element to copy.
+/// @param Last   iterator referring to one-past the last element to copy.
+///
+/// @return A reference to this `StaticVector`.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+template <typename InputIt,
+          std::enable_if_t<is_convertible_input_iterator<InputIt, T>::value> *>
+inline auto StaticVector<T, C>::assign(InputIt First, InputIt Last)
+    -> StaticVector & {
+  clear();
+  append(First, Last);
+  return *this;
+}
+
+///
+///  Assign contents to a specified number of values.
+///
+///  Clear current contents and then assign `N` elements to `Val` at the front
+///  of the container.
+///
+/// @param N    Number of elements to create during the assignment.
+/// @param Val  Value to assign to newly created elements.
+///
+/// @return A reference to this `StaticVector`.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::assign(size_type N, ValueParamT Val)
+    -> StaticVector & {
+  clear();
+  append(N, Val);
+  return *this;
+}
+
+///
+/// Copy assign from a std::initializer_list which holds elements of a type
+/// which is convertible to `T`.
+///
+/// @param IL  `std::initializer_list` to copy assign from.
+///
+/// @return A reference to this `StaticVector`.
+///
+template <typename T, size_t C>
+template <typename U, std::enable_if_t<std::is_convertible<U, T>::value> *>
+inline auto StaticVector<T, C>::assign(std::initializer_list<U> IL)
+    -> StaticVector & {
+  return assign(IL.begin(), IL.end());
+}
+
+///
+/// Copy assign from an arbitrary container which holds elements of a type which
+/// is convertible to `T`.
+///
+/// @param Container  Reference to the container to copy assign from.
+///
+/// @return A reference to this `StaticVector`.
+///
+template <typename T, size_t C>
+template < // clang-format off
+  typename ContainerT,
+  std::enable_if_t<
+    is_forward_iterable_and_convertible<ContainerT, T>::value
+  > *
+> // clang-format on
+inline auto StaticVector<T, C>::assign(ContainerT &&Container)
+    -> StaticVector & {
+  return assign(adl_begin(Container), adl_end(Container));
+}
+
+///
+/// Access a specified element in the `StaticVector`.
+///
+///  An assertion will trigger when specified index is out of bounds.
+///
+/// @param Offs  Index of the element to access.
+///
+/// @return A reference to the element at the specified index.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::operator[](size_type Offs) -> reference {
+  assert(Offs < size());
+  return data()[Offs];
+}
+
+///
+/// Access a specified element in the const-qualified `StaticVector`.
+///
+///  An assertion will trigger when specified index is out of bounds.
+///
+/// @param Offs  Index of the element to access.
+///
+/// @return A const-qualified reference to the element at the specified index.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::operator[](size_type Offs) const
+    -> const_reference {
+  assert(Offs < size());
+  return data()[Offs];
+}
+
+///
+/// Access the first element in the `StaticVector`.
+///
+///  An assertion will trigger if the container is `Empty`.
+///
+/// @return A reference to the first element in the `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::front() -> reference {
+  return operator[](0);
+}
+
+///
+/// Access the first element in the const-qualified `StaticVector`.
+///
+///  An assertion will trigger if the container is `Empty`.
+///
+/// @return A const-qualified reference to the first element in the
+///  `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::front() const -> const_reference {
+  return operator[](0);
+}
+
+///
+/// Access the last element in the `StaticVector`.
+///
+///  An assertion will trigger if the container is `Empty`.
+///
+/// @return A reference to the last element in the `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::back() -> reference {
+  return operator[](size() - 1);
+}
+
+///
+/// Access the last element in the const-qualified `StaticVector`.
+///
+///  An assertion will trigger if the container is `Empty`.
+///
+/// @return A const-qualified reference to the last element in the
+///  `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::back() const -> const_reference {
+  return operator[](size() - 1);
+}
+
+///
+/// Return a pointer to the data buffer.
+///
+///  This method is provided to allow interoperation with C-APIs.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::data() -> pointer {
+  return StorageT::data();
+}
+
+///
+/// Return a const-qualified pointer to the data buffer.
+///
+///  This method is provided to allow interoperation with C-APIs.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+constexpr auto StaticVector<T, C>::data() const -> const_pointer {
+  return StorageT::data();
+}
+
+///
+/// Report the number of elements that can be accommodated by the storage.
+///
+/// @return The maximum number of elements the container can store.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+constexpr auto StaticVector<T, C>::capacity() const -> size_type {
+  return StorageT::capacity();
+}
+
+///
+/// Report the current number of valid elements in the `StaticVector`.
+///
+/// @return The number of elements currently contained by the `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+constexpr auto StaticVector<T, C>::size() const -> size_type {
+  return StorageT::size();
+}
+
+///
+/// Report whether the `StaticVector` contains no elements.
+///
+/// @return `true` if no elements are currently inserted into the container;
+///  `false` otherwise.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+constexpr bool StaticVector<T, C>::empty() const {
+  return StorageT::rawSize() == 0;
+}
+
+///
+/// Return a forward iterator corresponding to the front of the
+///  `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::begin() -> iterator {
+  return data();
+}
+
+///
+/// Return a forward iterator corresponding to one-past the last valid
+///  element in the `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::end() -> iterator {
+  return data() + size();
+}
+
+///
+/// Return a forward const-iterator corresponding to the front of the
+///  `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+constexpr auto StaticVector<T, C>::begin() const -> const_iterator {
+  return data();
+}
+
+///
+/// Return a forward constiterator corresponding to one-past the
+///  last valid element in the `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+constexpr auto StaticVector<T, C>::end() const -> const_iterator {
+  return data() + size();
+}
+
+///
+/// Return a forward const-iterator corresponding to the front of the
+///  `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+constexpr auto StaticVector<T, C>::cbegin() const -> const_iterator {
+  return begin();
+}
+
+///
+/// Return a forward constiterator corresponding to one-past the
+///  last valid element in the `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+constexpr auto StaticVector<T, C>::cend() const -> const_iterator {
+  return end();
+}
+
+///
+/// Return a reverse iterator corresponding to the back of the
+///  `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::rbegin() -> reverse_iterator {
+  return reverse_iterator(end());
+}
+
+///
+/// Return a reverse iterator corresponding to one-before the first
+///  valid element in the `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::rend() -> reverse_iterator {
+  return reverse_iterator(begin());
+}
+
+///
+/// Return a reverse const-iterator corresponding to the back of the
+///  `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+constexpr auto StaticVector<T, C>::rbegin() const -> const_reverse_iterator {
+  return const_reverse_iterator(end());
+}
+
+///
+/// Return a reverse const-iterator corresponding to one-before the
+///  first valid element in the `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+constexpr auto StaticVector<T, C>::rend() const -> const_reverse_iterator {
+  return const_reverse_iterator(begin());
+}
+
+///
+/// Return a reverse const-iterator corresponding to the back of the
+///  `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+constexpr auto StaticVector<T, C>::crbegin() const -> const_reverse_iterator {
+  return rbegin();
+}
+
+///
+/// Return a reverse const-iterator corresponding to one-before the
+///  first valid element in the `StaticVector`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+constexpr auto StaticVector<T, C>::crend() const -> const_reverse_iterator {
+  return rend();
+}
+
+///
+/// Resize the conainer to a specified size; emplace newly created
+///  elements (if any).
+///
+///  If the specified number of elements is smaller than the current capacity,
+///  then elements at the back are destroyed (if applicable) and the container's
+///  size is updated; no values are written / copied.
+///
+///  New members of the `StaticVector` are constructed via perfect-forwarding
+///  specified arguments in the `Args` parameter pack.
+///
+/// @param NewSize  New size of the `StaticVector`.
+/// @param Args     Parameter pack of constructor arguments to use while
+///                  constructing new elements (if any).
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+template <typename... ArgsT>
+inline void StaticVector<T, C>::resize_emplace(size_type NewSize,
+                                               ArgsT &&...Args) {
+  assert(NewSize <= capacity());
+
+  if (NewSize > size()) {
+    constructRange(end(), begin() + NewSize, std::forward<ArgsT>(Args)...);
+  } else {
+    destroyRange(begin() + NewSize, end());
+  }
+
+  setSize(NewSize);
+}
+
+///
+/// Resize the conainer to a specified size; default construct newly
+///  created elements (if any).
+///
+///  If the specified number of elements is smaller than the current capacity,
+///  then elements at the back are destroyed (if applicable) and the container's
+///  size is updated; no values are written / copied.
+///
+///  New members of the `StaticVector` are default constructed.
+///
+/// @param NewSize  New size of the `StaticVector`.
+///
+/// @note Complexity = O(m); where 'm' is the number of elements destroyed
+///  or constructed.
+///
+template <typename T, size_t C>
+inline void StaticVector<T, C>::resize(size_type NewSize) {
+  resize_emplace(NewSize);
+}
+
+///
+/// Resize the conainer to a specified size; copy construct newly
+///  created elements from specified value.
+///
+///  If the specified number of elements is smaller than the current capacity,
+///  then elements at the back are destroyed (if applicable) and the container's
+///  size is updated; no values are written / copied.
+///
+///  New members of the `StaticVector` are copy constructed.
+///
+/// @param NewSize  New size of the `StaticVector`.
+/// @param Val      Value to copy construct into new elements.
+///
+/// @note Complexity = O(m); where 'm' is the number of elements destroyed
+///  or constructed.
+///
+template <typename T, size_t C>
+inline void StaticVector<T, C>::resize(size_type NewSize, ValueParamT Val) {
+  resize_emplace(NewSize, Val);
+}
+
+///
+/// Resize the buffer, but POD data types will be left uninitialized.
+///
+/// @param NewSize  New number of elements to size of the storage buffer.
+///
+/// @note Complexity = O(m); where 'm' is the number of elements destroyed or
+///  constructed.
+template <typename T, size_t C>
+inline void StaticVector<T, C>::resize_for_overwrite(size_type NewSize) {
+
+  if (NewSize < size()) {
+    destroyRange(data() + NewSize, data() + size());
+    setSize(NewSize);
+  } else if (NewSize > size()) {
+    assert(NewSize <= capacity());
+
+    for (auto I = end(), E = begin() + NewSize; I != E; ++I)
+      ::new (I) value_type;
+
+    setSize(NewSize);
+  }
+}
+
+///
+/// Insert a new element at the back, constructed with specified
+///  arguments (saves creation of a temporary).
+///
+/// @param Args  Parameter pack of arguments to pass to the constructor of
+///               the new element.
+///
+/// @return A `reference` to the newly inserted object.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+template <typename... ArgsT>
+inline auto StaticVector<T, C>::emplace_back(ArgsT &&...Args) -> reference {
+  assert(size() < capacity());
+  construct(data() + size(), std::forward<ArgsT>(Args)...);
+
+  setSize(size() + 1);
+  return back();
+}
+
+///
+/// Move a new element to the back.
+///
+/// @param Val  Object to move into the new back element.
+///
+/// @return A `reference` to the newly inserted object.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::push_back(value_type &&Val) -> reference {
+  return emplace_back(std::move(Val));
+}
+
+///
+/// Copy a new element at the back.
+///
+/// @param Val  Object to copy to the new back element.
+///
+/// @return A `reference` to the newly inserted object.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::push_back(const_reference Val) -> reference {
+  return emplace_back(Val);
+}
+
+///
+///  Insert an object constructed via specified arguments into this
+///  `StaticVector` before a specified position.
+///
+///  If `Pos == end()`, then the new members are inserted at the back of
+///  the `StaticVector`.
+///
+/// @param Pos   Position in the current `StaticVector` to insert before.
+/// @param Args  Parameter pack of constructor args to pass to the newly
+///               create element.
+///
+/// @return An `iterator` which represents the newly inserted element.
+///
+/// @note Complexity = O(m); where `m` is the number of items between
+///  `Pos` and end().
+///
+template <typename T, size_t C>
+template <typename... ArgsT>
+auto StaticVector<T, C>::emplace(const_iterator Pos, ArgsT &&...Args)
+    -> iterator {
+  using SelectorT = static_vector_detail::GetEmplaceSelector<ArgsT...>;
+  return SelectorT()(*this, Pos, std::forward<ArgsT>(Args)...);
+}
+
+///
+/// General implementation of emplace used for most parameter pack sizes.
+///
+/// @param Pos   Position in `this` to insert before.
+/// @param Args  Parameter pack used to construct the new element in place.
+///
+/// @return An `iterator` which represents the newly inserted element.
+///
+template <typename T, size_t C>
+template <typename... ArgsT>
+auto StaticVector<T, C>::emplaceImpl(const_iterator Pos, ArgsT &&...Args)
+    -> iterator {
+  assert(size() < capacity());
+
+  size_type Idx = std::distance(cbegin(), Pos);
+  pointer PIns = data() + Idx;
+  std::aligned_storage_t<sizeof(value_type), alignof(value_type)> AliasTmp;
+
+  bool Aliases = aliases(PIns, end(), std::forward<ArgsT>(Args)...);
+
+  if (Aliases) {
+    // One of the constructor args aliases the buffer we're about to move.
+    // Construct a temporary and then move that into the final position after
+    // moving existing elements up.
+    construct(reinterpret_cast<pointer>(std::addressof(AliasTmp)),
+              std::forward<ArgsT>(Args)...);
+  }
+
+  if (Idx != size()) {
+    construct(this->end(), std::move(back()));
+    std::move_backward(PIns, end() - 1, end());
+    destroy(PIns);
+  }
+
+  if (Aliases) {
+    construct(PIns, std::move(reinterpret_cast<reference>(AliasTmp)));
+    destroy((pointer)std::addressof(AliasTmp));
+  } else {
+    construct(PIns, std::forward<ArgsT>(Args)...);
+  }
+
+  setSize(size() + 1);
+
+  return PIns;
+}
+
+///
+/// Specialized implementation of emplace used for size==1 parameter packs.
+///
+///  This specialized implementation allows us to more efficiently handle the
+///  case where the parameter aliases with the back range of the `StaticVector`
+///  which will be moved upwards during the insertion.
+///
+/// @param Pos  Position in `this` to insert before.
+/// @param Arg  Parameter used to construct the new element in place.
+///
+/// @return An `iterator` which represents the newly inserted element.
+///
+template <typename T, size_t C>
+template <typename ArgT>
+auto StaticVector<T, C>::emplaceSingleArgImpl(const_iterator Pos, ArgT &&Arg)
+    -> iterator {
+  assert(size() < capacity());
+
+  size_type Idx = std::distance(cbegin(), Pos);
+  pointer PIns = data() + Idx;
+  auto *ConstructPtr = std::addressof(Arg);
+
+  bool Aliases = aliases(PIns, end(), std::forward<ArgT>(Arg));
+
+  if (Idx != size()) {
+    construct(this->end(), std::move(back()));
+    std::move_backward(PIns, end() - 1, end());
+    destroy(PIns);
+  }
+
+  if (Aliases) {
+    // Adjust the pointer... 'ConstructPtr' might not be a pointer to a
+    // `value_type`.  It could be a member of a `value_type` which is
+    // convertible to a `value_type`.  Therefore, we need to cast to char and
+    // adjust by sizeof(value_type) to ensure we're pointing at the right thing.
+    char *AdjustPtr = const_cast<char *>((char const *)ConstructPtr);
+    AdjustPtr += sizeof(value_type);
+    ConstructPtr = (decltype(ConstructPtr))(AdjustPtr);
+  }
+
+  construct(PIns, std::forward<ArgT>(*ConstructPtr));
+
+  setSize(size() + 1);
+
+  return PIns;
+}
+
+///
+///  Insert a new elements by copy before the specified position.
+///
+///  If `Pos == end()`, the new member is appended.
+///
+/// @param Pos  Position in the `StaticVector` to insert before.
+/// @param Val  Object to copy-construct into new elements inserted.
+///
+/// @return `Pos` if `n == 0`; otherwise an `iterator` which represents
+///  the first newly inserted item.
+///
+/// @note Complexity = O(m + N); where `m` is `std::distance(Pos, end())`.
+///
+template <typename T, size_t C>
+auto StaticVector<T, C>::insert(const_iterator Pos, const_reference Val)
+    -> iterator {
+  return emplace(Pos, Val);
+}
+
+///
+///  Insert a new elements via move construction before the specified position.
+///
+///  If `Pos == end()`, the new member is appended.
+///
+/// @param Pos  Position in the `StaticVector` to insert before.
+/// @param Val  Object to copy-construct into new elements inserted.
+///
+/// @return `Pos` if `n == 0`; otherwise an `iterator` which represents
+///  the first newly inserted item.
+///
+/// @note Complexity = O(m + N); where `m` is `std::distance(Pos, end())`.
+///
+template <typename T, size_t C>
+auto StaticVector<T, C>::insert(const_iterator Pos, value_type &&Val)
+    -> iterator {
+  return emplace(Pos, std::move(Val));
+}
+
+///
+/// Insert `N` new elements before the specified position.
+///
+///  If `Pos == end()`, then the new members are inserted at the back
+///  of the `StaticVector`.
+///
+/// @param Pos  Position in the `StaticVector` to insert before.
+/// @param N    Number of elements to insert.
+/// @param Val  Object to copy-construct into new elements inserted.
+///
+/// @return `Pos` if `n == 0`; otherwise an `iterator` which represents
+///  the first newly inserted item.
+///
+/// @note Complexity = O(m + N); where `m` is `std::distance(Pos, end())`.
+///
+template <typename T, size_t C>
+auto StaticVector<T, C>::insert(const_iterator Pos, size_type N,
+                                ValueParamT Val) -> iterator {
+  assert(Pos >= cbegin());
+  assert(Pos <= cend());
+  assert(size() + N <= capacity());
+
+  iterator I = begin() + std::distance(cbegin(), Pos);
+  iterator OldEnd = end();
+
+  value_type const *CopyPtr = std::addressof(Val);
+
+  if (size_t(OldEnd - I) >= N) {
+    // If there are more elements between the insertion point and the end of the
+    // range than there are being inserted, we can use a simple approach to
+    // insertion.  Since we already reserved space, we know that this won't
+    // reallocate the vector.
+    append(std::make_move_iterator(OldEnd - N),
+           std::make_move_iterator(OldEnd));
+
+    // Copy the existing elements that get replaced.
+    std::move_backward(I, OldEnd - N, OldEnd);
+
+    // If we just moved the element we're inserting, be sure to update
+    // the reference (never happens if TakesParamByValue).
+    if (!TakesParamByValue && I <= CopyPtr && CopyPtr < OldEnd)
+      CopyPtr += N;
+
+    std::fill_n(I, N, *CopyPtr);
+  } else {
+    // Otherwise, we're inserting more elements than exist already, and we're
+    // not inserting at the end.
+
+    // Move over the elements that we're about to overwrite.
+    setSize(size() + N);
+    size_t NumOverwritten = OldEnd - I;
+
+    std::uninitialized_copy(std::make_move_iterator(I),
+                            std::make_move_iterator(OldEnd), end() - N);
+
+    // If we just moved the element we're inserting, be sure to update
+    // the reference (never happens if TakesParamByValue).
+    if (!TakesParamByValue && I <= CopyPtr && CopyPtr < end())
+      CopyPtr += N;
+
+    // Replace the overwritten part.
+    std::fill_n(I, NumOverwritten, *CopyPtr);
+
+    // Insert the non-overwritten middle part.
+    std::uninitialized_fill_n(OldEnd, N - NumOverwritten, *CopyPtr);
+  }
+
+  return I;
+}
+
+///
+/// Insert new elements from an iterator range.
+///
+///  Insert new vector members which are copies of values described by
+///  input iterator range `[First, Last)` before the specified position
+///  (`Pos`). If `Pos == end()`, then the new members are inserted at
+///  the back of the `StaticVector`.
+///
+/// @param Pos   Position in the `StaticVector` to insert before.
+/// @param First Input iterator referencing the first element to insert.
+/// @param Last  Input iterator referencing one-past the last element to insert.
+///
+/// @return `Pos` if `First == Last`; otherwise an `iterator` which
+///  represents the first newly inserted item.
+///
+/// @note Complexity = O(m + `std::distance(First, Last)`); where `m` is the
+///  number of items between `Pos` and `end()`.
+///
+template <typename T, size_t C>
+template <typename InputIt,
+          std::enable_if_t<is_convertible_input_iterator<InputIt, T>::value> *>
+auto StaticVector<T, C>::insert(const_iterator Pos, InputIt First, InputIt Last)
+    -> iterator {
+  iterator I = begin() + std::distance(cbegin(), Pos);
+  iterator OldEnd = end();
+
+  if (I == OldEnd) {
+    append(First, Last);
+  } else {
+
+    size_t N = std::distance(First, Last);
+    assert(size() + N <= capacity());
+
+    // If there are more elements between the insertion point and the end of the
+    // range than there are being inserted, we can use a simple approach to
+    // insertion.  Since we already reserved space, we know that this won't
+    // reallocate the vector.
+    if (size_t(OldEnd - I) >= N) {
+      append(std::make_move_iterator(end() - N),
+             std::make_move_iterator(end()));
+
+      // Copy the existing elements that get replaced.
+      std::move_backward(I, OldEnd - N, OldEnd);
+
+      std::copy(First, Last, I);
+    } else {
+      // Otherwise, we're inserting more elements than exist already, and we're
+      // not inserting at the end.
+
+      // Move over the elements that we're about to overwrite.
+      setSize(size() + N);
+      size_t NumOverwritten = OldEnd - I;
+      std::uninitialized_copy(std::make_move_iterator(I),
+                              std::make_move_iterator(OldEnd),
+                              end() - NumOverwritten);
+
+      // Replace the overwritten part.
+      for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
+        *J = *First;
+        ++J;
+        ++First;
+      }
+
+      // Insert the non-overwritten middle part.
+      std::uninitialized_copy(First, Last, OldEnd);
+    }
+  }
+  return I;
+}
+
+///
+///  Insert a copy of values in the specified container before the
+///  specified position.
+///
+/// @note Shortcut method for common call:
+///   `insert(Pos, container.begin(), container.end());`
+///
+/// @param Pos        Position in the `StaticVector` to insert before.
+/// @param Container  Container whose contents to insert before `Pos`.
+///
+/// @return `Pos` if `Container` is empty; otherwise an `iterator` which
+///  represents the first newly inserted item.
+///
+/// @note Complexity = O(m + n);
+///  where `m` is the number of items between `Pos` and `end()`.
+///
+template <typename T, size_t C>
+template < // clang-format off
+  typename ContainerT,
+  std::enable_if_t<
+    is_forward_iterable_and_convertible<ContainerT, T>::value
+  > *
+> // clang-format on
+inline auto StaticVector<T, C>::insert(const_iterator Pos,
+                                       ContainerT &&Container) -> iterator {
+  return insert(Pos, adl_begin(Container), adl_end(Container));
+}
+
+///
+/// Append `N` new elements before the specified position.
+///
+/// @param N    Number of elements to append.
+/// @param Val  Object to copy-construct into new elements inserted.
+///
+/// @return `Pos` if `n == 0`; otherwise an `iterator` which represents
+///  the first newly inserted item.
+///
+/// @note Complexity = O(N)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::append(size_type N, ValueParamT Val)
+    -> iterator {
+  auto I = end();
+  resize_emplace(size() + N, Val);
+  return I;
+}
+
+///
+/// Append copies of values in a range.
+///
+/// @param First  First position in the range to copy
+/// @param Last   One-past the last position to copy.
+///
+/// @note Complexity = O(std::distance(First, Last))
+///
+template <typename T, size_t C>
+template <typename InputIt,
+          std::enable_if_t<is_convertible_input_iterator<InputIt, T>::value> *>
+auto StaticVector<T, C>::append(InputIt First, InputIt Last) -> iterator {
+
+  size_type Count = std::distance(First, Last);
+  assert(Count + size() <= capacity());
+
+  auto *NewElemPos = end();
+  std::uninitialized_copy(First, Last, NewElemPos);
+  setSize(size() + Count);
+
+  return NewElemPos;
+}
+
+///
+/// Append copies of elements in a `std::initializer_list` holding a type which
+/// is convertible to `T`.
+///
+/// @param IL  initializer_list to append copies from.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+template <typename U, std::enable_if<std::is_convertible<U, T>::value> *>
+inline auto StaticVector<T, C>::append(std::initializer_list<U> IL)
+    -> iterator {
+  return append(IL.begin(), IL.end());
+}
+
+///
+/// Append copies of elements in an arbitrary container holding a type which is
+/// convertible to `T`.
+///
+/// @param Container  The container to append copies from.
+///
+/// @note Complexity = O(n)
+///
+// clang-format off
+template <typename T, size_t C>
+template <
+  typename ContainerT,
+  std::enable_if_t<
+    is_forward_iterable_and_convertible<ContainerT, T>::value
+  > *
+> // clang-format on
+inline auto StaticVector<T, C>::append(ContainerT &&Container) -> iterator {
+  return append(adl_begin(Container), adl_end(Container));
+}
+
+///
+/// Mark the current `StaticVector` as empty and destroy all elememts.
+///
+/// @note Complexity = O(1) if `T` is trivially destructible;
+///  O(n) otherwise.
+///
+template <typename T, size_t C> inline void StaticVector<T, C>::clear() {
+  destroyRange(begin(), end());
+  setSize(0);
+}
+
+///
+/// Decrease the size of the container by `1`, removing the last element.
+///
+/// Asserts if the container is `Empty()`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C> inline void StaticVector<T, C>::pop_back() {
+  assert(size() >= 1);
+  setSize(size() - 1);
+  destroy(end());
+}
+
+///
+/// Decrease the size of the container by `N`, removing the last elements.
+///
+/// Asserts if the container does not have `N` elements to remove.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+inline void StaticVector<T, C>::pop_back_n(size_type N) {
+  assert(size() >= N);
+  destroyRange(end() - N, end());
+  setSize(size() - N);
+}
+
+///
+/// Decrease the size of the container by `1`, removing the last element.
+///
+/// Asserts if the container is `empty()`.
+///
+/// @note Complexity = O(1)
+///
+template <typename T, size_t C>
+inline auto StaticVector<T, C>::pop_back_val() -> value_type {
+  auto OldBack = back();
+  pop_back();
+  return OldBack;
+}
+
+///
+/// Erase a single element at a specified position from the
+/// `StaticVector`.
+///
+/// If `Pos == end()`, then no member is removed.
+///
+/// @param Pos  Position of the element to erase from the `StaticVector`.
+///
+/// @return An `iterator` referring to the new location of the element that
+///  followed the erased element.  This is `end()` if the operation erased
+///  the last element.
+///
+/// @note Complexity = O(m); where `m` is the number of items between `Pos`
+///  and `end()`.
+///
+template <typename T, size_t C>
+auto StaticVector<T, C>::erase(const_iterator Pos) -> iterator {
+  assert(Pos >= cbegin());
+  assert(Pos <= cend());
+
+  auto I = const_cast<iterator>(Pos);
+  std::move(I + 1, end(), I);
+  pop_back();
+  return I;
+}
+
+///
+/// Erase a sequence of elements in the range `[First, Last)` from the
+///  `StaticVector`.
+///
+///  If `First == Last`, then no member is erased.
+///
+/// @param First  The first element in the `StaticVector` to erase.
+/// @param Last   One-past the last element in the `StaticVector` to erase.
+///
+/// @return An `iterator` referring to the new location of the element that
+///  followed the erased element(s).  This is `end()` if the operation
+///  erased the last element.
+///
+/// @note Complexity = O(m); where `m` is the number of items between `First`
+///  and `end()`.
+///
+template <typename T, size_t C>
+auto StaticVector<T, C>::erase(const_iterator First, const_iterator Last)
+    -> iterator {
+  assert(First <= Last);
+  assert(First >= cbegin());
+  assert(First < cend());
+  assert(Last >= cbegin());
+  assert(Last <= cend());
+
+  auto F = const_cast<iterator>(First);
+  auto L = const_cast<iterator>(Last);
+
+  iterator I = std::move(L, end(), F);
+  destroyRange(I, end());
+  setSize(std::distance(begin(), I));
+  return F;
+}
+
+///
+/// Compare two `StaticVector`s for equality.
+///
+/// @return `true` if the containers are equal in size and value; `false`
+///  otherwise.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+inline bool StaticVector<T, C>::operator==(StaticVector const &RHS) const {
+  return size() == RHS.size() &&
+         std::equal(begin(), end(), RHS.begin(), RHS.end());
+}
+
+///
+/// Compare two `StaticVector`s for inequality.
+///
+/// @return `false` if the containers are equal in size and value; `true`
+///  otherwise.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+inline bool StaticVector<T, C>::operator!=(StaticVector const &RHS) const {
+  return !operator==(RHS);
+}
+
+///
+/// Compare to another `StaticVector` for less-than relation using
+/// lexicographical comparison.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+inline bool StaticVector<T, C>::operator<(StaticVector const &RHS) const {
+  return std::lexicographical_compare(begin(), end(), RHS.begin(), RHS.end());
+}
+
+///
+/// Compare to another `StaticVector` for greater-than relation using
+/// lexicographical comparison.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+inline bool StaticVector<T, C>::operator>(StaticVector const &RHS) const {
+  return RHS.operator<(*this);
+}
+
+///
+/// Compare to another `StaticVector` for less-than or equal relation using
+/// lexicographical comparison.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+inline bool StaticVector<T, C>::operator<=(StaticVector const &RHS) const {
+  return !RHS.operator<(*this);
+}
+
+///
+/// Compare to another `StaticVector` for greater-than or equal
+/// relation using lexicographical comparison.
+///
+/// @note Complexity = O(n)
+///
+template <typename T, size_t C>
+inline bool StaticVector<T, C>::operator>=(StaticVector const &RHS) const {
+  return !operator<(RHS);
+}
+
+} // namespace llvm
+
+#endif // LLVM_ADT_STATICVECTOR_H

llvm/unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   SimpleIListTest.cpp
   SmallPtrSetTest.cpp
   SmallSetTest.cpp
   SmallStringTest.cpp
   SmallVectorTest.cpp
   SparseBitVectorTest.cpp
   SparseMultiSetTest.cpp
   SparseSetTest.cpp
+  StaticVectorTest.cpp
   StatisticTest.cpp
   StringExtrasTest.cpp
   StringMapTest.cpp
   StringRefTest.cpp
   StringSetTest.cpp
   StringSwitchTest.cpp
   TinyPtrVectorTest.cpp
   TripleTest.cpp

llvm/unittests/ADT/StaticVectorTest.cpp

+//===- llvm/unittest/ADT/StaticVectorTest.cpp -------------------*- C++ -*-===//
+//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/StaticVector.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/Support/Compiler.h"
+#include "gtest/gtest.h"
+#include <list>
+#include <stdarg.h>
+
+using namespace llvm;
+
+namespace {
+
+/// An llvm::ArrayRef derived class which is only forward iterable via adl begin
+/// and end functions.
+template <typename T> class ForceADL : private ArrayRef<T> {
+  using BaseT = ArrayRef<T>;
+
+public:
+  using BaseT::BaseT;
+  using iterator = typename BaseT::iterator;
+
+  friend iterator begin(ForceADL const &AR) {
+    return reinterpret_cast<BaseT const &>(AR).begin();
+  }
+
+  friend iterator end(ForceADL const &AR) {
+    return reinterpret_cast<BaseT const &>(AR).end();
+  }
+};
+
+/// A helper class that counts the total number of constructor and
+/// destructor calls.
+class Constructable {
+private:
+  static int numConstructorCalls;
+  static int numMoveConstructorCalls;
+  static int numCopyConstructorCalls;
+  static int numDestructorCalls;
+  static int numAssignmentCalls;
+  static int numMoveAssignmentCalls;
+  static int numCopyAssignmentCalls;
+
+  bool constructed;
+  int value;
+
+public:
+  Constructable() : constructed(true), value(0) { ++numConstructorCalls; }
+
+  Constructable(int val) : constructed(true), value(val) {
+    ++numConstructorCalls;
+  }
+
+  Constructable(const Constructable &src) : constructed(true) {
+    value = src.value;
+    ++numConstructorCalls;
+    ++numCopyConstructorCalls;
+  }
+
+  Constructable(Constructable &&src) : constructed(true) {
+    value = src.value;
+    src.value = 0;
+    ++numConstructorCalls;
+    ++numMoveConstructorCalls;
+  }
+
+  ~Constructable() {
+    EXPECT_TRUE(constructed);
+    ++numDestructorCalls;
+    constructed = false;
+  }
+
+  Constructable &operator=(const Constructable &src) {
+    EXPECT_TRUE(constructed);
+    value = src.value;
+    ++numAssignmentCalls;
+    ++numCopyAssignmentCalls;
+    return *this;
+  }
+
+  Constructable &operator=(Constructable &&src) {
+    EXPECT_TRUE(constructed);
+    value = src.value;
+    src.value = 0;
+    ++numAssignmentCalls;
+    ++numMoveAssignmentCalls;
+    return *this;
+  }
+
+  int getValue() const { return abs(value); }
+
+  static void reset() {
+    numConstructorCalls = 0;
+    numMoveConstructorCalls = 0;
+    numCopyConstructorCalls = 0;
+    numDestructorCalls = 0;
+    numAssignmentCalls = 0;
+    numMoveAssignmentCalls = 0;
+    numCopyAssignmentCalls = 0;
+  }
+
+  static int getNumConstructorCalls() { return numConstructorCalls; }
+
+  static int getNumMoveConstructorCalls() { return numMoveConstructorCalls; }
+
+  static int getNumCopyConstructorCalls() { return numCopyConstructorCalls; }
+
+  static int getNumDestructorCalls() { return numDestructorCalls; }
+
+  static int getNumAssignmentCalls() { return numAssignmentCalls; }
+
+  static int getNumMoveAssignmentCalls() { return numMoveAssignmentCalls; }
+
+  static int getNumCopyAssignmentCalls() { return numCopyAssignmentCalls; }
+
+  friend bool operator==(const Constructable &c0, const Constructable &c1) {
+    return c0.getValue() == c1.getValue();
+  }
+
+  friend bool LLVM_ATTRIBUTE_UNUSED operator!=(const Constructable &c0,
+                                               const Constructable &c1) {
+    return c0.getValue() != c1.getValue();
+  }
+};
+
+int Constructable::numConstructorCalls;
+int Constructable::numCopyConstructorCalls;
+int Constructable::numMoveConstructorCalls;
+int Constructable::numDestructorCalls;
+int Constructable::numAssignmentCalls;
+int Constructable::numCopyAssignmentCalls;
+int Constructable::numMoveAssignmentCalls;
+
+struct NonCopyable {
+  NonCopyable() {}
+  NonCopyable(NonCopyable &&) {}
+  NonCopyable &operator=(NonCopyable &&) { return *this; }
+
+private:
+  NonCopyable(const NonCopyable &) = delete;
+  NonCopyable &operator=(const NonCopyable &) = delete;
+};
+
+LLVM_ATTRIBUTE_USED void CompileTest() {
+  StaticVector<NonCopyable, 1> V;
+  V.resize(42);
+}
+
+class StaticVectorTestBase : public testing::Test {
+protected:
+  void SetUp() override { Constructable::reset(); }
+
+  template <typename VectorT> void assertEmpty(VectorT &v) {
+    // Size tests
+    EXPECT_EQ(0u, v.size());
+    EXPECT_TRUE(v.empty());
+
+    // Iterator tests
+    EXPECT_TRUE(v.begin() == v.end());
+  }
+
+  // Assert that v contains the specified values, in order.
+  template <typename VectorT>
+  void assertValuesInOrder(VectorT &v, size_t size, ...) {
+    EXPECT_EQ(size, v.size());
+
+    va_list ap;
+    va_start(ap, size);
+    for (size_t i = 0; i < size; ++i) {
+      int value = va_arg(ap, int);
+      EXPECT_EQ(value, v[i].getValue());
+    }
+
+    va_end(ap);
+  }
+
+  template <typename VectorT>
+  void assertValuesInOrder(VectorT &v, llvm::ArrayRef<int> AR) {
+    EXPECT_EQ(AR.size(), v.size());
+
+    auto I1 = AR.begin();
+    auto E1 = AR.end();
+
+    auto I2 = v.begin();
+    auto E2 = v.end();
+
+    for (; I1 != E1 && I2 != E2; ++I1, ++I2) {
+      auto Expected = *I1;
+      auto Value = I2->getValue();
+      EXPECT_EQ(Value, Expected);
+    }
+  }
+
+  // Generate a sequence of values to initialize the vector.
+  template <typename VectorT>
+  void makeSequence(VectorT &v, int start, int end) {
+    for (int i = start; i <= end; ++i) {
+      v.push_back(Constructable(i));
+    }
+  }
+};
+
+// Test fixture class
+template <typename VectorT>
+class StaticVectorTest : public StaticVectorTestBase {
+protected:
+  VectorT theVector;
+  VectorT otherVector;
+};
+
+typedef ::testing::Types<StaticVector<Constructable, 4>,
+                         StaticVector<Constructable, 6>,
+                         StaticVector<Constructable, 10>>
+    StaticVectorTestTypes;
+TYPED_TEST_SUITE(StaticVectorTest, StaticVectorTestTypes, );
+
+// Constructor test.
+TYPED_TEST(StaticVectorTest, ConstructorNonIterTest) {
+  SCOPED_TRACE("ConstructorTest");
+  this->theVector = StaticVector<Constructable, 2>(2, 2);
+  this->assertValuesInOrder(this->theVector, 2u, 2, 2);
+}
+
+// Constructor test.
+TYPED_TEST(StaticVectorTest, ConstructorIterTest) {
+  SCOPED_TRACE("ConstructorTest");
+  int arr[] = {1, 2, 3};
+  this->theVector =
+      StaticVector<Constructable, 4>(std::begin(arr), std::end(arr));
+  this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3);
+}
+
+// New vector test.
+TYPED_TEST(StaticVectorTest, EmptyVectorTest) {
+  SCOPED_TRACE("EmptyVectorTest");
+  this->assertEmpty(this->theVector);
+  EXPECT_TRUE(this->theVector.rbegin() == this->theVector.rend());
+  EXPECT_EQ(0, Constructable::getNumConstructorCalls());
+  EXPECT_EQ(0, Constructable::getNumDestructorCalls());
+}
+
+// Simple insertions and deletions.
+TYPED_TEST(StaticVectorTest, PushPopTest) {
+  SCOPED_TRACE("PushPopTest");
+
+  // Track whether the vector will potentially have to grow.
+  bool const RequiresGrowth = this->theVector.capacity() < 3;
+  if (RequiresGrowth)
+    return;
+
+  // Push an element
+  this->theVector.emplace_back(1);
+
+  EXPECT_EQ(1, Constructable::getNumConstructorCalls());
+
+  // Size tests
+  this->assertValuesInOrder(this->theVector, 1u, 1);
+  EXPECT_FALSE(this->theVector.begin() == this->theVector.end());
+  EXPECT_FALSE(this->theVector.empty());
+
+  // Push another element
+  this->theVector.push_back(Constructable(2));
+  this->assertValuesInOrder(this->theVector, 2u, 1, 2);
+
+  // Insert at beginning. Reserve space to avoid reference invalidation from
+  // this->theVector[1].
+  this->theVector.insert(this->theVector.begin(), this->theVector[1]);
+  this->assertValuesInOrder(this->theVector, 3u, 2, 1, 2);
+
+  // Pop one element
+  this->theVector.pop_back();
+  this->assertValuesInOrder(this->theVector, 2u, 2, 1);
+
+  // Pop remaining elements
+  this->theVector.pop_back_n(2);
+  this->assertEmpty(this->theVector);
+
+  // Check number of constructor calls. Should be 2 for each list element,
+  // one for the argument to push_back, one for the argument to insert,
+  // and one for the list element itself.
+  if (!RequiresGrowth) {
+    EXPECT_EQ(5, Constructable::getNumConstructorCalls());
+    EXPECT_EQ(5, Constructable::getNumDestructorCalls());
+  } else {
+    // If we had to grow the vector, these only have a lower bound, but should
+    // always be equal.
+    EXPECT_LE(5, Constructable::getNumConstructorCalls());
+    EXPECT_EQ(Constructable::getNumConstructorCalls(),
+              Constructable::getNumDestructorCalls());
+  }
+}
+
+// Clear test.
+TYPED_TEST(StaticVectorTest, ClearTest) {
+  SCOPED_TRACE("ClearTest");
+
+  this->makeSequence(this->theVector, 1, 2);
+  this->theVector.clear();
+
+  this->assertEmpty(this->theVector);
+  EXPECT_EQ(4, Constructable::getNumConstructorCalls());
+  EXPECT_EQ(4, Constructable::getNumDestructorCalls());
+}
+
+// Resize smaller test.
+TYPED_TEST(StaticVectorTest, ResizeShrinkTest) {
+  SCOPED_TRACE("ResizeShrinkTest");
+
+  this->makeSequence(this->theVector, 1, 3);
+  this->theVector.resize(1);
+
+  this->assertValuesInOrder(this->theVector, 1u, 1);
+  EXPECT_EQ(6, Constructable::getNumConstructorCalls());
+  EXPECT_EQ(5, Constructable::getNumDestructorCalls());
+}
+
+// Resize bigger test.
+TYPED_TEST(StaticVectorTest, ResizeGrowTest) {
+  SCOPED_TRACE("ResizeGrowTest");
+
+  this->theVector.resize(2);
+
+  EXPECT_EQ(2, Constructable::getNumConstructorCalls());
+  EXPECT_EQ(0, Constructable::getNumDestructorCalls());
+  EXPECT_EQ(2u, this->theVector.size());
+}
+
+TYPED_TEST(StaticVectorTest, ResizeWithElementsTest) {
+  this->theVector.resize(2);
+
+  Constructable::reset();
+
+  this->theVector.resize(4);
+
+  size_t Ctors = Constructable::getNumConstructorCalls();
+  EXPECT_TRUE(Ctors == 2 || Ctors == 4);
+  size_t MoveCtors = Constructable::getNumMoveConstructorCalls();
+  EXPECT_TRUE(MoveCtors == 0 || MoveCtors == 2);
+  size_t Dtors = Constructable::getNumDestructorCalls();
+  EXPECT_TRUE(Dtors == 0 || Dtors == 2);
+}
+
+// Resize with fill value.
+TYPED_TEST(StaticVectorTest, ResizeFillTest) {
+  SCOPED_TRACE("ResizeFillTest");
+
+  this->theVector.resize(3, Constructable(77));
+  this->assertValuesInOrder(this->theVector, 3u, 77, 77, 77);
+}
+
+TEST(StaticVectorTest, ResizeForOverwrite) {
+  // Inline storage.
+  StaticVector<unsigned, 2> V;
+  V.push_back(5U);
+  V.pop_back();
+  V.resize_for_overwrite(V.size() + 1U);
+  EXPECT_EQ(5U, V.back());
+  V.pop_back();
+  V.resize(V.size() + 1);
+  EXPECT_EQ(0U, V.back());
+}
+
+// Iteration tests.
+TYPED_TEST(StaticVectorTest, IterationTest) {
+  this->makeSequence(this->theVector, 1, 2);
+
+  // Forward Iteration
+  typename TypeParam::iterator it = this->theVector.begin();
+  EXPECT_TRUE(*it == this->theVector.front());
+  EXPECT_TRUE(*it == this->theVector[0]);
+  EXPECT_EQ(1, it->getValue());
+  ++it;
+  EXPECT_TRUE(*it == this->theVector[1]);
+  EXPECT_TRUE(*it == this->theVector.back());
+  EXPECT_EQ(2, it->getValue());
+  ++it;
+  EXPECT_TRUE(it == this->theVector.end());
+  --it;
+  EXPECT_TRUE(*it == this->theVector[1]);
+  EXPECT_EQ(2, it->getValue());
+  --it;
+  EXPECT_TRUE(*it == this->theVector[0]);
+  EXPECT_EQ(1, it->getValue());
+
+  // Reverse Iteration
+  typename TypeParam::reverse_iterator rit = this->theVector.rbegin();
+  EXPECT_TRUE(*rit == this->theVector[1]);
+  EXPECT_EQ(2, rit->getValue());
+  ++rit;
+  EXPECT_TRUE(*rit == this->theVector[0]);
+  EXPECT_EQ(1, rit->getValue());
+  ++rit;
+  EXPECT_TRUE(rit == this->theVector.rend());
+  --rit;
+  EXPECT_TRUE(*rit == this->theVector[0]);
+  EXPECT_EQ(1, rit->getValue());
+  --rit;
+  EXPECT_TRUE(*rit == this->theVector[1]);
+  EXPECT_EQ(2, rit->getValue());
+}
+
+// Swap test.
+TYPED_TEST(StaticVectorTest, SwapTest) {
+  SCOPED_TRACE("SwapTest");
+
+  this->makeSequence(this->theVector, 1, 2);
+  std::swap(this->theVector, this->otherVector);
+
+  this->assertEmpty(this->theVector);
+  this->assertValuesInOrder(this->otherVector, 2u, 1, 2);
+}
+
+// Append test
+TYPED_TEST(StaticVectorTest, AppendTest) {
+  SCOPED_TRACE("AppendTest");
+
+  this->makeSequence(this->otherVector, 2, 3);
+
+  this->theVector.push_back(Constructable(1));
+  this->theVector.append(this->otherVector.begin(), this->otherVector.end());
+
+  this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3);
+}
+
+// Append repeated test
+TYPED_TEST(StaticVectorTest, AppendRepeatedTest) {
+  SCOPED_TRACE("AppendRepeatedTest");
+
+  this->theVector.push_back(Constructable(1));
+  this->theVector.append(2, Constructable(77));
+  this->assertValuesInOrder(this->theVector, 3u, 1, 77, 77);
+}
+
+// Append test
+TYPED_TEST(StaticVectorTest, AppendNonIterTest) {
+  SCOPED_TRACE("AppendRepeatedTest");
+
+  this->theVector.push_back(Constructable(1));
+  this->theVector.append(2, 7);
+  this->assertValuesInOrder(this->theVector, 3u, 1, 7, 7);
+}
+
+struct output_iterator {
+  typedef std::output_iterator_tag iterator_category;
+  typedef int value_type;
+  typedef int difference_type;
+  typedef value_type *pointer;
+  typedef value_type &reference;
+  operator int() { return 2; }
+  operator Constructable() { return 7; }
+};
+
+TYPED_TEST(StaticVectorTest, AppendRepeatedNonForwardIterator) {
+  SCOPED_TRACE("AppendRepeatedTest");
+
+  this->theVector.push_back(Constructable(1));
+  this->theVector.append(output_iterator(), output_iterator());
+  this->assertValuesInOrder(this->theVector, 3u, 1, 7, 7);
+}
+
+TYPED_TEST(StaticVectorTest, AppendStaticVector) {
+  SCOPED_TRACE("AppendStaticVector");
+
+  StaticVector<Constructable, 3> otherVector = {7, 7};
+  this->theVector.push_back(Constructable(1));
+  this->theVector.append(otherVector);
+  this->assertValuesInOrder(this->theVector, 3u, 1, 7, 7);
+}
+
+TYPED_TEST(StaticVectorTest, AppendArrayRefTest) {
+  SCOPED_TRACE("AppendArrayRefTest");
+  auto IL = {1, 2, 3};
+  ArrayRef<int> AR(IL);
+  this->theVector.append(AR);
+  this->assertValuesInOrder(this->theVector, IL);
+}
+
+TYPED_TEST(StaticVectorTest, AppendInitializerListTest) {
+  SCOPED_TRACE("AppendInitializerListTest");
+  auto IL = {1, 2, 3};
+  this->theVector.append(IL);
+  this->assertValuesInOrder(this->theVector, IL);
+}
+
+TYPED_TEST(StaticVectorTest, AppendContainerADL) {
+  SCOPED_TRACE("AppendContainerADL");
+  int iarr[]{1, 2, 3};
+  this->theVector.append(ForceADL<int>(iarr));
+  this->assertValuesInOrder(this->theVector, {1, 2, 3});
+}
+
+TYPED_TEST(StaticVectorTest, AppendRangeTest) {
+  SCOPED_TRACE("AppendRangeTest");
+  int iarr[]{1, 2, 3};
+  this->theVector.append(make_range(std::begin(iarr), std::end(iarr)));
+  this->assertValuesInOrder(this->theVector, {1, 2, 3});
+}
+
+TYPED_TEST(StaticVectorTest, AppendCArrayTest) {
+  SCOPED_TRACE("AppendCArrayTest");
+  const int iarr[]{1, 2, 3};
+  this->theVector.append(iarr);
+  this->assertValuesInOrder(this->theVector, iarr);
+}
+
+// Assign test
+TYPED_TEST(StaticVectorTest, AssignTest) {
+  SCOPED_TRACE("AssignTest");
+
+  this->theVector.push_back(Constructable(1));
+  this->theVector.assign(2, Constructable(77));
+  this->assertValuesInOrder(this->theVector, 2u, 77, 77);
+}
+
+// Assign test
+TYPED_TEST(StaticVectorTest, AssignRangeTest) {
+  SCOPED_TRACE("AssignTest");
+
+  this->theVector.push_back(Constructable(1));
+  int arr[] = {1, 2, 3};
+  this->theVector.assign(std::begin(arr), std::end(arr));
+  this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3);
+}
+
+// Assign test
+TYPED_TEST(StaticVectorTest, AssignNonIterTest) {
+  SCOPED_TRACE("AssignTest");
+
+  this->theVector.push_back(Constructable(1));
+  this->theVector.assign(2, 7);
+  this->assertValuesInOrder(this->theVector, 2u, 7, 7);
+}
+
+TYPED_TEST(StaticVectorTest, AssignStaticVector) {
+  SCOPED_TRACE("AssignStaticVector");
+
+  StaticVector<Constructable, 3> otherVector = {7, 7};
+  this->theVector.push_back(Constructable(1));
+  this->theVector.assign(otherVector);
+  this->assertValuesInOrder(this->theVector, 2u, 7, 7);
+}
+
+TYPED_TEST(StaticVectorTest, AssignCArrayVector) {
+  SCOPED_TRACE("AssignCArrayVector");
+
+  int Arr[]{1, 3, 5};
+
+  this->theVector.emplace_back(1);
+
+  // Us the assign() member function to assign.
+  this->theVector.assign(Arr);
+  this->assertValuesInOrder(this->theVector, Arr);
+
+  this->theVector.clear();
+  this->theVector.emplace_back(1);
+
+  // Use operator=() to assign.
+  this->theVector = Arr;
+  this->assertValuesInOrder(this->theVector, Arr);
+}
+
+TYPED_TEST(StaticVectorTest, AssignInitializerList) {
+  SCOPED_TRACE("AssignInitializerList");
+
+  this->theVector.emplace_back(1);
+  this->theVector.assign({2, 4, 6, 8});
+  this->assertValuesInOrder(this->theVector, {2, 4, 6, 8});
+
+  this->theVector.clear();
+  this->theVector.emplace_back(1);
+  this->theVector = {2, 4, 6, 8};
+  this->assertValuesInOrder(this->theVector, {2, 4, 6, 8});
+}
+
+TYPED_TEST(StaticVectorTest, AssignArrayRef) {
+  SCOPED_TRACE("AssignArrayRef");
+
+  auto IL = {2, 4, 6, 8};
+  ArrayRef<int> AR(IL);
+
+  this->theVector.emplace_back(1);
+  this->theVector.assign(AR);
+  this->assertValuesInOrder(this->theVector, AR);
+
+  this->theVector.clear();
+
+  this->theVector.emplace_back(1);
+  this->theVector = AR;
+  this->assertValuesInOrder(this->theVector, AR);
+}
+
+// Move-assign test
+TYPED_TEST(StaticVectorTest, MoveAssignTest) {
+  SCOPED_TRACE("MoveAssignTest");
+
+  // Set up our vector with a single element, but enough capacity for 4.
+  this->theVector.emplace_back(1);
+
+  // Set up the other vector with 2 elements.
+  this->otherVector.push_back(Constructable(2));
+  this->otherVector.push_back(Constructable(3));
+
+  // Move-assign from the other vector.
+  this->theVector = std::move(this->otherVector);
+
+  // Make sure we have the right result.
+  this->assertValuesInOrder(this->theVector, 2u, 2, 3);
+
+  // Make sure the # of constructor/destructor calls line up. There
+  // are two live objects after clearing the other vector.
+  this->otherVector.clear();
+  EXPECT_EQ(Constructable::getNumConstructorCalls() - 2,
+            Constructable::getNumDestructorCalls());
+
+  // There shouldn't be any live objects any more.
+  this->theVector.clear();
+  EXPECT_EQ(Constructable::getNumConstructorCalls(),
+            Constructable::getNumDestructorCalls());
+}
+
+// Erase a single element
+TYPED_TEST(StaticVectorTest, EraseTest) {
+  SCOPED_TRACE("EraseTest");
+
+  this->makeSequence(this->theVector, 1, 3);
+  const auto &theConstVector = this->theVector;
+  this->theVector.erase(theConstVector.begin());
+  this->assertValuesInOrder(this->theVector, {2, 3});
+}
+
+// Erase a range of elements
+TYPED_TEST(StaticVectorTest, EraseRangeTest) {
+  SCOPED_TRACE("EraseRangeTest");
+
+  this->makeSequence(this->theVector, 1, 3);
+  const auto &theConstVector = this->theVector;
+  this->theVector.erase(theConstVector.begin(), theConstVector.begin() + 2);
+  this->assertValuesInOrder(this->theVector, 1u, 3);
+}
+
+// Insert a single element.
+TYPED_TEST(StaticVectorTest, InsertTest) {
+  SCOPED_TRACE("InsertTest");
+
+  this->makeSequence(this->theVector, 1, 3);
+  typename TypeParam::iterator I =
+      this->theVector.insert(this->theVector.begin() + 1, Constructable(77));
+  EXPECT_EQ(this->theVector.begin() + 1, I);
+  this->assertValuesInOrder(this->theVector, {1, 77, 2, 3});
+}
+
+// Insert a copy of a single element.
+TYPED_TEST(StaticVectorTest, InsertCopy) {
+  SCOPED_TRACE("InsertTest");
+
+  this->makeSequence(this->theVector, 1, 3);
+  Constructable C(77);
+  typename TypeParam::iterator I =
+      this->theVector.insert(this->theVector.begin() + 1, C);
+  EXPECT_EQ(this->theVector.begin() + 1, I);
+  this->assertValuesInOrder(this->theVector, {1, 77, 2, 3});
+}
+
+// Insert repeated elements.
+TYPED_TEST(StaticVectorTest, InsertRepeatedTest) {
+  SCOPED_TRACE("InsertRepeatedTest");
+
+  if (this->theVector.capacity() < 6)
+    return;
+
+  this->makeSequence(this->theVector, 1, 4);
+  Constructable::reset();
+  auto I =
+      this->theVector.insert(this->theVector.begin() + 1, 2, Constructable(16));
+  // Move construct the top element into newly allocated space, and optionally
+  // reallocate the whole buffer, move constructing into it.
+  // FIXME: This is inefficient, we shouldn't move things into newly allocated
+  // space, then move them up/around, there should only be 2 or 4 move
+  // constructions here.
+  EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||
+              Constructable::getNumMoveConstructorCalls() == 6);
+  // Move assign the next two to shift them up and make a gap.
+  EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls());
+  // Copy construct the two new elements from the parameter.
+  EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());
+  // All without any copy construction.
+  EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls());
+  EXPECT_EQ(this->theVector.begin() + 1, I);
+  this->assertValuesInOrder(this->theVector, {1, 16, 16, 2, 3, 4});
+}
+
+TYPED_TEST(StaticVectorTest, InsertRepeatedNonIterTest) {
+  SCOPED_TRACE("InsertRepeatedNonIterTest");
+
+  if (this->theVector.capacity() < 6)
+    return;
+
+  this->makeSequence(this->theVector, 1, 4);
+  Constructable::reset();
+  auto I = this->theVector.insert(this->theVector.begin() + 1, 2, 7);
+  EXPECT_EQ(this->theVector.begin() + 1, I);
+  this->assertValuesInOrder(this->theVector, {1, 7, 7, 2, 3, 4});
+}
+
+TYPED_TEST(StaticVectorTest, InsertRepeatedAtEndTest) {
+  SCOPED_TRACE("InsertRepeatedAtEndTest");
+
+  if (this->theVector.capacity() < 6)
+    return;
+
+  this->makeSequence(this->theVector, 1, 4);
+  Constructable::reset();
+  auto I = this->theVector.insert(this->theVector.end(), 2, Constructable(16));
+  // Just copy construct them into newly allocated space
+  EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls());
+  // Move everything across if reallocation is needed.
+  EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 ||
+              Constructable::getNumMoveConstructorCalls() == 4);
+  // Without ever moving or copying anything else.
+  EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());
+  EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());
+
+  EXPECT_EQ(this->theVector.begin() + 4, I);
+  this->assertValuesInOrder(this->theVector, {1, 2, 3, 4, 16, 16});
+}
+
+TYPED_TEST(StaticVectorTest, InsertRepeatedEmptyTest) {
+  SCOPED_TRACE("InsertRepeatedEmptyTest");
+
+  if (this->theVector.capacity() < 4)
+    return;
+
+  auto I = this->theVector.insert(this->theVector.end(), 2, 10);
+  EXPECT_EQ(I, this->theVector.begin());
+  EXPECT_EQ(0, Constructable::getNumMoveConstructorCalls());
+  EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls());
+  EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());
+  EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());
+  this->assertValuesInOrder(this->theVector, {10, 10});
+
+  this->makeSequence(this->theVector, 12, 13);
+
+  // Empty insert.
+  EXPECT_EQ(
+      this->theVector.end(),
+      this->theVector.insert(this->theVector.end(), 0, Constructable(42)));
+  EXPECT_EQ(this->theVector.begin() + 1,
+            this->theVector.insert(this->theVector.begin() + 1, 0,
+                                   Constructable(42)));
+}
+
+// Insert range.
+TYPED_TEST(StaticVectorTest, InsertRangeTest) {
+  SCOPED_TRACE("InsertRangeTest");
+
+  if (this->theVector.capacity() < 6)
+    return;
+
+  Constructable Arr[3] = {Constructable(77), Constructable(77),
+                          Constructable(77)};
+
+  this->makeSequence(this->theVector, 1, 3);
+  Constructable::reset();
+  auto I = this->theVector.insert(this->theVector.begin() + 1, Arr, Arr + 3);
+  // Move construct the top 3 elements into newly allocated space.
+  // Possibly move the whole sequence into new space first.
+  // FIXME: This is inefficient, we shouldn't move things into newly allocated
+  // space, then move them up/around, there should only be 2 or 3 move
+  // constructions here.
+  EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 ||
+              Constructable::getNumMoveConstructorCalls() == 5);
+  // Copy assign the lower 2 new elements into existing space.
+  EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls());
+  // Copy construct the third element into newly allocated space.
+  EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls());
+  EXPECT_EQ(this->theVector.begin() + 1, I);
+  this->assertValuesInOrder(this->theVector, 6u, 1, 77, 77, 77, 2, 3);
+}
+
+TYPED_TEST(StaticVectorTest, InsertRangeAtEndTest) {
+  SCOPED_TRACE("InsertRangeAtEndTest");
+
+  if (this->theVector.capacity() < 6)
+    return;
+
+  Constructable Arr[3] = {Constructable(77), Constructable(77),
+                          Constructable(77)};
+
+  this->makeSequence(this->theVector, 1, 3);
+
+  // Insert at end.
+  Constructable::reset();
+  auto I = this->theVector.insert(this->theVector.end(), Arr, Arr + 3);
+  // Copy construct the 3 elements into new space at the top.
+  EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls());
+  // Don't copy/move anything else.
+  EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls());
+  // Reallocation might occur, causing all elements to be moved into the new
+  // buffer.
+  EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 ||
+              Constructable::getNumMoveConstructorCalls() == 3);
+  EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls());
+  EXPECT_EQ(this->theVector.begin() + 3, I);
+  this->assertValuesInOrder(this->theVector, 6u, 1, 2, 3, 77, 77, 77);
+}
+
+TYPED_TEST(StaticVectorTest, InsertEmptyRangeTest) {
+  SCOPED_TRACE("InsertRangeTest");
+  auto IL = {1, 2, 3};
+  auto I =
+      this->theVector.insert(this->theVector.begin(), IL.begin(), IL.end());
+  EXPECT_EQ(I, this->theVector.begin());
+  this->assertValuesInOrder(this->theVector, IL);
+
+  // Empty insert.
+  EXPECT_EQ(this->theVector.end(),
+            this->theVector.insert(this->theVector.end(),
+                                   this->theVector.begin(),
+                                   this->theVector.begin()));
+  EXPECT_EQ(this->theVector.begin() + 1,
+            this->theVector.insert(this->theVector.begin() + 1,
+                                   this->theVector.begin(),
+                                   this->theVector.begin()));
+}
+
+TYPED_TEST(StaticVectorTest, InsertCArrayTest) {
+  SCOPED_TRACE("InsertCArrayTest");
+  const int Arr[]{1, 2, 3};
+
+  this->theVector.emplace_back(4);
+
+  auto I = this->theVector.insert(this->theVector.begin(), Arr);
+  EXPECT_EQ(I, this->theVector.begin());
+  this->assertValuesInOrder(this->theVector, {1, 2, 3, 4});
+}
+
+TYPED_TEST(StaticVectorTest, InsertInializerListTest) {
+  SCOPED_TRACE("InsertInializerListTest");
+  auto IL = {1, 2, 3};
+
+  this->theVector.emplace_back(4);
+
+  auto I = this->theVector.insert(this->theVector.begin(), IL);
+  EXPECT_EQ(I, this->theVector.begin());
+  this->assertValuesInOrder(this->theVector, {1, 2, 3, 4});
+}
+
+TYPED_TEST(StaticVectorTest, InsertArrayRefTest) {
+  SCOPED_TRACE("InsertArrayRefTest");
+  auto IL = {2, 3, 4};
+
+  this->theVector.emplace_back(1);
+
+  auto I = this->theVector.insert(this->theVector.end(), IL);
+  EXPECT_EQ(I, this->theVector.begin() + 1);
+  this->assertValuesInOrder(this->theVector, {1, 2, 3, 4});
+}
+
+// Comparison tests.
+TYPED_TEST(StaticVectorTest, ComparisonTest) {
+  SCOPED_TRACE("ComparisonTest");
+
+  this->makeSequence(this->theVector, 1, 3);
+  this->makeSequence(this->otherVector, 1, 3);
+
+  EXPECT_TRUE(this->theVector == this->otherVector);
+  EXPECT_FALSE(this->theVector != this->otherVector);
+
+  this->otherVector.clear();
+  this->makeSequence(this->otherVector, 2, 4);
+
+  EXPECT_FALSE(this->theVector == this->otherVector);
+  EXPECT_TRUE(this->theVector != this->otherVector);
+}
+
+// Constant vector tests.
+TYPED_TEST(StaticVectorTest, ConstVectorTest) {
+  const TypeParam constVector;
+
+  EXPECT_EQ(0u, constVector.size());
+  EXPECT_TRUE(constVector.empty());
+  EXPECT_TRUE(constVector.begin() == constVector.end());
+}
+
+// Direct array access.
+TYPED_TEST(StaticVectorTest, DirectVectorTest) {
+  EXPECT_EQ(0u, this->theVector.size());
+  // this->theVector.reserve(4);
+  // if (this->theVector.capacity() < 4U)
+  //  return;
+  EXPECT_LE(4u, this->theVector.capacity());
+  EXPECT_EQ(0, Constructable::getNumConstructorCalls());
+  this->theVector.push_back(1);
+  this->theVector.push_back(2);
+  this->theVector.push_back(3);
+  this->theVector.push_back(4);
+  EXPECT_EQ(4u, this->theVector.size());
+  EXPECT_EQ(8, Constructable::getNumConstructorCalls());
+  EXPECT_EQ(1, this->theVector[0].getValue());
+  EXPECT_EQ(2, this->theVector[1].getValue());
+  EXPECT_EQ(3, this->theVector[2].getValue());
+  EXPECT_EQ(4, this->theVector[3].getValue());
+}
+
+TYPED_TEST(StaticVectorTest, IteratorTest) {
+  std::list<int> L;
+  this->theVector.insert(this->theVector.end(), L.begin(), L.end());
+}
+
+template <typename InvalidType> class DualStaticVectorsTest;
+
+template <typename VectorT1, typename VectorT2>
+class DualStaticVectorsTest<std::pair<VectorT1, VectorT2>>
+    : public StaticVectorTestBase {
+protected:
+  VectorT1 theVector;
+  VectorT2 otherVector;
+
+  template <typename T, size_t N>
+  static unsigned NumBuiltinElts(const StaticVector<T, N> &) {
+    return N;
+  }
+};
+
+typedef ::testing::Types<
+    // Small mode -> Small mode.
+    std::pair<StaticVector<Constructable, 4>, StaticVector<Constructable, 4>>>
+    DualStaticVectorTestTypes;
+
+TYPED_TEST_SUITE(DualStaticVectorsTest, DualStaticVectorTestTypes, );
+
+TYPED_TEST(DualStaticVectorsTest, MoveAssignment) {
+  SCOPED_TRACE("MoveAssignTest-DualVectorTypes");
+
+  // Set up our vector with four elements.
+  for (unsigned I = 0; I < 4; ++I)
+    this->otherVector.push_back(Constructable(I));
+
+  const Constructable *OrigDataPtr = this->otherVector.data();
+
+  // Move-assign from the other vector.
+  this->theVector = std::move(this->otherVector);
+
+  // Make sure we have the right result.
+  this->assertValuesInOrder(this->theVector, 4u, 0, 1, 2, 3);
+
+  // Make sure the # of constructor/destructor calls line up. There
+  // are two live objects after clearing the other vector.
+  this->otherVector.clear();
+  EXPECT_EQ(Constructable::getNumConstructorCalls() - 4,
+            Constructable::getNumDestructorCalls());
+
+  // If the source vector (otherVector) was in small-mode, assert that we just
+  // moved the data pointer over.
+  EXPECT_TRUE(this->NumBuiltinElts(this->otherVector) == 4 ||
+              this->theVector.data() == OrigDataPtr);
+
+  // There shouldn't be any live objects any more.
+  this->theVector.clear();
+  EXPECT_EQ(Constructable::getNumConstructorCalls(),
+            Constructable::getNumDestructorCalls());
+
+  // We shouldn't have copied anything in this whole process.
+  EXPECT_EQ(Constructable::getNumCopyConstructorCalls(), 0);
+}
+
+struct notassignable {
+  int &x;
+  notassignable(int &x) : x(x) {}
+};
+
+TEST(StaticVectorCustomTest, NoAssignTest) {
+  int x = 0;
+  StaticVector<notassignable, 2> vec;
+  vec.push_back(notassignable(x));
+  x = 42;
+  EXPECT_EQ(42, vec.pop_back_val().x);
+}
+
+struct MovedFrom {
+  bool hasValue;
+  MovedFrom() : hasValue(true) {}
+  MovedFrom(MovedFrom &&m) : hasValue(m.hasValue) { m.hasValue = false; }
+  MovedFrom &operator=(MovedFrom &&m) {
+    hasValue = m.hasValue;
+    m.hasValue = false;
+    return *this;
+  }
+};
+
+TEST(StaticVectorTest, MidInsert) {
+  StaticVector<MovedFrom, 3> v;
+  v.push_back(MovedFrom());
+  v.insert(v.begin(), MovedFrom());
+  for (MovedFrom &m : v)
+    EXPECT_TRUE(m.hasValue);
+}
+enum EmplaceableArgState {
+  EAS_Defaulted,
+  EAS_Arg,
+  EAS_LValue,
+  EAS_RValue,
+  EAS_Failure
+};
+
+template <int I> struct EmplaceableArg {
+  EmplaceableArgState State;
+  EmplaceableArg() : State(EAS_Defaulted) {}
+  EmplaceableArg(EmplaceableArg &&X)
+      : State(X.State == EAS_Arg ? EAS_RValue : EAS_Failure) {}
+  EmplaceableArg(EmplaceableArg &X)
+      : State(X.State == EAS_Arg ? EAS_LValue : EAS_Failure) {}
+
+  explicit EmplaceableArg(bool) : State(EAS_Arg) {}
+
+private:
+  EmplaceableArg &operator=(EmplaceableArg &&) = delete;
+  EmplaceableArg &operator=(const EmplaceableArg &) = delete;
+};
+
+enum EmplaceableState { ES_Emplaced, ES_Moved };
+struct Emplaceable {
+  EmplaceableArg<0> A0;
+  EmplaceableArg<1> A1;
+  EmplaceableArg<2> A2;
+  EmplaceableArg<3> A3;
+  EmplaceableState State;
+
+  Emplaceable() : State(ES_Emplaced) {}
+
+  template <class A0Ty>
+  explicit Emplaceable(A0Ty &&A0)
+      : A0(std::forward<A0Ty>(A0)), State(ES_Emplaced) {}
+
+  template <class A0Ty, class A1Ty>
+  Emplaceable(A0Ty &&A0, A1Ty &&A1)
+      : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
+        State(ES_Emplaced) {}
+
+  template <class A0Ty, class A1Ty, class A2Ty>
+  Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2)
+      : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
+        A2(std::forward<A2Ty>(A2)), State(ES_Emplaced) {}
+
+  template <class A0Ty, class A1Ty, class A2Ty, class A3Ty>
+  Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2, A3Ty &&A3)
+      : A0(std::forward<A0Ty>(A0)), A1(std::forward<A1Ty>(A1)),
+        A2(std::forward<A2Ty>(A2)), A3(std::forward<A3Ty>(A3)),
+        State(ES_Emplaced) {}
+
+  Emplaceable(Emplaceable &&) : State(ES_Moved) {}
+  Emplaceable &operator=(Emplaceable &&) {
+    State = ES_Moved;
+    return *this;
+  }
+
+private:
+  Emplaceable(const Emplaceable &) = delete;
+  Emplaceable &operator=(const Emplaceable &) = delete;
+};
+
+TEST(StaticVectorTest, EmplaceBack) {
+  EmplaceableArg<0> A0(true);
+  EmplaceableArg<1> A1(true);
+  EmplaceableArg<2> A2(true);
+  EmplaceableArg<3> A3(true);
+  {
+    StaticVector<Emplaceable, 3> V;
+    Emplaceable &back = V.emplace_back();
+    EXPECT_TRUE(&back == &V.back());
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(back.State == ES_Emplaced);
+    EXPECT_TRUE(back.A0.State == EAS_Defaulted);
+    EXPECT_TRUE(back.A1.State == EAS_Defaulted);
+    EXPECT_TRUE(back.A2.State == EAS_Defaulted);
+    EXPECT_TRUE(back.A3.State == EAS_Defaulted);
+  }
+  {
+    StaticVector<Emplaceable, 3> V;
+    Emplaceable &back = V.emplace_back(std::move(A0));
+    EXPECT_TRUE(&back == &V.back());
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(back.State == ES_Emplaced);
+    EXPECT_TRUE(back.A0.State == EAS_RValue);
+    EXPECT_TRUE(back.A1.State == EAS_Defaulted);
+    EXPECT_TRUE(back.A2.State == EAS_Defaulted);
+    EXPECT_TRUE(back.A3.State == EAS_Defaulted);
+  }
+  {
+    StaticVector<Emplaceable, 3> V;
+    Emplaceable &back = V.emplace_back(A0);
+    EXPECT_TRUE(&back == &V.back());
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(back.State == ES_Emplaced);
+    EXPECT_TRUE(back.A0.State == EAS_LValue);
+    EXPECT_TRUE(back.A1.State == EAS_Defaulted);
+    EXPECT_TRUE(back.A2.State == EAS_Defaulted);
+    EXPECT_TRUE(back.A3.State == EAS_Defaulted);
+  }
+  {
+    StaticVector<Emplaceable, 3> V;
+    Emplaceable &back = V.emplace_back(A0, A1);
+    EXPECT_TRUE(&back == &V.back());
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(back.State == ES_Emplaced);
+    EXPECT_TRUE(back.A0.State == EAS_LValue);
+    EXPECT_TRUE(back.A1.State == EAS_LValue);
+    EXPECT_TRUE(back.A2.State == EAS_Defaulted);
+    EXPECT_TRUE(back.A3.State == EAS_Defaulted);
+  }
+  {
+    StaticVector<Emplaceable, 3> V;
+    Emplaceable &back = V.emplace_back(std::move(A0), std::move(A1));
+    EXPECT_TRUE(&back == &V.back());
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(back.State == ES_Emplaced);
+    EXPECT_TRUE(back.A0.State == EAS_RValue);
+    EXPECT_TRUE(back.A1.State == EAS_RValue);
+    EXPECT_TRUE(back.A2.State == EAS_Defaulted);
+    EXPECT_TRUE(back.A3.State == EAS_Defaulted);
+  }
+  {
+    StaticVector<Emplaceable, 3> V;
+    Emplaceable &back = V.emplace_back(std::move(A0), A1, std::move(A2), A3);
+    EXPECT_TRUE(&back == &V.back());
+    EXPECT_TRUE(V.size() == 1);
+    EXPECT_TRUE(back.State == ES_Emplaced);
+    EXPECT_TRUE(back.A0.State == EAS_RValue);
+    EXPECT_TRUE(back.A1.State == EAS_LValue);
+    EXPECT_TRUE(back.A2.State == EAS_RValue);
+    EXPECT_TRUE(back.A3.State == EAS_LValue);
+  }
+  {
+    StaticVector<int, 2> V;
+    V.emplace_back();
+    V.emplace_back(42);
+    EXPECT_EQ(2U, V.size());
+    EXPECT_EQ(0, V[0]);
+    EXPECT_EQ(42, V[1]);
+  }
+}
+
+} // namespace