Skip to content

Commit 092c767

Browse files
author
Zachary Turner
committedMay 10, 2017
[Core] Make parallel algorithms match C++ Parallelism TS.
Differential Revision: https://reviews.llvm.org/D33016 llvm-svn: 302613
1 parent a09ff59 commit 092c767

File tree

7 files changed

+115
-76
lines changed

7 files changed

+115
-76
lines changed
 

‎lld/COFF/ICF.cpp

+1-1
Original file line numberDiff line numberDiff line change
@@ -192,7 +192,7 @@ void ICF::forEachClass(std::function<void(size_t, size_t)> Fn) {
192192
// Split sections into 256 shards and call Fn in parallel.
193193
size_t NumShards = 256;
194194
size_t Step = Chunks.size() / NumShards;
195-
parallel_for(size_t(0), NumShards, [&](size_t I) {
195+
for_each_n(parallel::par, size_t(0), NumShards, [&](size_t I) {
196196
forEachClassRange(I * Step, (I + 1) * Step, Fn);
197197
});
198198
forEachClassRange(Step * NumShards, Chunks.size(), Fn);

‎lld/COFF/MapFile.cpp

+1-1
Original file line numberDiff line numberDiff line change
@@ -76,7 +76,7 @@ static SymbolMapTy getSectionSyms(ArrayRef<DefinedRegular *> Syms) {
7676
static DenseMap<DefinedRegular *, std::string>
7777
getSymbolStrings(ArrayRef<DefinedRegular *> Syms) {
7878
std::vector<std::string> Str(Syms.size());
79-
parallel_for((size_t)0, Syms.size(), [&](size_t I) {
79+
for_each_n(parallel::par, (size_t)0, Syms.size(), [&](size_t I) {
8080
raw_string_ostream OS(Str[I]);
8181
writeHeader(OS, Syms[I]->getRVA(), 0, 0);
8282
OS << indent(2) << toString(*Syms[I]);

‎lld/COFF/Writer.cpp

+6-8
Original file line numberDiff line numberDiff line change
@@ -745,8 +745,8 @@ void Writer::writeSections() {
745745
// ADD instructions).
746746
if (Sec->getPermissions() & IMAGE_SCN_CNT_CODE)
747747
memset(SecBuf, 0xCC, Sec->getRawSize());
748-
parallel_for_each(Sec->getChunks().begin(), Sec->getChunks().end(),
749-
[&](Chunk *C) { C->writeTo(SecBuf); });
748+
for_each(parallel::par, Sec->getChunks().begin(), Sec->getChunks().end(),
749+
[&](Chunk *C) { C->writeTo(SecBuf); });
750750
}
751751
}
752752

@@ -760,16 +760,14 @@ void Writer::sortExceptionTable() {
760760
uint8_t *End = Begin + Sec->getVirtualSize();
761761
if (Config->Machine == AMD64) {
762762
struct Entry { ulittle32_t Begin, End, Unwind; };
763-
parallel_sort(
764-
(Entry *)Begin, (Entry *)End,
765-
[](const Entry &A, const Entry &B) { return A.Begin < B.Begin; });
763+
sort(parallel::par, (Entry *)Begin, (Entry *)End,
764+
[](const Entry &A, const Entry &B) { return A.Begin < B.Begin; });
766765
return;
767766
}
768767
if (Config->Machine == ARMNT) {
769768
struct Entry { ulittle32_t Begin, Unwind; };
770-
parallel_sort(
771-
(Entry *)Begin, (Entry *)End,
772-
[](const Entry &A, const Entry &B) { return A.Begin < B.Begin; });
769+
sort(parallel::par, (Entry *)Begin, (Entry *)End,
770+
[](const Entry &A, const Entry &B) { return A.Begin < B.Begin; });
773771
return;
774772
}
775773
errs() << "warning: don't know how to handle .pdata.\n";

‎lld/ELF/Threads.h

+6-8
Original file line numberDiff line numberDiff line change
@@ -71,19 +71,17 @@ namespace elf {
7171
template <class IterTy, class FuncTy>
7272
void parallelForEach(IterTy Begin, IterTy End, FuncTy Fn) {
7373
if (Config->Threads)
74-
parallel_for_each(Begin, End, Fn);
74+
for_each(parallel::par, Begin, End, Fn);
7575
else
76-
std::for_each(Begin, End, Fn);
76+
for_each(parallel::seq, Begin, End, Fn);
7777
}
7878

7979
inline void parallelFor(size_t Begin, size_t End,
8080
std::function<void(size_t)> Fn) {
81-
if (Config->Threads) {
82-
parallel_for(Begin, End, Fn);
83-
} else {
84-
for (size_t I = Begin; I < End; ++I)
85-
Fn(I);
86-
}
81+
if (Config->Threads)
82+
for_each_n(parallel::par, Begin, End, Fn);
83+
else
84+
for_each_n(parallel::seq, Begin, End, Fn);
8785
}
8886
}
8987
}

‎lld/include/lld/Core/Parallel.h

+95-52
Original file line numberDiff line numberDiff line change
@@ -12,8 +12,9 @@
1212

1313
#include "lld/Core/LLVM.h"
1414
#include "lld/Core/TaskGroup.h"
15-
#include "llvm/Support/MathExtras.h"
15+
#include "llvm/ADT/STLExtras.h"
1616
#include "llvm/Config/llvm-config.h"
17+
#include "llvm/Support/MathExtras.h"
1718

1819
#include <algorithm>
1920

@@ -24,25 +25,40 @@
2425

2526
namespace lld {
2627

27-
#if !LLVM_ENABLE_THREADS
28-
template <class RandomAccessIterator, class Comparator>
29-
void parallel_sort(
30-
RandomAccessIterator Start, RandomAccessIterator End,
31-
const Comparator &Comp = std::less<
32-
typename std::iterator_traits<RandomAccessIterator>::value_type>()) {
33-
std::sort(Start, End, Comp);
34-
}
35-
#elif defined(_MSC_VER)
36-
// Use ppl parallel_sort on Windows.
28+
namespace parallel {
29+
struct sequential_execution_policy {};
30+
struct parallel_execution_policy {};
31+
32+
template <typename T>
33+
struct is_execution_policy
34+
: public std::integral_constant<
35+
bool, llvm::is_one_of<T, sequential_execution_policy,
36+
parallel_execution_policy>::value> {};
37+
38+
constexpr sequential_execution_policy seq{};
39+
constexpr parallel_execution_policy par{};
40+
41+
#if LLVM_ENABLE_THREADS
42+
43+
namespace detail {
44+
45+
#if defined(_MSC_VER)
3746
template <class RandomAccessIterator, class Comparator>
38-
void parallel_sort(
39-
RandomAccessIterator Start, RandomAccessIterator End,
40-
const Comparator &Comp = std::less<
41-
typename std::iterator_traits<RandomAccessIterator>::value_type>()) {
47+
void parallel_sort(RandomAccessIterator Start, RandomAccessIterator End,
48+
const Comparator &Comp) {
4249
concurrency::parallel_sort(Start, End, Comp);
4350
}
51+
template <class IterTy, class FuncTy>
52+
void parallel_for_each(IterTy Begin, IterTy End, FuncTy Fn) {
53+
concurrency::parallel_for_each(Begin, End, Fn);
54+
}
55+
56+
template <class IndexTy, class FuncTy>
57+
void parallel_for_each_n(IndexTy Begin, IndexTy End, FuncTy Fn) {
58+
concurrency::parallel_for(Begin, End, Fn);
59+
}
60+
4461
#else
45-
namespace detail {
4662
const ptrdiff_t MinParallelSize = 1024;
4763

4864
/// \brief Inclusive median.
@@ -83,46 +99,15 @@ void parallel_quick_sort(RandomAccessIterator Start, RandomAccessIterator End,
8399
});
84100
parallel_quick_sort(Pivot + 1, End, Comp, TG, Depth - 1);
85101
}
86-
}
87102

88103
template <class RandomAccessIterator, class Comparator>
89-
void parallel_sort(
90-
RandomAccessIterator Start, RandomAccessIterator End,
91-
const Comparator &Comp = std::less<
92-
typename std::iterator_traits<RandomAccessIterator>::value_type>()) {
104+
void parallel_sort(RandomAccessIterator Start, RandomAccessIterator End,
105+
const Comparator &Comp) {
93106
TaskGroup TG;
94-
detail::parallel_quick_sort(Start, End, Comp, TG,
95-
llvm::Log2_64(std::distance(Start, End)) + 1);
96-
}
97-
#endif
98-
99-
template <class T> void parallel_sort(T *Start, T *End) {
100-
parallel_sort(Start, End, std::less<T>());
107+
parallel_quick_sort(Start, End, Comp, TG,
108+
llvm::Log2_64(std::distance(Start, End)) + 1);
101109
}
102110

103-
#if !LLVM_ENABLE_THREADS
104-
template <class IterTy, class FuncTy>
105-
void parallel_for_each(IterTy Begin, IterTy End, FuncTy Fn) {
106-
std::for_each(Begin, End, Fn);
107-
}
108-
109-
template <class IndexTy, class FuncTy>
110-
void parallel_for(IndexTy Begin, IndexTy End, FuncTy Fn) {
111-
for (IndexTy I = Begin; I != End; ++I)
112-
Fn(I);
113-
}
114-
#elif defined(_MSC_VER)
115-
// Use ppl parallel_for_each on Windows.
116-
template <class IterTy, class FuncTy>
117-
void parallel_for_each(IterTy Begin, IterTy End, FuncTy Fn) {
118-
concurrency::parallel_for_each(Begin, End, Fn);
119-
}
120-
121-
template <class IndexTy, class FuncTy>
122-
void parallel_for(IndexTy Begin, IndexTy End, FuncTy Fn) {
123-
concurrency::parallel_for(Begin, End, Fn);
124-
}
125-
#else
126111
template <class IterTy, class FuncTy>
127112
void parallel_for_each(IterTy Begin, IterTy End, FuncTy Fn) {
128113
// TaskGroup has a relatively high overhead, so we want to reduce
@@ -142,7 +127,7 @@ void parallel_for_each(IterTy Begin, IterTy End, FuncTy Fn) {
142127
}
143128

144129
template <class IndexTy, class FuncTy>
145-
void parallel_for(IndexTy Begin, IndexTy End, FuncTy Fn) {
130+
void parallel_for_each_n(IndexTy Begin, IndexTy End, FuncTy Fn) {
146131
ptrdiff_t TaskSize = (End - Begin) / 1024;
147132
if (TaskSize == 0)
148133
TaskSize = 1;
@@ -160,7 +145,65 @@ void parallel_for(IndexTy Begin, IndexTy End, FuncTy Fn) {
160145
Fn(J);
161146
});
162147
}
148+
149+
#endif
150+
151+
template <typename Iter>
152+
using DefComparator =
153+
std::less<typename std::iterator_traits<Iter>::value_type>;
154+
155+
} // namespace detail
163156
#endif
157+
158+
// sequential algorithm implementations.
159+
template <class Policy, class RandomAccessIterator,
160+
class Comparator = detail::DefComparator<RandomAccessIterator>>
161+
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End,
162+
const Comparator &Comp = Comparator()) {
163+
static_assert(is_execution_policy<Policy>::value,
164+
"Invalid execution policy!");
165+
std::sort(Start, End, Comp);
166+
}
167+
168+
template <class Policy, class IterTy, class FuncTy>
169+
void for_each(Policy policy, IterTy Begin, IterTy End, FuncTy Fn) {
170+
static_assert(is_execution_policy<Policy>::value,
171+
"Invalid execution policy!");
172+
std::for_each(Begin, End, Fn);
173+
}
174+
175+
template <class Policy, class IndexTy, class FuncTy>
176+
void for_each_n(Policy policy, IndexTy Begin, IndexTy End, FuncTy Fn) {
177+
static_assert(is_execution_policy<Policy>::value,
178+
"Invalid execution policy!");
179+
for (IndexTy I = Begin; I != End; ++I)
180+
Fn(I);
181+
}
182+
183+
// Parallel algorithm implementations, only available when LLVM_ENABLE_THREADS
184+
// is true.
185+
#if defined(LLVM_ENABLE_THREADS)
186+
template <class RandomAccessIterator,
187+
class Comparator = detail::DefComparator<RandomAccessIterator>>
188+
void sort(parallel_execution_policy policy, RandomAccessIterator Start,
189+
RandomAccessIterator End, const Comparator &Comp = Comparator()) {
190+
detail::parallel_sort(Start, End, Comp);
191+
}
192+
193+
template <class IterTy, class FuncTy>
194+
void for_each(parallel_execution_policy policy, IterTy Begin, IterTy End,
195+
FuncTy Fn) {
196+
detail::parallel_for_each(Begin, End, Fn);
197+
}
198+
199+
template <class IndexTy, class FuncTy>
200+
void for_each_n(parallel_execution_policy policy, IndexTy Begin, IndexTy End,
201+
FuncTy Fn) {
202+
detail::parallel_for_each_n(Begin, End, Fn);
203+
}
204+
#endif
205+
206+
} // namespace parallel
164207
} // End namespace lld
165208

166209
#endif // LLD_CORE_PARALLEL_H

‎lld/lib/ReaderWriter/MachO/LayoutPass.cpp

+4-4
Original file line numberDiff line numberDiff line change
@@ -461,10 +461,10 @@ llvm::Error LayoutPass::perform(SimpleFile &mergedFile) {
461461
});
462462

463463
std::vector<LayoutPass::SortKey> vec = decorate(atomRange);
464-
parallel_sort(vec.begin(), vec.end(),
465-
[&](const LayoutPass::SortKey &l, const LayoutPass::SortKey &r) -> bool {
466-
return compareAtoms(l, r, _customSorter);
467-
});
464+
sort(parallel::par, vec.begin(), vec.end(),
465+
[&](const LayoutPass::SortKey &l, const LayoutPass::SortKey &r) -> bool {
466+
return compareAtoms(l, r, _customSorter);
467+
});
468468
DEBUG(checkTransitivity(vec, _customSorter));
469469
undecorate(atomRange, vec);
470470

‎lld/unittests/CoreTests/ParallelTest.cpp

+2-2
Original file line numberDiff line numberDiff line change
@@ -26,7 +26,7 @@ TEST(Parallel, sort) {
2626
for (auto &i : array)
2727
i = dist(randEngine);
2828

29-
lld::parallel_sort(std::begin(array), std::end(array));
29+
sort(lld::parallel::par, std::begin(array), std::end(array));
3030
ASSERT_TRUE(std::is_sorted(std::begin(array), std::end(array)));
3131
}
3232

@@ -36,7 +36,7 @@ TEST(Parallel, parallel_for) {
3636
// writing.
3737
uint32_t range[2050];
3838
std::fill(range, range + 2050, 1);
39-
lld::parallel_for(0, 2049, [&range](size_t I) { ++range[I]; });
39+
for_each_n(lld::parallel::par, 0, 2049, [&range](size_t I) { ++range[I]; });
4040

4141
uint32_t expected[2049];
4242
std::fill(expected, expected + 2049, 2);

0 commit comments

Comments
 (0)
Please sign in to comment.