LCOV - code coverage report
Current view: top level - include/llvm/Support - Parallel.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 72 73 98.6 %
Date: 2017-09-14 15:23:50 Functions: 25 38 65.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/Support/Parallel.h - Parallel algorithms ----------------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : 
      10             : #ifndef LLVM_SUPPORT_PARALLEL_H
      11             : #define LLVM_SUPPORT_PARALLEL_H
      12             : 
      13             : #include "llvm/ADT/STLExtras.h"
      14             : #include "llvm/Config/llvm-config.h"
      15             : #include "llvm/Support/MathExtras.h"
      16             : 
      17             : #include <algorithm>
      18             : #include <condition_variable>
      19             : #include <functional>
      20             : #include <mutex>
      21             : 
      22             : #if defined(_MSC_VER) && LLVM_ENABLE_THREADS
      23             : #pragma warning(push)
      24             : #pragma warning(disable : 4530)
      25             : #include <concrt.h>
      26             : #include <ppl.h>
      27             : #pragma warning(pop)
      28             : #endif
      29             : 
      30             : namespace llvm {
      31             : 
      32             : namespace parallel {
      33             : struct sequential_execution_policy {};
      34             : struct parallel_execution_policy {};
      35             : 
      36             : template <typename T>
      37             : struct is_execution_policy
      38             :     : public std::integral_constant<
      39             :           bool, llvm::is_one_of<T, sequential_execution_policy,
      40             :                                 parallel_execution_policy>::value> {};
      41             : 
      42             : constexpr sequential_execution_policy seq{};
      43             : constexpr parallel_execution_policy par{};
      44             : 
      45             : namespace detail {
      46             : 
      47             : #if LLVM_ENABLE_THREADS
      48             : 
      49             : class Latch {
      50             :   uint32_t Count;
      51             :   mutable std::mutex Mutex;
      52             :   mutable std::condition_variable Cond;
      53             : 
      54             : public:
      55      428192 :   explicit Latch(uint32_t Count = 0) : Count(Count) {}
      56      214096 :   ~Latch() { sync(); }
      57             : 
      58       26853 :   void inc() {
      59       80566 :     std::unique_lock<std::mutex> lock(Mutex);
      60       26857 :     ++Count;
      61       26856 :   }
      62             : 
      63       40577 :   void dec() {
      64      121747 :     std::unique_lock<std::mutex> lock(Mutex);
      65       40585 :     if (--Count == 0)
      66        7847 :       Cond.notify_all();
      67       40585 :   }
      68             : 
      69      214096 :   void sync() const {
      70      642288 :     std::unique_lock<std::mutex> lock(Mutex);
      71      428192 :     Cond.wait(lock, [&] { return Count == 0; });
      72      214096 :   }
      73             : };
      74             : 
      75      849520 : class TaskGroup {
      76             :   Latch L;
      77             : 
      78             : public:
      79             :   void spawn(std::function<void()> f);
      80             : 
      81             :   void sync() const { L.sync(); }
      82             : };
      83             : 
      84             : #if defined(_MSC_VER)
      85             : template <class RandomAccessIterator, class Comparator>
      86             : void parallel_sort(RandomAccessIterator Start, RandomAccessIterator End,
      87             :                    const Comparator &Comp) {
      88             :   concurrency::parallel_sort(Start, End, Comp);
      89             : }
      90             : template <class IterTy, class FuncTy>
      91             : void parallel_for_each(IterTy Begin, IterTy End, FuncTy Fn) {
      92             :   concurrency::parallel_for_each(Begin, End, Fn);
      93             : }
      94             : 
      95             : template <class IndexTy, class FuncTy>
      96             : void parallel_for_each_n(IndexTy Begin, IndexTy End, FuncTy Fn) {
      97             :   concurrency::parallel_for(Begin, End, Fn);
      98             : }
      99             : 
     100             : #else
     101             : const ptrdiff_t MinParallelSize = 1024;
     102             : 
     103             : /// \brief Inclusive median.
     104             : template <class RandomAccessIterator, class Comparator>
     105        1762 : RandomAccessIterator medianOf3(RandomAccessIterator Start,
     106             :                                RandomAccessIterator End,
     107             :                                const Comparator &Comp) {
     108        1762 :   RandomAccessIterator Mid = Start + (std::distance(Start, End) / 2);
     109        1762 :   return Comp(*Start, *(End - 1))
     110        1762 :              ? (Comp(*Mid, *(End - 1)) ? (Comp(*Start, *Mid) ? Mid : Start)
     111             :                                        : End - 1)
     112         864 :              : (Comp(*Mid, *Start) ? (Comp(*(End - 1), *Mid) ? Mid : End - 1)
     113        1762 :                                    : Start);
     114             : }
     115             : 
     116             : template <class RandomAccessIterator, class Comparator>
     117        3715 : void parallel_quick_sort(RandomAccessIterator Start, RandomAccessIterator End,
     118             :                          const Comparator &Comp, TaskGroup &TG, size_t Depth) {
     119             :   // Do a sequential sort for small inputs.
     120        3715 :   if (std::distance(Start, End) < detail::MinParallelSize || Depth == 0) {
     121        1953 :     std::sort(Start, End, Comp);
     122         167 :     return;
     123             :   }
     124             : 
     125             :   // Partition.
     126        1762 :   auto Pivot = medianOf3(Start, End, Comp);
     127             :   // Move Pivot to End.
     128        3524 :   std::swap(*(End - 1), *Pivot);
     129     7893035 :   Pivot = std::partition(Start, End - 1, [&Comp, End](decltype(*Start) V) {
     130           0 :     return Comp(V, *(End - 1));
     131     7889511 :   });
     132             :   // Move Pivot to middle of partition.
     133        3524 :   std::swap(*Pivot, *(End - 1));
     134             : 
     135             :   // Recurse.
     136        8806 :   TG.spawn([=, &Comp, &TG] {
     137        3524 :     parallel_quick_sort(Start, Pivot, Comp, TG, Depth - 1);
     138        1756 :   });
     139        1762 :   parallel_quick_sort(Pivot + 1, End, Comp, TG, Depth - 1);
     140             : }
     141             : 
     142             : template <class RandomAccessIterator, class Comparator>
     143         192 : void parallel_sort(RandomAccessIterator Start, RandomAccessIterator End,
     144             :                    const Comparator &Comp) {
     145         384 :   TaskGroup TG;
     146         192 :   parallel_quick_sort(Start, End, Comp, TG,
     147         384 :                       llvm::Log2_64(std::distance(Start, End)) + 1);
     148         192 : }
     149             : 
     150             : template <class IterTy, class FuncTy>
     151        3583 : void parallel_for_each(IterTy Begin, IterTy End, FuncTy Fn) {
     152             :   // TaskGroup has a relatively high overhead, so we want to reduce
     153             :   // the number of spawn() calls. We'll create up to 1024 tasks here.
     154             :   // (Note that 1024 is an arbitrary number. This code probably needs
     155             :   // improving to take the number of available cores into account.)
     156        3583 :   ptrdiff_t TaskSize = std::distance(Begin, End) / 1024;
     157        3583 :   if (TaskSize == 0)
     158        3577 :     TaskSize = 1;
     159             : 
     160        3583 :   TaskGroup TG;
     161       26627 :   while (TaskSize < std::distance(Begin, End)) {
     162      138270 :     TG.spawn([=, &Fn] { std::for_each(Begin, Begin + TaskSize, Fn); });
     163             :     Begin += TaskSize;
     164             :   }
     165        3583 :   std::for_each(Begin, End, Fn);
     166        3583 : }
     167             : 
     168             : template <class IndexTy, class FuncTy>
     169      208605 : void parallel_for_each_n(IndexTy Begin, IndexTy End, FuncTy Fn) {
     170      208605 :   ptrdiff_t TaskSize = (End - Begin) / 1024;
     171      208605 :   if (TaskSize == 0)
     172      208604 :     TaskSize = 1;
     173             : 
     174      417210 :   TaskGroup TG;
     175      208605 :   IndexTy I = Begin;
     176      212707 :   for (; I + TaskSize < End; I += TaskSize) {
     177       10251 :     TG.spawn([=, &Fn] {
     178        5126 :       for (IndexTy J = I, E = I + TaskSize; J != E; ++J)
     179        5123 :         Fn(J);
     180        1023 :     });
     181             :   }
     182      625801 :   for (IndexTy J = I; J < End; ++J)
     183      208599 :     Fn(J);
     184      208605 : }
     185             : 
     186             : #endif
     187             : 
     188             : #endif
     189             : 
     190             : template <typename Iter>
     191             : using DefComparator =
     192             :     std::less<typename std::iterator_traits<Iter>::value_type>;
     193             : 
     194             : } // namespace detail
     195             : 
     196             : // sequential algorithm implementations.
     197             : template <class Policy, class RandomAccessIterator,
     198             :           class Comparator = detail::DefComparator<RandomAccessIterator>>
     199             : void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End,
     200             :           const Comparator &Comp = Comparator()) {
     201             :   static_assert(is_execution_policy<Policy>::value,
     202             :                 "Invalid execution policy!");
     203             :   std::sort(Start, End, Comp);
     204             : }
     205             : 
     206             : template <class Policy, class IterTy, class FuncTy>
     207             : void for_each(Policy policy, IterTy Begin, IterTy End, FuncTy Fn) {
     208             :   static_assert(is_execution_policy<Policy>::value,
     209             :                 "Invalid execution policy!");
     210             :   std::for_each(Begin, End, Fn);
     211             : }
     212             : 
     213             : template <class Policy, class IndexTy, class FuncTy>
     214          32 : void for_each_n(Policy policy, IndexTy Begin, IndexTy End, FuncTy Fn) {
     215             :   static_assert(is_execution_policy<Policy>::value,
     216             :                 "Invalid execution policy!");
     217          64 :   for (IndexTy I = Begin; I != End; ++I)
     218          32 :     Fn(I);
     219          32 : }
     220             : 
     221             : // Parallel algorithm implementations, only available when LLVM_ENABLE_THREADS
     222             : // is true.
     223             : #if LLVM_ENABLE_THREADS
     224             : template <class RandomAccessIterator,
     225             :           class Comparator = detail::DefComparator<RandomAccessIterator>>
     226             : void sort(parallel_execution_policy policy, RandomAccessIterator Start,
     227             :           RandomAccessIterator End, const Comparator &Comp = Comparator()) {
     228         192 :   detail::parallel_sort(Start, End, Comp);
     229             : }
     230             : 
     231             : template <class IterTy, class FuncTy>
     232             : void for_each(parallel_execution_policy policy, IterTy Begin, IterTy End,
     233             :               FuncTy Fn) {
     234        3583 :   detail::parallel_for_each(Begin, End, Fn);
     235             : }
     236             : 
     237             : template <class IndexTy, class FuncTy>
     238      208597 : void for_each_n(parallel_execution_policy policy, IndexTy Begin, IndexTy End,
     239             :                 FuncTy Fn) {
     240      417202 :   detail::parallel_for_each_n(Begin, End, Fn);
     241      208597 : }
     242             : #endif
     243             : 
     244             : } // namespace parallel
     245             : } // namespace llvm
     246             : 
     247             : #endif // LLVM_SUPPORT_PARALLEL_H

Generated by: LCOV version 1.13