Import libc++ 8.0.0.

11 files changed, 1439 insertions, 83 deletions

diff --git a/lib/libcxx/benchmarks/CMakeLists.txt b/lib/libcxx/benchmarks/CMakeLists.txt
index f557d4aea39..3823b87b39e 100644
--- a/lib/libcxx/benchmarks/CMakeLists.txt
+++ b/lib/libcxx/benchmarks/CMakeLists.txt
@@ -11,17 +11,21 @@ set(BENCHMARK_LIBCXX_COMPILE_FLAGS
     -isystem ${LIBCXX_SOURCE_DIR}/include
     -L${LIBCXX_LIBRARY_DIR}
     -Wl,-rpath,${LIBCXX_LIBRARY_DIR}
+    ${SANITIZER_FLAGS}
     )
 if (DEFINED LIBCXX_CXX_ABI_LIBRARY_PATH)
   list(APPEND BENCHMARK_LIBCXX_COMPILE_FLAGS
           -L${LIBCXX_CXX_ABI_LIBRARY_PATH}
           -Wl,-rpath,${LIBCXX_CXX_ABI_LIBRARY_PATH})
 endif()
+if (LIBCXX_NEEDS_SITE_CONFIG)
+  list(APPEND BENCHMARK_LIBCXX_COMPILE_FLAGS -include "${LIBCXX_BINARY_DIR}/__config_site")
+endif()
 split_list(BENCHMARK_LIBCXX_COMPILE_FLAGS)
 
 ExternalProject_Add(google-benchmark-libcxx
         EXCLUDE_FROM_ALL ON
-        DEPENDS cxx
+        DEPENDS cxx cxx-headers
         PREFIX benchmark-libcxx
         SOURCE_DIR ${LIBCXX_SOURCE_DIR}/utils/google-benchmark
         INSTALL_DIR ${CMAKE_CURRENT_BINARY_DIR}/benchmark-libcxx
@@ -67,8 +71,19 @@ add_custom_target(cxx-benchmarks)
 set(BENCHMARK_OUTPUT_DIR ${CMAKE_CURRENT_BINARY_DIR})
 set(BENCHMARK_LIBCXX_INSTALL ${CMAKE_CURRENT_BINARY_DIR}/benchmark-libcxx)
 set(BENCHMARK_NATIVE_INSTALL ${CMAKE_CURRENT_BINARY_DIR}/benchmark-native)
+
+check_flag_supported("-std=c++17")
+mangle_name("LIBCXX_SUPPORTS_STD_EQ_c++17_FLAG" BENCHMARK_SUPPORTS_STD_CXX17_FLAG)
+if (${BENCHMARK_SUPPORTS_STD_CXX17_FLAG})
+  set(BENCHMARK_DIALECT_FLAG "-std=c++17")
+else()
+  # If the compiler doesn't support -std=c++17, attempt to fall back to -std=c++1z while still
+  # requiring C++17 language features.
+  set(BENCHMARK_DIALECT_FLAG "-std=c++1z")
+endif()
+
 set(BENCHMARK_TEST_COMPILE_FLAGS
-    -std=c++17 -O2
+    ${BENCHMARK_DIALECT_FLAG} -O2
     -I${BENCHMARK_LIBCXX_INSTALL}/include
     -I${LIBCXX_SOURCE_DIR}/test/support
 )
@@ -76,11 +91,18 @@ set(BENCHMARK_TEST_LIBCXX_COMPILE_FLAGS
     -nostdinc++
     -isystem ${LIBCXX_SOURCE_DIR}/include
     ${BENCHMARK_TEST_COMPILE_FLAGS}
+    ${SANITIZER_FLAGS}
     -Wno-user-defined-literals
 )
+if (LIBCXX_NEEDS_SITE_CONFIG)
+  list(APPEND BENCHMARK_TEST_LIBCXX_COMPILE_FLAGS
+      -include "${LIBCXX_BINARY_DIR}/__config_site")
+endif()
+
 set(BENCHMARK_TEST_LIBCXX_LINK_FLAGS
     -nodefaultlibs
     -L${BENCHMARK_LIBCXX_INSTALL}/lib/
+    ${SANITIZER_FLAGS}
 )
 set(BENCHMARK_TEST_NATIVE_COMPILE_FLAGS
   ${BENCHMARK_NATIVE_TARGET_FLAGS}
@@ -95,10 +117,25 @@ split_list(BENCHMARK_TEST_LIBCXX_COMPILE_FLAGS)
 split_list(BENCHMARK_TEST_LIBCXX_LINK_FLAGS)
 split_list(BENCHMARK_TEST_NATIVE_COMPILE_FLAGS)
 split_list(BENCHMARK_TEST_NATIVE_LINK_FLAGS)
-macro(add_benchmark_test name source_file)
+
+if (LIBCXX_BENCHMARK_NATIVE_STDLIB STREQUAL "libstdc++")
+  find_library(LIBSTDCXX_FILESYSTEM_TEST stdc++fs
+        PATHS ${LIBCXX_BENCHMARK_NATIVE_GCC_TOOLCHAIN}
+        PATH_SUFFIXES lib lib64
+        DOC "The libstdc++ filesystem library used by the benchmarks"
+    )
+    if (NOT "${LIBSTDCXX_FILESYSTEM_TEST}" STREQUAL "LIBSTDCXX_FILESYSTEM_TEST-NOTFOUND")
+      set(LIBSTDCXX_FILESYSTEM_LIB "stdc++fs")
+    endif()
+endif()
+
+set(libcxx_benchmark_targets)
+
+function(add_benchmark_test name source_file)
   set(libcxx_target ${name}_libcxx)
+  list(APPEND libcxx_benchmark_targets ${libcxx_target})
   add_executable(${libcxx_target} EXCLUDE_FROM_ALL ${source_file})
-  add_dependencies(${libcxx_target} cxx google-benchmark-libcxx)
+  add_dependencies(${libcxx_target} cxx cxx-headers google-benchmark-libcxx)
   add_dependencies(cxx-benchmarks ${libcxx_target})
   if (LIBCXX_ENABLE_SHARED)
     target_link_libraries(${libcxx_target} cxx_shared)
@@ -108,7 +145,13 @@ macro(add_benchmark_test name source_file)
   if (TARGET cxx_experimental)
     target_link_libraries(${libcxx_target} cxx_experimental)
   endif()
+  if (TARGET cxx_filesystem)
+    target_link_libraries(${libcxx_target} cxx_filesystem)
+  endif()
   target_link_libraries(${libcxx_target} -lbenchmark)
+  if (LLVM_USE_SANITIZER)
+    target_link_libraries(${libcxx_target} -ldl)
+  endif()
   set_target_properties(${libcxx_target}
     PROPERTIES
           OUTPUT_NAME "${name}.libcxx.out"
@@ -116,15 +159,19 @@ macro(add_benchmark_test name source_file)
           COMPILE_FLAGS "${BENCHMARK_TEST_LIBCXX_COMPILE_FLAGS}"
           LINK_FLAGS "${BENCHMARK_TEST_LIBCXX_LINK_FLAGS}")
   if (LIBCXX_BENCHMARK_NATIVE_STDLIB)
+    if (LIBCXX_BENCHMARK_NATIVE_STDLIB STREQUAL "libstdc++" AND NOT DEFINED LIBSTDCXX_FILESYSTEM_LIB
+        AND "${name}" STREQUAL "filesystem")
+      return()
+    endif()
     set(native_target ${name}_native)
     add_executable(${native_target} EXCLUDE_FROM_ALL ${source_file})
     add_dependencies(${native_target} google-benchmark-native
                                       google-benchmark-libcxx)
     target_link_libraries(${native_target} -lbenchmark)
     if (LIBCXX_BENCHMARK_NATIVE_STDLIB STREQUAL "libstdc++")
-      target_link_libraries(${native_target} -lstdc++fs)
+      target_link_libraries(${native_target} ${LIBSTDCXX_FILESYSTEM_LIB})
     elseif (LIBCXX_BENCHMARK_NATIVE_STDLIB STREQUAL "libc++")
-      target_link_libraries(${native_target} -lc++experimental)
+      target_link_libraries(${native_target} -lc++fs -lc++experimental)
     endif()
     if (LIBCXX_HAS_PTHREAD_LIB)
       target_link_libraries(${native_target} -pthread)
@@ -138,7 +185,7 @@ macro(add_benchmark_test name source_file)
           COMPILE_FLAGS "${BENCHMARK_TEST_NATIVE_COMPILE_FLAGS}"
           LINK_FLAGS "${BENCHMARK_TEST_NATIVE_LINK_FLAGS}")
   endif()
-endmacro()
+endfunction()
 
 
 #==============================================================================
@@ -155,3 +202,23 @@ foreach(test_path ${BENCHMARK_TESTS})
   endif()
   add_benchmark_test(${test_name} ${test_file})
 endforeach()
+
+if (LIBCXX_INCLUDE_TESTS)
+  include(AddLLVM)
+
+  if (NOT DEFINED LIBCXX_TEST_DEPS)
+    message(FATAL_ERROR "Expected LIBCXX_TEST_DEPS to be defined")
+  endif()
+
+  configure_lit_site_cfg(
+          ${CMAKE_CURRENT_SOURCE_DIR}/lit.site.cfg.py.in
+          ${CMAKE_CURRENT_BINARY_DIR}/lit.site.cfg.py)
+
+  set(BENCHMARK_LIT_ARGS "--show-all --show-xfail --show-unsupported ${LIT_ARGS_DEFAULT}")
+
+  add_lit_target(check-cxx-benchmarks
+          "Running libcxx benchmarks tests"
+          ${CMAKE_CURRENT_BINARY_DIR}
+          DEPENDS cxx-benchmarks ${LIBCXX_TEST_DEPS}
+          ARGS ${BENCHMARK_LIT_ARGS})
+endif()
diff --git a/lib/libcxx/benchmarks/CartesianBenchmarks.hpp b/lib/libcxx/benchmarks/CartesianBenchmarks.hpp
new file mode 100644
index 00000000000..88a994c5551
--- /dev/null
+++ b/lib/libcxx/benchmarks/CartesianBenchmarks.hpp
@@ -0,0 +1,135 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+
+#include <string>
+#include <tuple>
+#include <type_traits>
+#include <vector>
+
+#include "benchmark/benchmark.h"
+#include "test_macros.h"
+
+namespace internal {
+
+template <class D, class E, size_t I>
+struct EnumValue : std::integral_constant<E, static_cast<E>(I)> {
+  static std::string name() { return std::string("_") + D::Names[I]; }
+};
+
+template <class D, class E, size_t ...Idxs>
+constexpr auto makeEnumValueTuple(std::index_sequence<Idxs...>) {
+  return std::make_tuple(EnumValue<D, E, Idxs>{}...);
+}
+
+template <class B>
+static auto skip(const B& Bench, int) -> decltype(Bench.skip()) {
+  return Bench.skip();
+}
+template <class B>
+static auto skip(const B& Bench, char) {
+  return false;
+}
+
+template <class B, class Args, size_t... Is>
+void makeBenchmarkFromValuesImpl(const Args& A, std::index_sequence<Is...>) {
+  for (auto& V : A) {
+    B Bench{std::get<Is>(V)...};
+    if (!internal::skip(Bench, 0)) {
+      benchmark::RegisterBenchmark(Bench.name().c_str(),
+                                   [=](benchmark::State& S) { Bench.run(S); });
+    }
+  }
+}
+
+template <class B, class... Args>
+void makeBenchmarkFromValues(const std::vector<std::tuple<Args...> >& A) {
+  makeBenchmarkFromValuesImpl<B>(A, std::index_sequence_for<Args...>());
+}
+
+template <template <class...> class B, class Args, class... U>
+void makeBenchmarkImpl(const Args& A, std::tuple<U...> t) {
+  makeBenchmarkFromValues<B<U...> >(A);
+}
+
+template <template <class...> class B, class Args, class... U,
+          class... T, class... Tuples>
+void makeBenchmarkImpl(const Args& A, std::tuple<U...>, std::tuple<T...>,
+                       Tuples... rest) {
+  (internal::makeBenchmarkImpl<B>(A, std::tuple<U..., T>(), rest...), ...);
+}
+
+template <class R, class T>
+void allValueCombinations(R& Result, const T& Final) {
+  return Result.push_back(Final);
+}
+
+template <class R, class T, class V, class... Vs>
+void allValueCombinations(R& Result, const T& Prev, const V& Value,
+                          const Vs&... Values) {
+  for (const auto& E : Value) {
+    allValueCombinations(Result, std::tuple_cat(Prev, std::make_tuple(E)),
+                         Values...);
+  }
+}
+
+}  // namespace internal
+
+// CRTP class that enables using enum types as a dimension for
+// makeCartesianProductBenchmark below.
+// The type passed to `B` will be a std::integral_constant<E, e>, with the
+// additional static function `name()` that returns the stringified name of the
+// label.
+//
+// Eg:
+// enum class MyEnum { A, B };
+// struct AllMyEnum : EnumValuesAsTuple<AllMyEnum, MyEnum, 2> {
+//   static constexpr absl::string_view Names[] = {"A", "B"};
+// };
+template <class Derived, class EnumType, size_t NumLabels>
+using EnumValuesAsTuple =
+    decltype(internal::makeEnumValueTuple<Derived, EnumType>(
+        std::make_index_sequence<NumLabels>{}));
+
+// Instantiates B<T0, T1, ..., TN> where <Ti...> are the combinations in the
+// cartesian product of `Tuples...`, and pass (arg0, ..., argN) as constructor
+// arguments where `(argi...)` are the combination in the cartesian product of
+// the runtime values of `A...`.
+// B<T...> requires:
+//  - std::string name(args...): The name of the benchmark.
+//  - void run(benchmark::State&, args...): The body of the benchmark.
+// It can also optionally provide:
+//  - bool skip(args...): When `true`, skips the combination. Default is false.
+//
+// Returns int to facilitate registration. The return value is unspecified.
+template <template <class...> class B, class... Tuples, class... Args>
+int makeCartesianProductBenchmark(const Args&... A) {
+  std::vector<std::tuple<typename Args::value_type...> > V;
+  internal::allValueCombinations(V, std::tuple<>(), A...);
+  internal::makeBenchmarkImpl<B>(V, std::tuple<>(), Tuples()...);
+  return 0;
+}
+
+template <class B, class... Args>
+int makeCartesianProductBenchmark(const Args&... A) {
+  std::vector<std::tuple<typename Args::value_type...> > V;
+  internal::allValueCombinations(V, std::tuple<>(), A...);
+  internal::makeBenchmarkFromValues<B>(V);
+  return 0;
+}
+
+// When `opaque` is true, this function hides the runtime state of `value` from
+// the optimizer.
+// It returns `value`.
+template <class T>
+TEST_ALWAYS_INLINE inline T maybeOpaque(T value, bool opaque) {
+  if (opaque) benchmark::DoNotOptimize(value);
+  return value;
+}
+
diff --git a/lib/libcxx/benchmarks/algorithms.bench.cpp b/lib/libcxx/benchmarks/algorithms.bench.cpp
index 86315390e0d..eee8a4da2ab 100644
--- a/lib/libcxx/benchmarks/algorithms.bench.cpp
+++ b/lib/libcxx/benchmarks/algorithms.bench.cpp
@@ -1,62 +1,270 @@
-#include <unordered_set>
-#include <vector>
+
+#include <algorithm>
 #include <cstdint>
+#include <map>
+#include <random>
+#include <string>
+#include <utility>
+#include <vector>
 
-#include "benchmark/benchmark.h"
+#include "CartesianBenchmarks.hpp"
 #include "GenerateInput.hpp"
+#include "benchmark/benchmark.h"
+#include "test_macros.h"
+
+namespace {
+
+enum class ValueType { Uint32, String };
+struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 2> {
+  static constexpr const char* Names[] = {"uint32", "string"};
+};
+
+template <class V>
+using Value =
+    std::conditional_t<V() == ValueType::Uint32, uint32_t, std::string>;
+
+enum class Order {
+  Random,
+  Ascending,
+  Descending,
+  SingleElement,
+  PipeOrgan,
+  Heap
+};
+struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 6> {
+  static constexpr const char* Names[] = {"Random",     "Ascending",
+                                          "Descending", "SingleElement",
+                                          "PipeOrgan",  "Heap"};
+};
+
+void fillValues(std::vector<uint32_t>& V, size_t N, Order O) {
+  if (O == Order::SingleElement) {
+    V.resize(N, 0);
+  } else {
+    while (V.size() < N)
+      V.push_back(V.size());
+  }
+}
+
+void fillValues(std::vector<std::string>& V, size_t N, Order O) {
+
+  if (O == Order::SingleElement) {
+    V.resize(N, getRandomString(1024));
+  } else {
+    while (V.size() < N)
+      V.push_back(getRandomString(1024));
+  }
+}
+
+template <class T>
+void sortValues(T& V, Order O) {
+  assert(std::is_sorted(V.begin(), V.end()));
+  switch (O) {
+  case Order::Random: {
+    std::random_device R;
+    std::mt19937 M(R());
+    std::shuffle(V.begin(), V.end(), M);
+    break;
+  }
+  case Order::Ascending:
+    std::sort(V.begin(), V.end());
+    break;
+  case Order::Descending:
+    std::sort(V.begin(), V.end(), std::greater<>());
+    break;
+  case Order::SingleElement:
+    // Nothing to do
+    break;
+  case Order::PipeOrgan:
+    std::sort(V.begin(), V.end());
+    std::reverse(V.begin() + V.size() / 2, V.end());
+    break;
+  case Order::Heap:
+    std::make_heap(V.begin(), V.end());
+    break;
+  }
+}
+
+template <class ValueType>
+std::vector<std::vector<Value<ValueType> > > makeOrderedValues(size_t N,
+                                                               Order O) {
+  // Let's make sure that all random sequences of the same size are the same.
+  // That way we can compare the different algorithms with the same input.
+  static std::map<std::pair<size_t, Order>, std::vector<Value<ValueType> > >
+      Cached;
 
-constexpr std::size_t TestNumInputs = 1024;
-
-template <class GenInputs>
-void BM_Sort(benchmark::State& st, GenInputs gen) {
-    using ValueType = typename decltype(gen(0))::value_type;
-    const auto in = gen(st.range(0));
-    std::vector<ValueType> inputs[5];
-    auto reset_inputs = [&]() {
-        for (auto& C : inputs) {
-            C = in;
-            benchmark::DoNotOptimize(C.data());
-        }
-    };
-    reset_inputs();
-    while (st.KeepRunning()) {
-        for (auto& I : inputs) {
-            std::sort(I.data(), I.data() + I.size());
-            benchmark::DoNotOptimize(I.data());
-        }
-        st.PauseTiming();
-        reset_inputs();
-        benchmark::ClobberMemory();
-        st.ResumeTiming();
+  auto& Values = Cached[{N, O}];
+  if (Values.empty()) {
+    fillValues(Values, N, O);
+    sortValues(Values, O);
+  };
+  const size_t NumCopies = std::max(size_t{1}, 1000 / N);
+  return { NumCopies, Values };
+}
+
+template <class T, class U>
+TEST_ALWAYS_INLINE void resetCopies(benchmark::State& state, T& Copies,
+                                    U& Orig) {
+  state.PauseTiming();
+  for (auto& Copy : Copies)
+    Copy = Orig;
+  state.ResumeTiming();
+}
+
+template <class ValueType, class F>
+void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O,
+                   bool CountElements, F f) {
+  auto Copies = makeOrderedValues<ValueType>(Quantity, O);
+  const auto Orig = Copies[0];
+
+  const size_t Batch = CountElements ? Copies.size() * Quantity : Copies.size();
+  while (state.KeepRunningBatch(Batch)) {
+    for (auto& Copy : Copies) {
+      f(Copy);
+      benchmark::DoNotOptimize(Copy);
     }
+    resetCopies(state, Copies, Orig);
+  }
 }
 
-BENCHMARK_CAPTURE(BM_Sort, random_uint32,
-    getRandomIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+template <class ValueType, class Order>
+struct Sort {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
+      std::sort(Copy.begin(), Copy.end());
+    });
+  }
+
+  bool skip() const { return Order() == ::Order::Heap; }
+
+  std::string name() const {
+    return "BM_Sort" + ValueType::name() + Order::name() + "_" +
+           std::to_string(Quantity);
+  };
+};
+
+template <class ValueType, class Order>
+struct StableSort {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
+      std::stable_sort(Copy.begin(), Copy.end());
+    });
+  }
+
+  bool skip() const { return Order() == ::Order::Heap; }
+
+  std::string name() const {
+    return "BM_StableSort" + ValueType::name() + Order::name() + "_" +
+           std::to_string(Quantity);
+  };
+};
+
+template <class ValueType, class Order>
+struct MakeHeap {
+  size_t Quantity;
 
-BENCHMARK_CAPTURE(BM_Sort, sorted_ascending_uint32,
-    getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
+      std::make_heap(Copy.begin(), Copy.end());
+    });
+  }
 
-BENCHMARK_CAPTURE(BM_Sort, sorted_descending_uint32,
-    getReverseSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+  std::string name() const {
+    return "BM_MakeHeap" + ValueType::name() + Order::name() + "_" +
+           std::to_string(Quantity);
+  };
+};
 
-BENCHMARK_CAPTURE(BM_Sort, single_element_uint32,
-    getDuplicateIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+template <class ValueType>
+struct SortHeap {
+  size_t Quantity;
 
-BENCHMARK_CAPTURE(BM_Sort, pipe_organ_uint32,
-    getPipeOrganIntegerInputs<uint32_t>)->Arg(TestNumInputs);
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order::Heap, false,
+        [](auto& Copy) { std::sort_heap(Copy.begin(), Copy.end()); });
+  }
 
-BENCHMARK_CAPTURE(BM_Sort, random_strings,
-    getRandomStringInputs)->Arg(TestNumInputs);
+  std::string name() const {
+    return "BM_SortHeap" + ValueType::name() + "_" + std::to_string(Quantity);
+  };
+};
 
-BENCHMARK_CAPTURE(BM_Sort, sorted_ascending_strings,
-    getSortedStringInputs)->Arg(TestNumInputs);
+template <class ValueType, class Order>
+struct MakeThenSortHeap {
+  size_t Quantity;
 
-BENCHMARK_CAPTURE(BM_Sort, sorted_descending_strings,
-    getReverseSortedStringInputs)->Arg(TestNumInputs);
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
+      std::make_heap(Copy.begin(), Copy.end());
+      std::sort_heap(Copy.begin(), Copy.end());
+    });
+  }
 
-BENCHMARK_CAPTURE(BM_Sort, single_element_strings,
-    getDuplicateStringInputs)->Arg(TestNumInputs);
+  std::string name() const {
+    return "BM_MakeThenSortHeap" + ValueType::name() + Order::name() + "_" +
+           std::to_string(Quantity);
+  };
+};
 
+template <class ValueType, class Order>
+struct PushHeap {
+  size_t Quantity;
 
-BENCHMARK_MAIN();
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) {
+      for (auto I = Copy.begin(), E = Copy.end(); I != E; ++I) {
+        std::push_heap(Copy.begin(), I + 1);
+      }
+    });
+  }
+
+  bool skip() const { return Order() == ::Order::Heap; }
+
+  std::string name() const {
+    return "BM_PushHeap" + ValueType::name() + Order::name() + "_" +
+           std::to_string(Quantity);
+  };
+};
+
+template <class ValueType>
+struct PopHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) {
+      for (auto B = Copy.begin(), I = Copy.end(); I != B; --I) {
+        std::pop_heap(B, I);
+      }
+    });
+  }
+
+  std::string name() const {
+    return "BM_PopHeap" + ValueType::name() + "_" + std::to_string(Quantity);
+  };
+};
+
+} // namespace
+
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+
+  const std::vector<size_t> Quantities = {1 << 0, 1 << 2,  1 << 4,  1 << 6,
+                                          1 << 8, 1 << 10, 1 << 14, 1 << 18};
+  makeCartesianProductBenchmark<Sort, AllValueTypes, AllOrders>(Quantities);
+  makeCartesianProductBenchmark<StableSort, AllValueTypes, AllOrders>(
+      Quantities);
+  makeCartesianProductBenchmark<MakeHeap, AllValueTypes, AllOrders>(Quantities);
+  makeCartesianProductBenchmark<SortHeap, AllValueTypes>(Quantities);
+  makeCartesianProductBenchmark<MakeThenSortHeap, AllValueTypes, AllOrders>(
+      Quantities);
+  makeCartesianProductBenchmark<PushHeap, AllValueTypes, AllOrders>(Quantities);
+  makeCartesianProductBenchmark<PopHeap, AllValueTypes>(Quantities);
+  benchmark::RunSpecifiedBenchmarks();
+}
diff --git a/lib/libcxx/benchmarks/algorithms.partition_point.bench.cpp b/lib/libcxx/benchmarks/algorithms.partition_point.bench.cpp
new file mode 100644
index 00000000000..00a3bb27267
--- /dev/null
+++ b/lib/libcxx/benchmarks/algorithms.partition_point.bench.cpp
@@ -0,0 +1,124 @@
+#include <array>
+#include <algorithm>
+#include <cassert>
+#include <cstdint>
+#include <tuple>
+#include <vector>
+
+#include "benchmark/benchmark.h"
+
+#include "CartesianBenchmarks.hpp"
+#include "GenerateInput.hpp"
+
+namespace {
+
+template <typename I, typename N>
+std::array<I, 10> every_10th_percentile_N(I first, N n) {
+  N step = n / 10;
+  std::array<I, 10> res;
+
+  for (size_t i = 0; i < 10; ++i) {
+    res[i] = first;
+    std::advance(first, step);
+  }
+
+  return res;
+}
+
+template <class IntT>
+struct TestIntBase {
+  static std::vector<IntT> generateInput(size_t size) {
+    std::vector<IntT> Res(size);
+    std::generate(Res.begin(), Res.end(),
+                  [] { return getRandomInteger<IntT>(); });
+    return Res;
+  }
+};
+
+struct TestInt32 : TestIntBase<std::int32_t> {
+  static constexpr const char* Name = "TestInt32";
+};
+
+struct TestInt64 : TestIntBase<std::int64_t> {
+  static constexpr const char* Name = "TestInt64";
+};
+
+struct TestUint32 : TestIntBase<std::uint32_t> {
+  static constexpr const char* Name = "TestUint32";
+};
+
+struct TestMediumString {
+  static constexpr const char* Name = "TestMediumString";
+  static constexpr size_t StringSize = 32;
+
+  static std::vector<std::string> generateInput(size_t size) {
+    std::vector<std::string> Res(size);
+    std::generate(Res.begin(), Res.end(), [] { return getRandomString(StringSize); });
+    return Res;
+  }
+};
+
+using AllTestTypes = std::tuple<TestInt32, TestInt64, TestUint32, TestMediumString>;
+
+struct LowerBoundAlg {
+  template <class I, class V>
+  I operator()(I first, I last, const V& value) const {
+    return std::lower_bound(first, last, value);
+  }
+
+  static constexpr const char* Name = "LowerBoundAlg";
+};
+
+struct UpperBoundAlg {
+  template <class I, class V>
+  I operator()(I first, I last, const V& value) const {
+    return std::upper_bound(first, last, value);
+  }
+
+  static constexpr const char* Name = "UpperBoundAlg";
+};
+
+struct EqualRangeAlg {
+  template <class I, class V>
+  std::pair<I, I> operator()(I first, I last, const V& value) const {
+    return std::equal_range(first, last, value);
+  }
+
+  static constexpr const char* Name = "EqualRangeAlg";
+};
+
+using AllAlgs = std::tuple<LowerBoundAlg, UpperBoundAlg, EqualRangeAlg>;
+
+template <class Alg, class TestType>
+struct PartitionPointBench {
+  size_t Quantity;
+
+  std::string name() const {
+    return std::string("PartitionPointBench_") + Alg::Name + "_" +
+           TestType::Name + '/' + std::to_string(Quantity);
+  }
+
+  void run(benchmark::State& state) const {
+    auto Data = TestType::generateInput(Quantity);
+    std::sort(Data.begin(), Data.end());
+    auto Every10Percentile = every_10th_percentile_N(Data.begin(), Data.size());
+
+    for (auto _ : state) {
+      for (auto Test : Every10Percentile)
+        benchmark::DoNotOptimize(Alg{}(Data.begin(), Data.end(), *Test));
+    }
+  }
+};
+
+} // namespace
+
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+
+  const std::vector<size_t> Quantities = {1 << 8, 1 << 10, 1 << 20};
+  makeCartesianProductBenchmark<PartitionPointBench, AllAlgs, AllTestTypes>(
+      Quantities);
+  benchmark::RunSpecifiedBenchmarks();
+}
diff --git a/lib/libcxx/benchmarks/function.bench.cpp b/lib/libcxx/benchmarks/function.bench.cpp
new file mode 100644
index 00000000000..4f0e1fd80fa
--- /dev/null
+++ b/lib/libcxx/benchmarks/function.bench.cpp
@@ -0,0 +1,232 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include <cstdint>
+#include <functional>
+#include <memory>
+#include <string>
+
+#include "CartesianBenchmarks.hpp"
+#include "benchmark/benchmark.h"
+#include "test_macros.h"
+
+namespace {
+
+enum class FunctionType {
+  Null,
+  FunctionPointer,
+  MemberFunctionPointer,
+  MemberPointer,
+  SmallTrivialFunctor,
+  SmallNonTrivialFunctor,
+  LargeTrivialFunctor,
+  LargeNonTrivialFunctor
+};
+
+struct AllFunctionTypes : EnumValuesAsTuple<AllFunctionTypes, FunctionType, 8> {
+  static constexpr const char* Names[] = {"Null",
+                                          "FuncPtr",
+                                          "MemFuncPtr",
+                                          "MemPtr",
+                                          "SmallTrivialFunctor",
+                                          "SmallNonTrivialFunctor",
+                                          "LargeTrivialFunctor",
+                                          "LargeNonTrivialFunctor"};
+};
+
+enum class Opacity { kOpaque, kTransparent };
+
+struct AllOpacity : EnumValuesAsTuple<AllOpacity, Opacity, 2> {
+  static constexpr const char* Names[] = {"Opaque", "Transparent"};
+};
+
+struct S {
+  int function() const { return 0; }
+  int field = 0;
+};
+
+int FunctionWithS(const S*) { return 0; }
+
+struct SmallTrivialFunctor {
+  int operator()(const S*) const { return 0; }
+};
+struct SmallNonTrivialFunctor {
+  SmallNonTrivialFunctor() {}
+  SmallNonTrivialFunctor(const SmallNonTrivialFunctor&) {}
+  ~SmallNonTrivialFunctor() {}
+  int operator()(const S*) const { return 0; }
+};
+struct LargeTrivialFunctor {
+  LargeTrivialFunctor() {
+      // Do not spend time initializing the padding.
+  }
+  int padding[16];
+  int operator()(const S*) const { return 0; }
+};
+struct LargeNonTrivialFunctor {
+  int padding[16];
+  LargeNonTrivialFunctor() {
+      // Do not spend time initializing the padding.
+  }
+  LargeNonTrivialFunctor(const LargeNonTrivialFunctor&) {}
+  ~LargeNonTrivialFunctor() {}
+  int operator()(const S*) const { return 0; }
+};
+
+using Function = std::function<int(const S*)>;
+
+TEST_ALWAYS_INLINE
+inline Function MakeFunction(FunctionType type, bool opaque = false) {
+  switch (type) {
+    case FunctionType::Null:
+      return nullptr;
+    case FunctionType::FunctionPointer:
+      return maybeOpaque(FunctionWithS, opaque);
+    case FunctionType::MemberFunctionPointer:
+      return maybeOpaque(&S::function, opaque);
+    case FunctionType::MemberPointer:
+      return maybeOpaque(&S::field, opaque);
+    case FunctionType::SmallTrivialFunctor:
+      return maybeOpaque(SmallTrivialFunctor{}, opaque);
+    case FunctionType::SmallNonTrivialFunctor:
+      return maybeOpaque(SmallNonTrivialFunctor{}, opaque);
+    case FunctionType::LargeTrivialFunctor:
+      return maybeOpaque(LargeTrivialFunctor{}, opaque);
+    case FunctionType::LargeNonTrivialFunctor:
+      return maybeOpaque(LargeNonTrivialFunctor{}, opaque);
+  }
+}
+
+template <class Opacity, class FunctionType>
+struct ConstructAndDestroy {
+  static void run(benchmark::State& state) {
+    for (auto _ : state) {
+      if (Opacity() == ::Opacity::kOpaque) {
+        benchmark::DoNotOptimize(MakeFunction(FunctionType(), true));
+      } else {
+        MakeFunction(FunctionType());
+      }
+    }
+  }
+
+  static std::string name() {
+    return "BM_ConstructAndDestroy" + FunctionType::name() + Opacity::name();
+  }
+};
+
+template <class FunctionType>
+struct Copy {
+  static void run(benchmark::State& state) {
+    auto value = MakeFunction(FunctionType());
+    for (auto _ : state) {
+      benchmark::DoNotOptimize(value);
+      auto copy = value;  // NOLINT
+      benchmark::DoNotOptimize(copy);
+    }
+  }
+
+  static std::string name() { return "BM_Copy" + FunctionType::name(); }
+};
+
+template <class FunctionType>
+struct Move {
+  static void run(benchmark::State& state) {
+    Function values[2] = {MakeFunction(FunctionType())};
+    int i = 0;
+    for (auto _ : state) {
+      benchmark::DoNotOptimize(values);
+      benchmark::DoNotOptimize(values[i ^ 1] = std::move(values[i]));
+      i ^= 1;
+    }
+  }
+
+  static std::string name() {
+    return "BM_Move" + FunctionType::name();
+  }
+};
+
+template <class Function1, class Function2>
+struct Swap {
+  static void run(benchmark::State& state) {
+    Function values[2] = {MakeFunction(Function1()), MakeFunction(Function2())};
+    for (auto _ : state) {
+      benchmark::DoNotOptimize(values);
+      values[0].swap(values[1]);
+    }
+  }
+
+  static bool skip() { return Function1() > Function2(); }
+
+  static std::string name() {
+    return "BM_Swap" + Function1::name() + Function2::name();
+  }
+};
+
+template <class FunctionType>
+struct OperatorBool {
+  static void run(benchmark::State& state) {
+    auto f = MakeFunction(FunctionType());
+    for (auto _ : state) {
+      benchmark::DoNotOptimize(f);
+      benchmark::DoNotOptimize(static_cast<bool>(f));
+    }
+  }
+
+  static std::string name() { return "BM_OperatorBool" + FunctionType::name(); }
+};
+
+template <class FunctionType>
+struct Invoke {
+  static void run(benchmark::State& state) {
+    S s;
+    const auto value = MakeFunction(FunctionType());
+    for (auto _ : state) {
+      benchmark::DoNotOptimize(value);
+      benchmark::DoNotOptimize(value(&s));
+    }
+  }
+
+  static bool skip() { return FunctionType() == ::FunctionType::Null; }
+
+  static std::string name() { return "BM_Invoke" + FunctionType::name(); }
+};
+
+template <class FunctionType>
+struct InvokeInlined {
+  static void run(benchmark::State& state) {
+    S s;
+    for (auto _ : state) {
+      MakeFunction(FunctionType())(&s);
+    }
+  }
+
+  static bool skip() { return FunctionType() == ::FunctionType::Null; }
+
+  static std::string name() {
+    return "BM_InvokeInlined" + FunctionType::name();
+  }
+};
+
+}  // namespace
+
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+
+  makeCartesianProductBenchmark<ConstructAndDestroy, AllOpacity,
+                                AllFunctionTypes>();
+  makeCartesianProductBenchmark<Copy, AllFunctionTypes>();
+  makeCartesianProductBenchmark<Move, AllFunctionTypes>();
+  makeCartesianProductBenchmark<Swap, AllFunctionTypes, AllFunctionTypes>();
+  makeCartesianProductBenchmark<OperatorBool, AllFunctionTypes>();
+  makeCartesianProductBenchmark<Invoke, AllFunctionTypes>();
+  makeCartesianProductBenchmark<InvokeInlined, AllFunctionTypes>();
+  benchmark::RunSpecifiedBenchmarks();
+}
diff --git a/lib/libcxx/benchmarks/lit.cfg.py b/lib/libcxx/benchmarks/lit.cfg.py
new file mode 100644
index 00000000000..84857d570d7
--- /dev/null
+++ b/lib/libcxx/benchmarks/lit.cfg.py
@@ -0,0 +1,23 @@
+# -*- Python -*- vim: set ft=python ts=4 sw=4 expandtab tw=79:
+# Configuration file for the 'lit' test runner.
+import os
+import site
+
+site.addsitedir(os.path.join(os.path.dirname(os.path.dirname(__file__)), 'utils'))
+from libcxx.test.googlebenchmark import GoogleBenchmark
+
+# Tell pylint that we know config and lit_config exist somewhere.
+if 'PYLINT_IMPORT' in os.environ:
+    config = object()
+    lit_config = object()
+
+# name: The name of this test suite.
+config.name = 'libc++ benchmarks'
+config.suffixes = []
+
+config.test_exec_root = os.path.join(config.libcxx_obj_root, 'benchmarks')
+config.test_source_root = config.test_exec_root
+
+config.test_format = GoogleBenchmark(test_sub_dirs='.',
+                                     test_suffix='.libcxx.out',
+                                     benchmark_args=config.benchmark_args)
\ No newline at end of file
diff --git a/lib/libcxx/benchmarks/lit.site.cfg.py.in b/lib/libcxx/benchmarks/lit.site.cfg.py.in
new file mode 100644
index 00000000000..e3ce8b22263
--- /dev/null
+++ b/lib/libcxx/benchmarks/lit.site.cfg.py.in
@@ -0,0 +1,10 @@
+@LIT_SITE_CFG_IN_HEADER@
+
+import sys
+
+config.libcxx_src_root = "@LIBCXX_SOURCE_DIR@"
+config.libcxx_obj_root = "@LIBCXX_BINARY_DIR@"
+config.benchmark_args = "@LIBCXX_BENCHMARK_TEST_ARGS@".split(';')
+
+# Let the main config do the real work.
+lit_config.load_config(config, "@LIBCXX_SOURCE_DIR@/benchmarks/lit.cfg.py")
\ No newline at end of file
diff --git a/lib/libcxx/benchmarks/ordered_set.bench.cpp b/lib/libcxx/benchmarks/ordered_set.bench.cpp
new file mode 100644
index 00000000000..b2ef0725b7b
--- /dev/null
+++ b/lib/libcxx/benchmarks/ordered_set.bench.cpp
@@ -0,0 +1,249 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+#include <cstdint>
+#include <memory>
+#include <random>
+#include <set>
+#include <string>
+#include <vector>
+
+#include "CartesianBenchmarks.hpp"
+#include "benchmark/benchmark.h"
+#include "test_macros.h"
+
+namespace {
+
+enum class HitType { Hit, Miss };
+
+struct AllHitTypes : EnumValuesAsTuple<AllHitTypes, HitType, 2> {
+  static constexpr const char* Names[] = {"Hit", "Miss"};
+};
+
+enum class AccessPattern { Ordered, Random };
+
+struct AllAccessPattern
+    : EnumValuesAsTuple<AllAccessPattern, AccessPattern, 2> {
+  static constexpr const char* Names[] = {"Ordered", "Random"};
+};
+
+void sortKeysBy(std::vector<uint64_t>& Keys, AccessPattern AP) {
+  if (AP == AccessPattern::Random) {
+    std::random_device R;
+    std::mt19937 M(R());
+    std::shuffle(std::begin(Keys), std::end(Keys), M);
+  }
+}
+
+struct TestSets {
+  std::vector<std::set<uint64_t> > Sets;
+  std::vector<uint64_t> Keys;
+};
+
+TestSets makeTestingSets(size_t TableSize, size_t NumTables, HitType Hit,
+                         AccessPattern Access) {
+  TestSets R;
+  R.Sets.resize(1);
+
+  for (uint64_t I = 0; I < TableSize; ++I) {
+    R.Sets[0].insert(2 * I);
+    R.Keys.push_back(Hit == HitType::Hit ? 2 * I : 2 * I + 1);
+  }
+  R.Sets.resize(NumTables, R.Sets[0]);
+  sortKeysBy(R.Keys, Access);
+
+  return R;
+}
+
+struct Base {
+  size_t TableSize;
+  size_t NumTables;
+  Base(size_t T, size_t N) : TableSize(T), NumTables(N) {}
+
+  bool skip() const {
+    size_t Total = TableSize * NumTables;
+    return Total < 100 || Total > 1000000;
+  }
+
+  std::string baseName() const {
+    return "_TableSize" + std::to_string(TableSize) + "_NumTables" +
+           std::to_string(NumTables);
+  }
+};
+
+template <class Access>
+struct Create : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    std::vector<uint64_t> Keys(TableSize);
+    std::iota(Keys.begin(), Keys.end(), uint64_t{0});
+    sortKeysBy(Keys, Access());
+
+    while (State.KeepRunningBatch(TableSize * NumTables)) {
+      std::vector<std::set<uint64_t>> Sets(NumTables);
+      for (auto K : Keys) {
+        for (auto& Set : Sets) {
+          benchmark::DoNotOptimize(Set.insert(K));
+        }
+      }
+    }
+  }
+
+  std::string name() const {
+    return "BM_Create" + Access::name() + baseName();
+  }
+};
+
+template <class Hit, class Access>
+struct Find : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access());
+
+    while (State.KeepRunningBatch(TableSize * NumTables)) {
+      for (auto K : Data.Keys) {
+        for (auto& Set : Data.Sets) {
+          benchmark::DoNotOptimize(Set.find(K));
+        }
+      }
+    }
+  }
+
+  std::string name() const {
+    return "BM_Find" + Hit::name() + Access::name() + baseName();
+  }
+};
+
+template <class Hit, class Access>
+struct FindNeEnd : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    auto Data = makeTestingSets(TableSize, NumTables, Hit(), Access());
+
+    while (State.KeepRunningBatch(TableSize * NumTables)) {
+      for (auto K : Data.Keys) {
+        for (auto& Set : Data.Sets) {
+          benchmark::DoNotOptimize(Set.find(K) != Set.end());
+        }
+      }
+    }
+  }
+
+  std::string name() const {
+    return "BM_FindNeEnd" + Hit::name() + Access::name() + baseName();
+  }
+};
+
+template <class Access>
+struct InsertHit : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    auto Data = makeTestingSets(TableSize, NumTables, HitType::Hit, Access());
+
+    while (State.KeepRunningBatch(TableSize * NumTables)) {
+      for (auto K : Data.Keys) {
+        for (auto& Set : Data.Sets) {
+          benchmark::DoNotOptimize(Set.insert(K));
+        }
+      }
+    }
+  }
+
+  std::string name() const {
+    return "BM_InsertHit" + Access::name() + baseName();
+  }
+};
+
+template <class Access>
+struct InsertMissAndErase : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss, Access());
+
+    while (State.KeepRunningBatch(TableSize * NumTables)) {
+      for (auto K : Data.Keys) {
+        for (auto& Set : Data.Sets) {
+          benchmark::DoNotOptimize(Set.erase(Set.insert(K).first));
+        }
+      }
+    }
+  }
+
+  std::string name() const {
+    return "BM_InsertMissAndErase" + Access::name() + baseName();
+  }
+};
+
+struct IterateRangeFor : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss,
+                                AccessPattern::Ordered);
+
+    while (State.KeepRunningBatch(TableSize * NumTables)) {
+      for (auto& Set : Data.Sets) {
+        for (auto& V : Set) {
+          benchmark::DoNotOptimize(V);
+        }
+      }
+    }
+  }
+
+  std::string name() const { return "BM_IterateRangeFor" + baseName(); }
+};
+
+struct IterateBeginEnd : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    auto Data = makeTestingSets(TableSize, NumTables, HitType::Miss,
+                                AccessPattern::Ordered);
+
+    while (State.KeepRunningBatch(TableSize * NumTables)) {
+      for (auto& Set : Data.Sets) {
+        for (auto it = Set.begin(); it != Set.end(); ++it) {
+          benchmark::DoNotOptimize(*it);
+        }
+      }
+    }
+  }
+
+  std::string name() const { return "BM_IterateBeginEnd" + baseName(); }
+};
+
+}  // namespace
+
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+
+  const std::vector<size_t> TableSize{1, 10, 100, 1000, 10000, 100000, 1000000};
+  const std::vector<size_t> NumTables{1, 10, 100, 1000, 10000, 100000, 1000000};
+
+  makeCartesianProductBenchmark<Create, AllAccessPattern>(TableSize, NumTables);
+  makeCartesianProductBenchmark<Find, AllHitTypes, AllAccessPattern>(
+      TableSize, NumTables);
+  makeCartesianProductBenchmark<FindNeEnd, AllHitTypes, AllAccessPattern>(
+      TableSize, NumTables);
+  makeCartesianProductBenchmark<InsertHit, AllAccessPattern>(
+      TableSize, NumTables);
+  makeCartesianProductBenchmark<InsertMissAndErase, AllAccessPattern>(
+      TableSize, NumTables);
+  makeCartesianProductBenchmark<IterateRangeFor>(TableSize, NumTables);
+  makeCartesianProductBenchmark<IterateBeginEnd>(TableSize, NumTables);
+  benchmark::RunSpecifiedBenchmarks();
+}
diff --git a/lib/libcxx/benchmarks/string.bench.cpp b/lib/libcxx/benchmarks/string.bench.cpp
index 8a09e738d9b..b8f97e6e2c1 100644
--- a/lib/libcxx/benchmarks/string.bench.cpp
+++ b/lib/libcxx/benchmarks/string.bench.cpp
@@ -1,9 +1,12 @@
-#include <unordered_set>
-#include <vector>
+
 #include <cstdint>
+#include <new>
+#include <vector>
 
-#include "benchmark/benchmark.h"
+#include "CartesianBenchmarks.hpp"
 #include "GenerateInput.hpp"
+#include "benchmark/benchmark.h"
+#include "test_macros.h"
 
 constexpr std::size_t MAX_STRING_LEN = 8 << 14;
 
@@ -11,7 +14,7 @@ constexpr std::size_t MAX_STRING_LEN = 8 << 14;
 static void BM_StringFindNoMatch(benchmark::State &state) {
   std::string s1(state.range(0), '-');
   std::string s2(8, '*');
-  while (state.KeepRunning())
+  for (auto _ : state)
     benchmark::DoNotOptimize(s1.find(s2));
 }
 BENCHMARK(BM_StringFindNoMatch)->Range(10, MAX_STRING_LEN);
@@ -20,7 +23,7 @@ BENCHMARK(BM_StringFindNoMatch)->Range(10, MAX_STRING_LEN);
 static void BM_StringFindAllMatch(benchmark::State &state) {
   std::string s1(MAX_STRING_LEN, '-');
   std::string s2(state.range(0), '-');
-  while (state.KeepRunning())
+  for (auto _ : state)
     benchmark::DoNotOptimize(s1.find(s2));
 }
 BENCHMARK(BM_StringFindAllMatch)->Range(1, MAX_STRING_LEN);
@@ -30,7 +33,7 @@ static void BM_StringFindMatch1(benchmark::State &state) {
   std::string s1(MAX_STRING_LEN / 2, '*');
   s1 += std::string(state.range(0), '-');
   std::string s2(state.range(0), '-');
-  while (state.KeepRunning())
+  for (auto _ : state)
     benchmark::DoNotOptimize(s1.find(s2));
 }
 BENCHMARK(BM_StringFindMatch1)->Range(1, MAX_STRING_LEN / 4);
@@ -41,30 +44,332 @@ static void BM_StringFindMatch2(benchmark::State &state) {
   s1 += std::string(state.range(0), '-');
   s1 += std::string(state.range(0), '*');
   std::string s2(state.range(0), '-');
-  while (state.KeepRunning())
+  for (auto _ : state)
     benchmark::DoNotOptimize(s1.find(s2));
 }
 BENCHMARK(BM_StringFindMatch2)->Range(1, MAX_STRING_LEN / 4);
 
 static void BM_StringCtorDefault(benchmark::State &state) {
-  while (state.KeepRunning()) {
-    for (unsigned I=0; I < 1000; ++I) {
-      std::string Default;
-      benchmark::DoNotOptimize(Default.c_str());
-    }
+  for (auto _ : state) {
+    std::string Default;
+    benchmark::DoNotOptimize(Default);
   }
 }
 BENCHMARK(BM_StringCtorDefault);
 
-static void BM_StringCtorCStr(benchmark::State &state) {
-  std::string Input = getRandomString(state.range(0));
-  const char *Str = Input.c_str();
-  benchmark::DoNotOptimize(Str);
-  while (state.KeepRunning()) {
-    std::string Tmp(Str);
-    benchmark::DoNotOptimize(Tmp.c_str());
+enum class Length { Empty, Small, Large, Huge };
+struct AllLengths : EnumValuesAsTuple<AllLengths, Length, 4> {
+  static constexpr const char* Names[] = {"Empty", "Small", "Large", "Huge"};
+};
+
+enum class Opacity { Opaque, Transparent };
+struct AllOpacity : EnumValuesAsTuple<AllOpacity, Opacity, 2> {
+  static constexpr const char* Names[] = {"Opaque", "Transparent"};
+};
+
+enum class DiffType { Control, ChangeFirst, ChangeMiddle, ChangeLast };
+struct AllDiffTypes : EnumValuesAsTuple<AllDiffTypes, DiffType, 4> {
+  static constexpr const char* Names[] = {"Control", "ChangeFirst",
+                                          "ChangeMiddle", "ChangeLast"};
+};
+
+TEST_ALWAYS_INLINE const char* getSmallString(DiffType D) {
+  switch (D) {
+    case DiffType::Control:
+      return "0123456";
+    case DiffType::ChangeFirst:
+      return "-123456";
+    case DiffType::ChangeMiddle:
+      return "012-456";
+    case DiffType::ChangeLast:
+      return "012345-";
+  }
+}
+
+TEST_ALWAYS_INLINE const char* getLargeString(DiffType D) {
+#define LARGE_STRING_FIRST "123456789012345678901234567890"
+#define LARGE_STRING_SECOND "234567890123456789012345678901"
+  switch (D) {
+    case DiffType::Control:
+      return "0" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "2";
+    case DiffType::ChangeFirst:
+      return "-" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "2";
+    case DiffType::ChangeMiddle:
+      return "0" LARGE_STRING_FIRST "-" LARGE_STRING_SECOND "2";
+    case DiffType::ChangeLast:
+      return "0" LARGE_STRING_FIRST "1" LARGE_STRING_SECOND "-";
+  }
+}
+
+TEST_ALWAYS_INLINE const char* getHugeString(DiffType D) {
+#define HUGE_STRING0 "0123456789"
+#define HUGE_STRING1 HUGE_STRING0 HUGE_STRING0 HUGE_STRING0 HUGE_STRING0
+#define HUGE_STRING2 HUGE_STRING1 HUGE_STRING1 HUGE_STRING1 HUGE_STRING1
+#define HUGE_STRING3 HUGE_STRING2 HUGE_STRING2 HUGE_STRING2 HUGE_STRING2
+#define HUGE_STRING4 HUGE_STRING3 HUGE_STRING3 HUGE_STRING3 HUGE_STRING3
+  switch (D) {
+    case DiffType::Control:
+      return "0123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "0123456789";
+    case DiffType::ChangeFirst:
+      return "-123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "0123456789";
+    case DiffType::ChangeMiddle:
+      return "0123456789" HUGE_STRING4 "01234-6789" HUGE_STRING4 "0123456789";
+    case DiffType::ChangeLast:
+      return "0123456789" HUGE_STRING4 "0123456789" HUGE_STRING4 "012345678-";
+  }
+}
+
+TEST_ALWAYS_INLINE std::string makeString(Length L,
+                                          DiffType D = DiffType::Control,
+                                          Opacity O = Opacity::Transparent) {
+  switch (L) {
+  case Length::Empty:
+    return maybeOpaque("", O == Opacity::Opaque);
+  case Length::Small:
+    return maybeOpaque(getSmallString(D), O == Opacity::Opaque);
+  case Length::Large:
+    return maybeOpaque(getLargeString(D), O == Opacity::Opaque);
+  case Length::Huge:
+    return maybeOpaque(getHugeString(D), O == Opacity::Opaque);
+  }
+}
+
+template <class Length, class Opaque>
+struct StringConstructDestroyCStr {
+  static void run(benchmark::State& state) {
+    for (auto _ : state) {
+      benchmark::DoNotOptimize(
+          makeString(Length(), DiffType::Control, Opaque()));
+    }
+  }
+
+  static std::string name() {
+    return "BM_StringConstructDestroyCStr" + Length::name() + Opaque::name();
+  }
+};
+
+template <class Length, bool MeasureCopy, bool MeasureDestroy>
+static void StringCopyAndDestroy(benchmark::State& state) {
+  static constexpr size_t NumStrings = 1024;
+  auto Orig = makeString(Length());
+  std::aligned_storage<sizeof(std::string)>::type Storage[NumStrings];
+
+  while (state.KeepRunningBatch(NumStrings)) {
+    if (!MeasureCopy)
+      state.PauseTiming();
+    for (size_t I = 0; I < NumStrings; ++I) {
+      ::new (static_cast<void*>(Storage + I)) std::string(Orig);
+    }
+    if (!MeasureCopy)
+      state.ResumeTiming();
+    if (!MeasureDestroy)
+      state.PauseTiming();
+    for (size_t I = 0; I < NumStrings; ++I) {
+      using S = std::string;
+      reinterpret_cast<S*>(Storage + I)->~S();
+    }
+    if (!MeasureDestroy)
+      state.ResumeTiming();
+  }
+}
+
+template <class Length>
+struct StringCopy {
+  static void run(benchmark::State& state) {
+    StringCopyAndDestroy<Length, true, false>(state);
+  }
+
+  static std::string name() { return "BM_StringCopy" + Length::name(); }
+};
+
+template <class Length>
+struct StringDestroy {
+  static void run(benchmark::State& state) {
+    StringCopyAndDestroy<Length, false, true>(state);
+  }
+
+  static std::string name() { return "BM_StringDestroy" + Length::name(); }
+};
+
+template <class Length>
+struct StringMove {
+  static void run(benchmark::State& state) {
+    // Keep two object locations and move construct back and forth.
+    std::aligned_storage<sizeof(std::string), alignof(std::string)>::type Storage[2];
+    using S = std::string;
+    size_t I = 0;
+    S *newS = new (static_cast<void*>(Storage)) std::string(makeString(Length()));
+    for (auto _ : state) {
+      // Switch locations.
+      I ^= 1;
+      benchmark::DoNotOptimize(Storage);
+      // Move construct into the new location,
+      S *tmpS = new (static_cast<void*>(Storage + I)) S(std::move(*newS));
+      // then destroy the old one.
+      newS->~S();
+      newS = tmpS;
+    }
+    newS->~S();
+  }
+
+  static std::string name() { return "BM_StringMove" + Length::name(); }
+};
+
+enum class Relation { Eq, Less, Compare };
+struct AllRelations : EnumValuesAsTuple<AllRelations, Relation, 3> {
+  static constexpr const char* Names[] = {"Eq", "Less", "Compare"};
+};
+
+template <class Rel, class LHLength, class RHLength, class DiffType>
+struct StringRelational {
+  static void run(benchmark::State& state) {
+    auto Lhs = makeString(RHLength());
+    auto Rhs = makeString(LHLength(), DiffType());
+    for (auto _ : state) {
+      benchmark::DoNotOptimize(Lhs);
+      benchmark::DoNotOptimize(Rhs);
+      switch (Rel()) {
+      case Relation::Eq:
+        benchmark::DoNotOptimize(Lhs == Rhs);
+        break;
+      case Relation::Less:
+        benchmark::DoNotOptimize(Lhs < Rhs);
+        break;
+      case Relation::Compare:
+        benchmark::DoNotOptimize(Lhs.compare(Rhs));
+        break;
+      }
+    }
+  }
+
+  static bool skip() {
+    // Eq is commutative, so skip half the matrix.
+    if (Rel() == Relation::Eq && LHLength() > RHLength())
+      return true;
+    // We only care about control when the lengths differ.
+    if (LHLength() != RHLength() && DiffType() != ::DiffType::Control)
+      return true;
+    // For empty, only control matters.
+    if (LHLength() == Length::Empty && DiffType() != ::DiffType::Control)
+      return true;
+    return false;
+  }
+
+  static std::string name() {
+    return "BM_StringRelational" + Rel::name() + LHLength::name() +
+           RHLength::name() + DiffType::name();
+  }
+};
+
+enum class Depth { Shallow, Deep };
+struct AllDepths : EnumValuesAsTuple<AllDepths, Depth, 2> {
+  static constexpr const char* Names[] = {"Shallow", "Deep"};
+};
+
+enum class Temperature { Hot, Cold };
+struct AllTemperatures : EnumValuesAsTuple<AllTemperatures, Temperature, 2> {
+  static constexpr const char* Names[] = {"Hot", "Cold"};
+};
+
+template <class Temperature, class Depth, class Length>
+struct StringRead {
+  void run(benchmark::State& state) const {
+    static constexpr size_t NumStrings =
+        Temperature() == ::Temperature::Hot
+            ? 1 << 10
+            : /* Enough strings to overflow the cache */ 1 << 20;
+    static_assert((NumStrings & (NumStrings - 1)) == 0,
+                  "NumStrings should be a power of two to reduce overhead.");
+
+    std::vector<std::string> Values(NumStrings, makeString(Length()));
+    size_t I = 0;
+    for (auto _ : state) {
+      // Jump long enough to defeat cache locality, and use a value that is
+      // coprime with NumStrings to ensure we visit every element.
+      I = (I + 17) % NumStrings;
+      const auto& V = Values[I];
+
+      // Read everything first. Escaping data() through DoNotOptimize might
+      // cause the compiler to have to recalculate information about `V` due to
+      // aliasing.
+      const char* const Data = V.data();
+      const size_t Size = V.size();
+      benchmark::DoNotOptimize(Data);
+      benchmark::DoNotOptimize(Size);
+      if (Depth() == ::Depth::Deep) {
+        // Read into the payload. This mainly shows the benefit of SSO when the
+        // data is cold.
+        benchmark::DoNotOptimize(*Data);
+      }
+    }
+  }
+
+  static bool skip() {
+    // Huge does not give us anything that Large doesn't have. Skip it.
+    if (Length() == ::Length::Huge) {
+      return true;
+    }
+    return false;
+  }
+
+  std::string name() const {
+    return "BM_StringRead" + Temperature::name() + Depth::name() +
+           Length::name();
+  }
+};
+
+void sanityCheckGeneratedStrings() {
+  for (auto Lhs : {Length::Empty, Length::Small, Length::Large, Length::Huge}) {
+    const auto LhsString = makeString(Lhs);
+    for (auto Rhs :
+         {Length::Empty, Length::Small, Length::Large, Length::Huge}) {
+      if (Lhs > Rhs)
+        continue;
+      const auto RhsString = makeString(Rhs);
+
+      // The smaller one must be a prefix of the larger one.
+      if (RhsString.find(LhsString) != 0) {
+        fprintf(stderr, "Invalid autogenerated strings for sizes (%d,%d).\n",
+                static_cast<int>(Lhs), static_cast<int>(Rhs));
+        std::abort();
+      }
+    }
+  }
+  // Verify the autogenerated diffs
+  for (auto L : {Length::Small, Length::Large, Length::Huge}) {
+    const auto Control = makeString(L);
+    const auto Verify = [&](std::string Exp, size_t Pos) {
+      // Only change on the Pos char.
+      if (Control[Pos] != Exp[Pos]) {
+        Exp[Pos] = Control[Pos];
+        if (Control == Exp)
+          return;
+      }
+      fprintf(stderr, "Invalid autogenerated diff with size %d\n",
+              static_cast<int>(L));
+      std::abort();
+    };
+    Verify(makeString(L, DiffType::ChangeFirst), 0);
+    Verify(makeString(L, DiffType::ChangeMiddle), Control.size() / 2);
+    Verify(makeString(L, DiffType::ChangeLast), Control.size() - 1);
   }
 }
-BENCHMARK(BM_StringCtorCStr)->Arg(1)->Arg(8)->Range(16, MAX_STRING_LEN / 4);
 
-BENCHMARK_MAIN();
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+
+  sanityCheckGeneratedStrings();
+
+  makeCartesianProductBenchmark<StringConstructDestroyCStr, AllLengths,
+                                AllOpacity>();
+  makeCartesianProductBenchmark<StringCopy, AllLengths>();
+  makeCartesianProductBenchmark<StringMove, AllLengths>();
+  makeCartesianProductBenchmark<StringDestroy, AllLengths>();
+  makeCartesianProductBenchmark<StringRelational, AllRelations, AllLengths,
+                                AllLengths, AllDiffTypes>();
+  makeCartesianProductBenchmark<StringRead, AllTemperatures, AllDepths,
+                                AllLengths>();
+  benchmark::RunSpecifiedBenchmarks();
+}
diff --git a/lib/libcxx/benchmarks/stringstream.bench.cpp b/lib/libcxx/benchmarks/stringstream.bench.cpp
index 75a7a284e07..828ef4b405f 100644
--- a/lib/libcxx/benchmarks/stringstream.bench.cpp
+++ b/lib/libcxx/benchmarks/stringstream.bench.cpp
@@ -1,7 +1,9 @@
 #include "benchmark/benchmark.h"
+#include "test_macros.h"
 
 #include <sstream>
-double __attribute__((noinline)) istream_numbers();
+
+TEST_NOINLINE double istream_numbers();
 
 double istream_numbers() {
   const char *a[] = {
diff --git a/lib/libcxx/benchmarks/unordered_set_operations.bench.cpp b/lib/libcxx/benchmarks/unordered_set_operations.bench.cpp
index ee0ea29b8d2..1fee6d362c4 100644
--- a/lib/libcxx/benchmarks/unordered_set_operations.bench.cpp
+++ b/lib/libcxx/benchmarks/unordered_set_operations.bench.cpp
@@ -9,25 +9,26 @@
 
 #include "ContainerBenchmarks.hpp"
 #include "GenerateInput.hpp"
+#include "test_macros.h"
 
 using namespace ContainerBenchmarks;
 
 constexpr std::size_t TestNumInputs = 1024;
 
 template <class _Size>
-inline __attribute__((__always_inline__))
+inline TEST_ALWAYS_INLINE
 _Size loadword(const void* __p) {
     _Size __r;
     std::memcpy(&__r, __p, sizeof(__r));
     return __r;
 }
 
-inline __attribute__((__always_inline__))
+inline TEST_ALWAYS_INLINE
 std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) {
     return (__val >> __shift) | (__val << (64 - __shift));
 }
 
-inline __attribute__((__always_inline__))
+inline TEST_ALWAYS_INLINE
 std::size_t hash_len_16(std::size_t __u, std::size_t __v) {
     const  std::size_t __mul = 0x9ddfea08eb382d69ULL;
     std::size_t __a = (__u ^ __v) * __mul;
@@ -40,7 +41,7 @@ std::size_t hash_len_16(std::size_t __u, std::size_t __v) {
 
 
 template <std::size_t _Len>
-inline __attribute__((__always_inline__))
+inline TEST_ALWAYS_INLINE
 std::size_t hash_len_0_to_8(const char* __s) {
     static_assert(_Len == 4 || _Len == 8, "");
     const uint64_t __a = loadword<uint32_t>(__s);
@@ -50,7 +51,7 @@ std::size_t hash_len_0_to_8(const char* __s) {
 
 struct UInt32Hash {
   UInt32Hash() = default;
-  inline __attribute__((__always_inline__))
+  inline TEST_ALWAYS_INLINE
   std::size_t operator()(uint32_t data) const {
       return hash_len_0_to_8<4>(reinterpret_cast<const char*>(&data));
   }
@@ -58,7 +59,7 @@ struct UInt32Hash {
 
 struct UInt64Hash {
   UInt64Hash() = default;
-  inline __attribute__((__always_inline__))
+  inline TEST_ALWAYS_INLINE
   std::size_t operator()(uint64_t data) const {
       return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
   }
@@ -66,7 +67,7 @@ struct UInt64Hash {
 
 struct UInt128Hash {
   UInt128Hash() = default;
-  inline __attribute__((__always_inline__))
+  inline TEST_ALWAYS_INLINE
   std::size_t operator()(__uint128_t data) const {
       const __uint128_t __mask = static_cast<std::size_t>(-1);
       const std::size_t __a = (std::size_t)(data & __mask);
@@ -77,7 +78,7 @@ struct UInt128Hash {
 
 struct UInt32Hash2 {
   UInt32Hash2() = default;
-  inline __attribute__((__always_inline__))
+  inline TEST_ALWAYS_INLINE
   std::size_t operator()(uint32_t data) const {
       const uint32_t __m = 0x5bd1e995;
       const uint32_t __r = 24;
@@ -97,7 +98,7 @@ struct UInt32Hash2 {
 
 struct UInt64Hash2 {
   UInt64Hash2() = default;
-  inline __attribute__((__always_inline__))
+  inline TEST_ALWAYS_INLINE
   std::size_t operator()(uint64_t data) const {
       return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
   }