[Support] Sink LLD's parallel algorithm wrappers to support

[rnk]

Summary

Essentially takes the lld/Common/Threads.h wrappers and moves them to
the llvm/Support/Paralle.h algorithm header.

The changes are:

• Add range overloads
• Use the sequential algorithm directly when 1 thread is requested (skips task grouping)
• Fix the index type of for_each_n to size_t. Nobody in LLVM was using any other parameter, and it made overload resolution hard for for_each_n(par, 0, foo.size(), ...) because 0 is int, not size_t.

Remove Threads.h and update LLD for that.

This is a prerequisite for parallel public symbol processing in the PDB
library, which is in LLVM.

[MaskRay]

Add range overloads
Use the sequential algorithm directly when 1 thread is requested (skips task grouping)
Fix the index type of for_each_n to size_t. Nobody in LLVM was using any other parameter, and it made overload resolution hard for for_each_n(par, 0, foo.size(), ...) because 0 is int, not size_t.

These changes all look good to me. I have a question regarding the intended usage:

lld/COFF/LLDMapFile.cpp

77

Isn't parallel::par redundant? Can we just use

parallel::for_each_n((size_t)0, syms.size(), [&](size_t i) { ... }) ?

[aganea]

This is a prerequisite for parallel public symbol processing in the PDB
library, which is in LLVM.

Thanks for working on this Reid :-)

lld/COFF/LLDMapFile.cpp

77

+1

lld/ELF/Writer.cpp

1752

sym, as indicated by the clang-tidy log.

[rnk]

lld/COFF/LLDMapFile.cpp

77

IMO yes, but I think these APIs are designed to be drop-in replaceable by the parallel STL APIs standardized in C++17, and those take a policy. I think the idea is that there could be other policies for GPUs, accelerators, SIMD variants, etc, although I'm not super familiar with them.

I peaked at llvm-project/pstl/include/internal/glue_algorithm_impl.h, which declares the C++17 standard APIs, and they are already slightly different from what LLVM has here. (No range wrappers, for_each_n does not take size_t.) If we are going to be different, we might as well simplify the API. I will remove the policy parameter and reupload this change. I believe there are only two other in-tree clients of this API in MLIR.

[rnk]

• Drop policy parameter

While doing this, I may have re-discovered the reason that the committee
designed the APIs this way. With the parameter, you can use ADL to write this:

sort(parallel::par, vec.begin(), vec.end(), ...);
for_each(parallel::par, vec.begin(), vec.end(), ...);

You can even do using namespace (llvm|std)::parallel; and write this:

sort(par, vec.begin(), vec.end(), ...);

If you drop the policy parameter, using the llvm::parallel namespace becomes
almost impossible because it makes every unqualified call to sort ambiguous.

WDYT? I would be happy to go back and rewrite all the code to this:

sort([llvm::]parallel::par, ...);

As in, drop the "parallel::" prefix from "parallel::sort(...)", and rely on
ADL. Maybe that is too tricky, though.

[rriddle]

LGTM for anything in MLIR.

[aganea]

If the goal is to replace Parallel.h with pSTL sometime in the future, then maybe it's better to keep the STL-like API and the policy (but I wouldn't favor that ATM)
I find it pleasant to read the way it is -- if you want to protect from someone doing using llvm::parallel, why not keep the LLD nomenclature? llvm::parallelSort(...). It will not be ambiguous, even if you do using llvm; parallelSort(...);.

[rnk]

• rename to parallelSort, parallelForEach[N]

[MaskRay]

Seems the conclusion is that llvm::parallelSort(..) is better than llvm::parallel::sort(...) or llvm::parallel(parallel::seq, ...).

It is nice to avoid ADL when doing the refactoring. llvm::parallelSort also avoids functions with same signatures but overloaded in different namespaces (std:: llvm::parallel::)

[aganea]

LGTM as well, thank you!

lld/lib/ReaderWriter/MachO/LayoutPass.cpp

464–468

Could this be llvm::parallelSort(vec, ...)?

llvm/unittests/Support/ParallelTest.cpp

33

parallelSort(array)?

[rnk]

Thanks!

llvm/unittests/Support/ParallelTest.cpp

33

The compiler didn't like that one:

llvm-project/llvm/unittests/Support/ParallelTest.cpp:33:3: error: no matching function for call to 'parallelSort'
  parallelSort(array);
  ^~~~~~~~~~~~
llvm-project/llvm/include/llvm/Support/Parallel.h:204:6: note: candidate template ignored: substitution failure [with RangeTy = unsigned int (&)[1048576]]: reference to type 'unsigned int [1048576]' requires an initializer

lld/COFF/Driver.cpp

 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Writer.h"
 #include "lld/Common/Args.h"
 #include "lld/Common/Driver.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Filesystem.h"
 #include "lld/Common/Memory.h"
-#include "lld/Common/Threads.h"
 #include "lld/Common/Timer.h"
 #include "lld/Common/Version.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/BinaryFormat/Magic.h"
 #include "llvm/LTO/LTO.h"
 #include "llvm/Object/ArchiveWriter.h"
 #include "llvm/Object/COFFImportFile.h"
 #include "llvm/Object/COFFModuleDefinition.h"
 #include "llvm/Object/WindowsMachineFlag.h"
 #include "llvm/Option/Arg.h"
 #include "llvm/Option/ArgList.h"
 #include "llvm/Option/Option.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/LEB128.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/Support/Parallel.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Process.h"
 #include "llvm/Support/TarWriter.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/ToolDrivers/llvm-lib/LibDriver.h"
 #include <algorithm>
 #include <future>

lld/COFF/ICF.cpp

 // See ELF/ICF.cpp for the details about the algorithm.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ICF.h"
 #include "Chunks.h"
 #include "Symbols.h"
 #include "lld/Common/ErrorHandler.h"
-#include "lld/Common/Threads.h"
 #include "lld/Common/Timer.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Parallel.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Support/xxhash.h"
 #include <algorithm>
 #include <atomic>

lld/COFF/LLDMapFile.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "LLDMapFile.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Writer.h"
 #include "lld/Common/ErrorHandler.h"
-#include "lld/Common/Threads.h"
+#include "llvm/Support/Parallel.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 using namespace llvm::object;
 using namespace lld;
 using namespace lld::coff;
 
 using SymbolMapTy =
static SymbolMapTy getSectionSyms(ArrayRef<DefinedRegular *> syms) {
   }
   return ret;
 }
 
 // Construct a map from symbols to their stringified representations.
 static DenseMap<DefinedRegular *, std::string>
 getSymbolStrings(ArrayRef<DefinedRegular *> syms) {
   std::vector<std::string> str(syms.size());
   parallelForEachN((size_t)0, syms.size(), [&](size_t i) {
     raw_string_ostream os(str[i]);
     writeHeader(os, syms[i]->getRVA(), 0, 0);
     os << indent16 << toString(*syms[i]);
   });
 
   DenseMap<DefinedRegular *, std::string> ret;
   for (size_t i = 0, e = syms.size(); i < e; ++i)
     ret[syms[i]] = std::move(str[i]);

lld/COFF/MapFile.cpp

 // 0000:00000000  __guard_fids__       0000000140000000     libcmt : exe_main.obj
 //===----------------------------------------------------------------------===//
 
 #include "MapFile.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Writer.h"
 #include "lld/Common/ErrorHandler.h"
-#include "lld/Common/Threads.h"
 #include "lld/Common/Timer.h"
+#include "llvm/Support/Parallel.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 using namespace llvm::object;
 using namespace lld;
 using namespace lld::coff;
 

lld/COFF/PDB.cpp

 #include "Config.h"
 #include "DebugTypes.h"
 #include "Driver.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "TypeMerger.h"
 #include "Writer.h"
 #include "lld/Common/ErrorHandler.h"
-#include "lld/Common/Threads.h"
 #include "lld/Common/Timer.h"
 #include "llvm/DebugInfo/CodeView/DebugFrameDataSubsection.h"
 #include "llvm/DebugInfo/CodeView/DebugSubsectionRecord.h"
 #include "llvm/DebugInfo/CodeView/GlobalTypeTableBuilder.h"
 #include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h"
 #include "llvm/DebugInfo/CodeView/MergingTypeTableBuilder.h"
 #include "llvm/DebugInfo/CodeView/RecordName.h"
 #include "llvm/DebugInfo/CodeView/SymbolDeserializer.h"

 #include "llvm/Object/COFF.h"
 #include "llvm/Object/CVDebugRecord.h"
 #include "llvm/Support/BinaryByteStream.h"
 #include "llvm/Support/CRC.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/FormatAdapters.h"
 #include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/Parallel.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include <memory>
 
 using namespace llvm;
 using namespace llvm::codeview;
 using namespace lld;
 using namespace lld::coff;

lld/COFF/Writer.cpp

 #include "InputFiles.h"
 #include "LLDMapFile.h"
 #include "MapFile.h"
 #include "PDB.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
-#include "lld/Common/Threads.h"
 #include "lld/Common/Timer.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/BinaryStreamReader.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Endian.h"

lld/Common/ErrorHandler.cpp

 //===- ErrorHandler.cpp ---------------------------------------------------===//
 //
 // 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 "lld/Common/ErrorHandler.h"
 
-#include "lld/Common/Threads.h"
+#include "llvm/Support/Parallel.h"
 
 #include "llvm/ADT/Twine.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/DiagnosticPrinter.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/raw_ostream.h"
 #include <mutex>
 #include <regex>

lld/Common/Filesystem.cpp

 //===- Filesystem.cpp -----------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains a few utility functions to handle files.
 //
 //===----------------------------------------------------------------------===//
 
 #include "lld/Common/Filesystem.h"
-#include "lld/Common/Threads.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/Support/FileOutputBuffer.h"
 #include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Parallel.h"
 #if LLVM_ON_UNIX
 #include <unistd.h>
 #endif
 #include <thread>
 
 using namespace llvm;
 using namespace lld;
 

lld/ELF/Driver.cpp

 #include "Writer.h"
 #include "lld/Common/Args.h"
 #include "lld/Common/Driver.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Filesystem.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Strings.h"
 #include "lld/Common/TargetOptionsCommandFlags.h"
-#include "lld/Common/Threads.h"
 #include "lld/Common/Version.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/LTO/LTO.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compression.h"
 #include "llvm/Support/GlobPattern.h"
 #include "llvm/Support/LEB128.h"
+#include "llvm/Support/Parallel.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/TarWriter.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Support/TimeProfiler.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstdlib>
 #include <utility>
 

lld/ELF/ICF.cpp

 #include "ICF.h"
 #include "Config.h"
 #include "LinkerScript.h"
 #include "OutputSections.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Writer.h"
-#include "lld/Common/Threads.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/BinaryFormat/ELF.h"
 #include "llvm/Object/ELF.h"
+#include "llvm/Support/Parallel.h"
 #include "llvm/Support/TimeProfiler.h"
 #include "llvm/Support/xxhash.h"
 #include <algorithm>
 #include <atomic>
 
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
template <class ELFT> void ICF<ELFT>::run() {
   // Collect sections to merge.
   for (InputSectionBase *sec : inputSections) {
     auto *s = cast<InputSection>(sec);
     if (isEligible(s))
       sections.push_back(s);
   }
 
   // Initially, we use hash values to partition sections.
-  parallelForEach(sections, [&](InputSection *s) {
-    s->eqClass[0] = xxHash64(s->data());
-  });
+  parallelForEach(
+      sections, [&](InputSection *s) { s->eqClass[0] = xxHash64(s->data()); });
 
   for (unsigned cnt = 0; cnt != 2; ++cnt) {
     parallelForEach(sections, [&](InputSection *s) {
       if (s->areRelocsRela)
         combineRelocHashes<ELFT>(cnt, s, s->template relas<ELFT>());
       else
         combineRelocHashes<ELFT>(cnt, s, s->template rels<ELFT>());
     });

lld/ELF/LinkerScript.cpp

 #include "OutputSections.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "Writer.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Strings.h"
-#include "lld/Common/Threads.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/BinaryFormat/ELF.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Parallel.h"
 #include "llvm/Support/Path.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <iterator>
 #include <limits>
 #include <string>

lld/ELF/MapFile.cpp

 #include "MapFile.h"
 #include "InputFiles.h"
 #include "LinkerScript.h"
 #include "OutputSections.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "lld/Common/Strings.h"
-#include "lld/Common/Threads.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SetVector.h"
+#include "llvm/Support/Parallel.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 using namespace llvm::object;
 
 namespace lld {
 namespace elf {
 using SymbolMapTy = DenseMap<const SectionBase *, SmallVector<Defined *, 4>>;

lld/ELF/OutputSections.cpp

 //===- OutputSections.cpp -------------------------------------------------===//
 //
 // 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 "OutputSections.h"
 #include "Config.h"
 #include "LinkerScript.h"
 #include "SymbolTable.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Strings.h"
-#include "lld/Common/Threads.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/Support/Compression.h"
 #include "llvm/Support/MD5.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/Support/Parallel.h"
 #include "llvm/Support/SHA1.h"
 #include <regex>
 
 using namespace llvm;
 using namespace llvm::dwarf;
 using namespace llvm::object;
 using namespace llvm::support::endian;
 using namespace llvm::ELF;

lld/ELF/SyntheticSections.cpp

 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Target.h"
 #include "Writer.h"
 #include "lld/Common/DWARF.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Strings.h"
-#include "lld/Common/Threads.h"
 #include "lld/Common/Version.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/DebugInfo/DWARF/DWARFDebugPubTable.h"
 #include "llvm/Object/ELFObjectFile.h"
 #include "llvm/Support/Compression.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/LEB128.h"
 #include "llvm/Support/MD5.h"
+#include "llvm/Support/Parallel.h"
 #include "llvm/Support/TimeProfiler.h"
 #include <cstdlib>
 #include <thread>
 
 using namespace llvm;
 using namespace llvm::dwarf;
 using namespace llvm::ELF;
 using namespace llvm::object;

lld/ELF/Writer.cpp

 #include "Relocations.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "lld/Common/Filesystem.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Strings.h"
-#include "lld/Common/Threads.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringSwitch.h"
+#include "llvm/Support/Parallel.h"
 #include "llvm/Support/RandomNumberGenerator.h"
 #include "llvm/Support/SHA1.h"
 #include "llvm/Support/TimeProfiler.h"
 #include "llvm/Support/xxhash.h"
 #include <climits>
 
 #define DEBUG_TYPE "lld"
 

 }
 
 // If Input Sections have been shrinked (basic block sections) then
 // update symbol values and sizes associated with these sections.  With basic
 // block sections, input sections can shrink when the jump instructions at
 // the end of the section are relaxed.
 static void fixSymbolsAfterShrinking() {
   for (InputFile *File : objectFiles) {
     parallelForEach(File->getSymbols(), [&](Symbol *Sym) {
       auto *def = dyn_cast<Defined>(Sym);
       if (!def)
         return;
 
       const SectionBase *sec = def->section;
       if (!sec)
         return;
 

lld/include/lld/Common/Threads.h

-//===- Threads.h ------------------------------------------------*- 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
-//
-//===----------------------------------------------------------------------===//
-//
-// LLD supports threads to distribute workloads to multiple cores. Using
-// multicore is most effective when more than one core are idle. At the
-// last step of a build, it is often the case that a linker is the only
-// active process on a computer. So, we are naturally interested in using
-// threads wisely to reduce latency to deliver results to users.
-//
-// That said, we don't want to do "too clever" things using threads.
-// Complex multi-threaded algorithms are sometimes extremely hard to
-// reason about and can easily mess up the entire design.
-//
-// Fortunately, when a linker links large programs (when the link time is
-// most critical), it spends most of the time to work on massive number of
-// small pieces of data of the same kind, and there are opportunities for
-// large parallelism there. Here are examples:
-//
-//  - We have hundreds of thousands of input sections that need to be
-//    copied to a result file at the last step of link. Once we fix a file
-//    layout, each section can be copied to its destination and its
-//    relocations can be applied independently.
-//
-//  - We have tens of millions of small strings when constructing a
-//    mergeable string section.
-//
-// For the cases such as the former, we can just use parallelForEach
-// instead of std::for_each (or a plain for loop). Because tasks are
-// completely independent from each other, we can run them in parallel
-// without any coordination between them. That's very easy to understand
-// and reason about.
-//
-// For the cases such as the latter, we can use parallel algorithms to
-// deal with massive data. We have to write code for a tailored algorithm
-// for each problem, but the complexity of multi-threading is isolated in
-// a single pass and doesn't affect the linker's overall design.
-//
-// The above approach seems to be working fairly well. As an example, when
-// linking Chromium (output size 1.6 GB), using 4 cores reduces latency to
-// 75% compared to single core (from 12.66 seconds to 9.55 seconds) on my
-// Ivy Bridge Xeon 2.8 GHz machine. Using 40 cores reduces it to 63% (from
-// 12.66 seconds to 7.95 seconds). Because of the Amdahl's law, the
-// speedup is not linear, but as you add more cores, it gets faster.
-//
-// On a final note, if you are trying to optimize, keep the axiom "don't
-// guess, measure!" in mind. Some important passes of the linker are not
-// that slow. For example, resolving all symbols is not a very heavy pass,
-// although it would be very hard to parallelize it. You want to first
-// identify a slow pass and then optimize it.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLD_COMMON_THREADS_H
-#define LLD_COMMON_THREADS_H
-
-#include "llvm/Support/Parallel.h"
-#include <functional>
-
-namespace lld {
-
-template <typename R, class FuncTy> void parallelForEach(R &&range, FuncTy fn) {
-  if (llvm::parallel::strategy.ThreadsRequested != 1)
-    for_each(llvm::parallel::par, std::begin(range), std::end(range), fn);
-  else
-    for_each(llvm::parallel::seq, std::begin(range), std::end(range), fn);
-}
-
-inline void parallelForEachN(size_t begin, size_t end,
-                             llvm::function_ref<void(size_t)> fn) {
-  if (llvm::parallel::strategy.ThreadsRequested != 1)
-    for_each_n(llvm::parallel::par, begin, end, fn);
-  else
-    for_each_n(llvm::parallel::seq, begin, end, fn);
-}
-
-template <typename R, class FuncTy> void parallelSort(R &&range, FuncTy fn) {
-  if (llvm::parallel::strategy.ThreadsRequested != 1)
-    sort(llvm::parallel::par, std::begin(range), std::end(range), fn);
-  else
-    sort(llvm::parallel::seq, std::begin(range), std::end(range), fn);
-}
-
-} // namespace lld
-
-#endif

lld/lib/ReaderWriter/MachO/LayoutPass.cpp

llvm::Error LayoutPass::perform(SimpleFile &mergedFile) {
   buildOrdinalOverrideMap(atomRange);
 
   LLVM_DEBUG({
     llvm::dbgs() << "unsorted atoms:\n";
     printDefinedAtoms(atomRange);
   });
 
   std::vector<LayoutPass::SortKey> vec = decorate(atomRange);
-  sort(llvm::parallel::par, vec.begin(), vec.end(),
-       [&](const LayoutPass::SortKey &l, const LayoutPass::SortKey &r) -> bool {
-         return compareAtoms(l, r, _customSorter);
-       });
+  llvm::parallelSort(
+      vec,
   LLVM_DEBUG(checkTransitivity(vec, _customSorter));
   undecorate(atomRange, vec);
 
   LLVM_DEBUG({
     llvm::dbgs() << "sorted atoms:\n";
     printDefinedAtoms(atomRange);
   });
 

lld/wasm/Driver.cpp

 #include "SymbolTable.h"
 #include "Writer.h"
 #include "lld/Common/Args.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Filesystem.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Reproduce.h"
 #include "lld/Common/Strings.h"
-#include "lld/Common/Threads.h"
 #include "lld/Common/Version.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Object/Wasm.h"
 #include "llvm/Option/Arg.h"
 #include "llvm/Option/ArgList.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Host.h"
+#include "llvm/Support/Parallel.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Process.h"
 #include "llvm/Support/TarWriter.h"
 #include "llvm/Support/TargetSelect.h"
 
 #define DEBUG_TYPE "lld"
 
 using namespace llvm;

lld/wasm/OutputSections.cpp

 //===- OutputSections.cpp -------------------------------------------------===//
 //
 // 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 "OutputSections.h"
 #include "InputChunks.h"
 #include "InputFiles.h"
 #include "OutputSegment.h"
 #include "WriterUtils.h"
 #include "lld/Common/ErrorHandler.h"
-#include "lld/Common/Threads.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Support/LEB128.h"
+#include "llvm/Support/Parallel.h"
 
 #define DEBUG_TYPE "lld"
 
 using namespace llvm;
 using namespace llvm::wasm;
 
 namespace lld {
 

lld/wasm/Writer.cpp

 #include "OutputSegment.h"
 #include "Relocations.h"
 #include "SymbolTable.h"
 #include "SyntheticSections.h"
 #include "WriterUtils.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Strings.h"
-#include "lld/Common/Threads.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/BinaryFormat/Wasm.h"
 #include "llvm/Object/WasmTraits.h"
 #include "llvm/Support/FileOutputBuffer.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/LEB128.h"
+#include "llvm/Support/Parallel.h"
 
 #include <cstdarg>
 #include <map>
 
 #define DEBUG_TYPE "lld"
 
 using namespace llvm;
 using namespace llvm::wasm;

llvm/include/llvm/Support/Parallel.h

 #include <algorithm>
 #include <condition_variable>
 #include <functional>
 #include <mutex>
 
 namespace llvm {
 
 namespace parallel {
-struct sequential_execution_policy {};
-struct parallel_execution_policy {};
-
-template <typename T>
-struct is_execution_policy
-    : public std::integral_constant<
-          bool, llvm::is_one_of<T, sequential_execution_policy,
-                                parallel_execution_policy>::value> {};
-
-constexpr sequential_execution_policy seq{};
-constexpr parallel_execution_policy par{};
 
 // Strategy for the default executor used by the parallel routines provided by
 // this file. It defaults to using all hardware threads and should be
 // initialized before the first use of parallel routines.
 extern ThreadPoolStrategy strategy;
 
 namespace detail {
 
for (; I + TaskSize < End; I += TaskSize) {
     });
   }
   for (IndexTy J = I; J < End; ++J)
     Fn(J);
 }
 
 #endif
 
-template <typename Iter>
-using DefComparator =
-    std::less<typename std::iterator_traits<Iter>::value_type>;
-
 } // namespace detail
+} // namespace parallel
 
-// sequential algorithm implementations.
-template <class Policy, class RandomAccessIterator,
-          class Comparator = detail::DefComparator<RandomAccessIterator>>
-void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End,
+template <class RandomAccessIterator,
+          class Comparator = std::less<
+              typename std::iterator_traits<RandomAccessIterator>::value_type>>
+void parallelSort(RandomAccessIterator Start, RandomAccessIterator End,
                   const Comparator &Comp = Comparator()) {
-  static_assert(is_execution_policy<Policy>::value,
-                "Invalid execution policy!");
+#if LLVM_ENABLE_THREADS
+  if (parallel::strategy.ThreadsRequested != 1) {
+    parallel::detail::parallel_sort(Start, End, Comp);
+    return;
+  }
+#endif
   llvm::sort(Start, End, Comp);
 }
 
-template <class Policy, class IterTy, class FuncTy>
-void for_each(Policy policy, IterTy Begin, IterTy End, FuncTy Fn) {
-  static_assert(is_execution_policy<Policy>::value,
-                "Invalid execution policy!");
-  std::for_each(Begin, End, Fn);
+template <class IterTy, class FuncTy>
+void parallelForEach(IterTy Begin, IterTy End, FuncTy Fn) {
+#if LLVM_ENABLE_THREADS
+  if (parallel::strategy.ThreadsRequested != 1) {
+    parallel::detail::parallel_for_each(Begin, End, Fn);
+    return;
   }
-
-template <class Policy, class IndexTy, class FuncTy>
-void for_each_n(Policy policy, IndexTy Begin, IndexTy End, FuncTy Fn) {
-  static_assert(is_execution_policy<Policy>::value,
-                "Invalid execution policy!");
-  for (IndexTy I = Begin; I != End; ++I)
-    Fn(I);
+#endif
+  std::for_each(Begin, End, Fn);
 }
 
-// Parallel algorithm implementations, only available when LLVM_ENABLE_THREADS
-// is true.
+template <class FuncTy>
+void parallelForEachN(size_t Begin, size_t End, FuncTy Fn) {
 #if LLVM_ENABLE_THREADS
-template <class RandomAccessIterator,
-          class Comparator = detail::DefComparator<RandomAccessIterator>>
-void sort(parallel_execution_policy policy, RandomAccessIterator Start,
-          RandomAccessIterator End, const Comparator &Comp = Comparator()) {
-  detail::parallel_sort(Start, End, Comp);
+  if (parallel::strategy.ThreadsRequested != 1) {
+    parallel::detail::parallel_for_each_n(Begin, End, Fn);
+    return;
+  }
+#endif
+  for (size_t I = Begin; I != End; ++I)
+    Fn(I);
 }
 
-template <class IterTy, class FuncTy>
-void for_each(parallel_execution_policy policy, IterTy Begin, IterTy End,
-              FuncTy Fn) {
-  detail::parallel_for_each(Begin, End, Fn);
+// Range wrappers.
+template <class RangeTy,
+          class Comparator = std::less<decltype(*std::begin(RangeTy()))>>
+void parallelSort(RangeTy &&R, const Comparator &Comp = Comparator()) {
+  parallelSort(std::begin(R), std::end(R), Comp);
 }
 
-template <class IndexTy, class FuncTy>
-void for_each_n(parallel_execution_policy policy, IndexTy Begin, IndexTy End,
-                FuncTy Fn) {
-  detail::parallel_for_each_n(Begin, End, Fn);
+template <class RangeTy, class FuncTy>
+void parallelForEach(RangeTy &&R, FuncTy Fn) {
+  parallelForEach(std::begin(R), std::end(R), Fn);
 }
-#endif
 
-} // namespace parallel
 } // namespace llvm
 
 #endif // LLVM_SUPPORT_PARALLEL_H

llvm/unittests/Support/ParallelTest.cpp

 
 TEST(Parallel, sort) {
   std::mt19937 randEngine;
   std::uniform_int_distribution<uint32_t> dist;
 
   for (auto &i : array)
     i = dist(randEngine);
 
-  sort(parallel::par, std::begin(array), std::end(array));
+  parallelSort(std::begin(array), std::end(array));
   ASSERT_TRUE(llvm::is_sorted(array));
 }
 
 TEST(Parallel, parallel_for) {
   // We need to test the case with a TaskSize > 1. We are white-box testing
   // here. The TaskSize is calculated as (End - Begin) / 1024 at the time of
   // writing.
   uint32_t range[2050];
   std::fill(range, range + 2050, 1);
-  for_each_n(parallel::par, 0, 2049, [&range](size_t I) { ++range[I]; });
+  parallelForEachN(0, 2049, [&range](size_t I) { ++range[I]; });
 
   uint32_t expected[2049];
   std::fill(expected, expected + 2049, 2);
   ASSERT_TRUE(std::equal(range, range + 2049, expected));
   // Check that we don't write past the end of the requested range.
   ASSERT_EQ(range[2049], 1u);
 }
 
 #endif

mlir/docs/Diagnostics.md

 A simple example is shown below:
 
 ```c++
 MLIRContext *context = ...;
 ParallelDiagnosticHandler handler(context);
 
 // Process a list of operations in parallel.
 std::vector<Operation *> opsToProcess = ...;
-llvm::for_each_n(llvm::parallel::par, 0, opsToProcess.size(),
-                 [&](size_t i) {
+llvm::parallelForEachN(0, opsToProcess.size(), [&](size_t i) {
   // Notify the handler that we are processing the i'th operation.
   handler.setOrderIDForThread(i);
   auto *op = opsToProcess[i];
   ...
 
   // Notify the handler that we are finished processing diagnostics on this
   // thread.
   handler.eraseOrderIDForThread();
 });
 ```

mlir/lib/Pass/Pass.cpp

void OpToOpPassAdaptor::runOnOperationAsyncImpl() {
 
   // Get the current thread for this adaptor.
   PassInstrumentation::PipelineParentInfo parentInfo = {llvm::get_threadid(),
                                                         this};
   auto *instrumentor = am.getPassInstrumentor();
 
   // An atomic failure variable for the async executors.
   std::atomic<bool> passFailed(false);
-  llvm::parallel::for_each(
-      llvm::parallel::par, asyncExecutors.begin(),
+  llvm::parallelForEach(
+      asyncExecutors.begin(),
       std::next(asyncExecutors.begin(),
                 std::min(asyncExecutors.size(), opAMPairs.size())),
       [&](MutableArrayRef<OpPassManager> pms) {
         for (auto e = opAMPairs.size(); !passFailed && opIt < e;) {
           // Get the next available operation index.
           unsigned nextID = opIt++;
           if (nextID >= e)
             break;

mlir/lib/Transforms/Inliner.cpp

if (nodesToCanonicalize.empty())
     return;
 
   // Canonicalize each of the nodes within the SCC in parallel.
   // NOTE: This is simple now, because we don't enable canonicalizing nodes
   // within children. When we remove this restriction, this logic will need to
   // be reworked.
   if (context->isMultithreadingEnabled()) {
     ParallelDiagnosticHandler canonicalizationHandler(context);
-    llvm::parallel::for_each_n(
-        llvm::parallel::par, /*Begin=*/size_t(0),
-        /*End=*/nodesToCanonicalize.size(), [&](size_t index) {
+    llvm::parallelForEachN(
+        /*Begin=*/0, /*End=*/nodesToCanonicalize.size(), [&](size_t index) {
           // Set the order for this thread so that diagnostics will be properly
           // ordered.
           canonicalizationHandler.setOrderIDForThread(index);
 
           // Apply the canonicalization patterns to this region.
           auto *node = nodesToCanonicalize[index];
           applyPatternsAndFoldGreedily(*node->getCallableRegion(),
                                        canonPatterns);