Improve codegen for deque.

This patch rewrites a few loops in deque and split_buffer to better
optimize the codegen. For constructors like
`deque<unsigned char> d(500000, 0);` this patch results in a 2x speedup.

The patch improves the codegen  in roughly three ways:

1. Changes do { ... } while (...) loops into more typical for loops.
  The optimizer can reason about normal looking loops better.

2. Split the iteration over a range into (A) iteration over the blocks,
then (B) iteration within the block. This nested structure helps LLVM
lower the inner loop to `memset`.

3. Do fewer things each iteration. Some of these loops were incrementing
  or changing 4-5 variables every loop (in addition to the
  construction). Previously most loops would increment the end pointer,
  the size, and decrement the count of remaining items to construct.
  Now we only increment a single pointer for most iterations.

llvm-svn: 368547

3 files changed, 93 insertions, 3 deletions

diff --git a/libcxx/benchmarks/ContainerBenchmarks.hpp b/libcxx/benchmarks/ContainerBenchmarks.hpp
index 648617a9cd2..581d3c53e60 100644
--- a/libcxx/benchmarks/ContainerBenchmarks.hpp
+++ b/libcxx/benchmarks/ContainerBenchmarks.hpp
@@ -1,8 +1,18 @@
+// -*- 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
+//
+//===----------------------------------------------------------------------===//
+
 #ifndef BENCHMARK_CONTAINER_BENCHMARKS_HPP
 #define BENCHMARK_CONTAINER_BENCHMARKS_HPP
 
 #include <cassert>
 
+#include "Utilities.hpp"
 #include "benchmark/benchmark.h"
 
 namespace ContainerBenchmarks {
@@ -12,7 +22,7 @@ void BM_ConstructSize(benchmark::State& st, Container) {
   auto size = st.range(0);
   for (auto _ : st) {
     Container c(size);
-    benchmark::DoNotOptimize(c.data());
+    DoNotOptimizeData(c);
   }
 }
 
@@ -21,7 +31,7 @@ void BM_ConstructSizeValue(benchmark::State& st, Container, typename Container::
   const auto size = st.range(0);
   for (auto _ : st) {
     Container c(size, val);
-    benchmark::DoNotOptimize(c.data());
+    DoNotOptimizeData(c);
   }
 }
 
@@ -33,7 +43,7 @@ void BM_ConstructIterIter(benchmark::State& st, Container, GenInputs gen) {
     benchmark::DoNotOptimize(&in);
     while (st.KeepRunning()) {
         Container c(begin, end);
-        benchmark::DoNotOptimize(c.data());
+        DoNotOptimizeData(c);
     }
 }
 
diff --git a/libcxx/benchmarks/Utilities.hpp b/libcxx/benchmarks/Utilities.hpp
new file mode 100644
index 00000000000..1b25f746dda
--- /dev/null
+++ b/libcxx/benchmarks/Utilities.hpp
@@ -0,0 +1,33 @@
+// -*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef BENCHMARK_UTILITIES_HPP
+#define BENCHMARK_UTILITIES_HPP
+
+#include <cassert>
+#include <type_traits>
+
+#include "benchmark/benchmark.h"
+
+namespace UtilitiesInternal {
+  template <class Container>
+  auto HaveDataImpl(int) -> decltype((std::declval<Container&>().data(), std::true_type{}));
+  template <class Container>
+  auto HaveDataImpl(long) -> std::false_type;
+  template <class T>
+  using HasData = decltype(HaveDataImpl<T>(0));
+} // namespace UtilitiesInternal
+
+template <class Container, std::enable_if_t<UtilitiesInternal::HasData<Container>::value>* = nullptr>
+void DoNotOptimizeData(Container &c) { benchmark::DoNotOptimize(c.data()); }
+template <class Container, std::enable_if_t<!UtilitiesInternal::HasData<Container>::value>* = nullptr>
+void DoNotOptimizeData(Container &c) { benchmark::DoNotOptimize(&c); }
+
+
+#endif // BENCHMARK_UTILITIES_HPP
diff --git a/libcxx/benchmarks/deque.bench.cpp b/libcxx/benchmarks/deque.bench.cpp
new file mode 100644
index 00000000000..44a492b7b3d
--- /dev/null
+++ b/libcxx/benchmarks/deque.bench.cpp
@@ -0,0 +1,47 @@
+// -*- 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 <deque>
+
+#include "benchmark/benchmark.h"
+
+#include "ContainerBenchmarks.hpp"
+#include "GenerateInput.hpp"
+
+using namespace ContainerBenchmarks;
+
+constexpr std::size_t TestNumInputs = 1024;
+
+BENCHMARK_CAPTURE(BM_ConstructSize,
+    deque_byte,
+    std::deque<unsigned char>{})->Arg(5140480);
+
+BENCHMARK_CAPTURE(BM_ConstructSizeValue,
+    deque_byte,
+    std::deque<unsigned char>{}, 0)->Arg(5140480);
+
+BENCHMARK_CAPTURE(BM_ConstructIterIter,
+  deque_char,
+  std::deque<char>{},
+  getRandomIntegerInputs<char>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_ConstructIterIter,
+  deque_size_t,
+  std::deque<size_t>{},
+  getRandomIntegerInputs<size_t>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_ConstructIterIter,
+  deque_string,
+  std::deque<std::string>{},
+  getRandomStringInputs)->Arg(TestNumInputs);
+
+
+
+
+BENCHMARK_MAIN();