Improve codegen for deque.
authorEric Fiselier <eric@efcs.ca>
Mon, 12 Aug 2019 07:51:05 +0000 (07:51 +0000)
committerEric Fiselier <eric@efcs.ca>
Mon, 12 Aug 2019 07:51:05 +0000 (07:51 +0000)
commitb0945e1bd2e2d7ac6dd8152e479a56db302d981e
treedc9395039df5dd3272da9cc49c1f4e7b244a0cc1
parentfd5ea1b0d904dc8f9793fcdf7699d10009f6a45f
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
libcxx/benchmarks/ContainerBenchmarks.hpp
libcxx/benchmarks/Utilities.hpp [new file with mode: 0644]
libcxx/benchmarks/deque.bench.cpp [new file with mode: 0644]
libcxx/include/__split_buffer
libcxx/include/deque