llvm weekly 256 - combine interleaved loads

Weekly256

Interested in:
[libcxx] Add docker configurations used by the buildbots.
[PATCH] [CodeGen] Add pass to combine interleaved loads.

/// First Order Polynomial on an n-Bit Integer Value
///
/// Polynomial(Value) = Value * B + A + E*2^(n-e)
///
/// A and B are the coefficients. E*2^(n-e) is an error within 'e' most
/// significant bits. It is introduced if an exact computation cannot be proven
/// (e.q. division by 2).
class Polynomial {
  /// Operations on B
  enum BOps {
    LShr,
    Mul,
    SExt,
    Trunc,
  };

  /// Number of Error Bits e
  unsigned ErrorMSBs;

  /// Value
  Value *V;

  /// Coefficient B
  SmallVector<std::pair<BOps, APInt>, 4> B;

  /// Coefficient A
  APInt A;
  ..
};

[libcxx] Add benchmarks for sorting and heap functions.

• Why not directly use 'uint32_t', 'std::string', .., but wrap these types by 'ValueType'?
  (need to check makeCartesianProductBenchmark)

// Code Snippet from: https://reviews.llvm.org/rL347329
// Author: sbenza

enum class ValueType { Uint32, String };
struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 2> {
  static constexpr const char* Names[] = {"uint32", "string"};
};

/** conditional (since c++11)
    conditional_t (since c++14) 

    template< bool B, class T, class F > struct conditional;
    template< bool B, class T, class F >
        using conditional_t = typename conditional::type;

    if (B) return type T
    else   return type F
  */

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"};
};

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;
  }
}

void fillValues(std::vector<uint32_t>& V, size_t N, Order O) { .. }
void fillValues(std::vector<std::string>& V, size_t N, Order O) { .. }

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;

  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 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);
  }
}

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 {
  ...
  void run(benchmark::State& state) const {
    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
      std::stable_sort(Copy.begin(), Copy.end());
    });
  }
  ...
};

template <class ValueType, class Order>
struct MakeHeap { ... };

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);
  ..
}