CodeGen: Introduce LinkedCodeGen and teach LTOCodeGenerator to use it.

[pcc]

Summary

llvm::LinkedCodeGen is a function that implements the core of parallel LTO
code generation. It uses llvm::SplitModule to split the module into linkable
partitions and spawning one code generation thread per partition. The function
produces multiple object files which can be linked in the usual way.

This has been threaded through to LTOCodeGenerator (and llvm-lto for testing
purposes). Separate patches will add parallel LTO support to the gold plugin
and lld.

[pcc]

Rebase

[pcc]

lib/CodeGen/Parallel.cpp

43 ↗

(On Diff #33017)

Although this API takes an array of stream pointers, all current clients (llvm-lto, gold-plugin D12308, lld D12309) own their streams, making this API a little awkward to use. Probably a better choice of argument type here would be ArrayRef<std::unique_ptr<raw_pwrite_stream>>. This would mean a few extra allocations, but the cost would be dwarfed by that of LTO.

[pcc]

• Fix Windows build

[mehdi_amini]

A few comments.

lib/CodeGen/Parallel.cpp

70 ↗

(On Diff #33150)

Add a comment? Something like: we need to do this because we want to clone the module in a new context to multi-thread the codegen. The "dumping()" part has to be performed in the caller thread and not the one we create just after because we are still in the old LLVMContext

It seems LLVM is missing the ability to clone a module in a new context directly...

72 ↗

(On Diff #33150)

What is copied? Might replace the = with an explicit list if possible. I'm not sure why you want to copy "Options" for instance? Also, some values are passed as argument to the function, the cut is not clear to me.

lib/LTO/LTOCodeGenerator.cpp

504 ↗

(On Diff #33150)

rename, not longer involved in CodeGen

tools/llvm-lto/llvm-lto.cpp

253 ↗

(On Diff #33150)

Tools are usually using tool_output_file, is it appropriate here?

275 ↗

(On Diff #33150)

Why? I mean any particular reason or just for convenience of the implementation?

[pcc]

• Address review comments

lib/CodeGen/Parallel.cpp

44 ↗

(On Diff #33150)

This doesn't seem like it will work, as we do have a client that does not own the stream (LTOCodeGenerator::compileOptimizedToFile, and now llvm-lto). Let's keep the existing API for now.

70 ↗

(On Diff #33150)

Done

72 ↗

(On Diff #33150)

This is now a list of copied things.

It seems that we don't need to copy Options, but this is a micro-optimization not worth thinking about, so I'd rather just copy it.

lib/LTO/LTOCodeGenerator.cpp

504 ↗

(On Diff #33150)

Done

tools/llvm-lto/llvm-lto.cpp

253 ↗

(On Diff #33150)

Yes, I suppose so -- we might want to clean up if one of the files cannot be opened. Done.

275 ↗

(On Diff #33150)

The latter. Since we wouldn't be able to gain any extra test coverage by supporting this case, we don't need to.

[pcc]

• Update file headers

[pcc]

• Update guard

[mehdi_amini]

LGTM. One inline comment.

lib/CodeGen/ParallelCG.cpp

86 ↗

(On Diff #33361)

No move needed here since it is a const ref right?

[pcc]

lib/CodeGen/ParallelCG.cpp

86 ↗

(On Diff #33361)

The std::move here is needed for the std::thread constructor to move (rather than copy) BC into thread-accessible storage (the const ref is taken from that storage). Added a comment clarifying.

llvm/trunk/include/llvm/CodeGen/ParallelCG.h

+//===-- llvm/CodeGen/ParallelCG.h - Parallel code generation ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This header declares functions that can be used for parallel code generation.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_PARALLELCG_H
+#define LLVM_CODEGEN_PARALLELCG_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/Support/CodeGen.h"
+
+namespace llvm {
+
+class Module;
+class TargetOptions;
+class raw_pwrite_stream;
+
+/// Split M into OSs.size() partitions, and generate code for each. Writes
+/// OSs.size() object files to the output streams in OSs. The resulting object
+/// files if linked together are intended to be equivalent to the single object
+/// file that would have been code generated from M.
+///
+/// \returns M if OSs.size() == 1, otherwise returns std::unique_ptr<Module>().
+std::unique_ptr<Module>
+splitCodeGen(std::unique_ptr<Module> M, ArrayRef<raw_pwrite_stream *> OSs,
+             StringRef CPU, StringRef Features, const TargetOptions &Options,
+             Reloc::Model RM = Reloc::Default,
+             CodeModel::Model CM = CodeModel::Default,
+             CodeGenOpt::Level OL = CodeGenOpt::Default);
+
+} // namespace llvm
+
+#endif

llvm/trunk/include/llvm/LTO/LTOCodeGenerator.h

bool optimize(bool disableInline,
                 bool disableVectorization,
                 std::string &errMsg);
 
   // Compiles the merged optimized module into a single object file. It brings
   // the object to a buffer, and returns the buffer to the caller. Return NULL
   // if the compilation was not successful.
   std::unique_ptr<MemoryBuffer> compileOptimized(std::string &errMsg);
 
+  // Compile the merged optimized module into out.size() object files each
+  // representing a linkable partition of the module. If out contains more than
+  // one element, code generation is done in parallel with out.size() threads.
+  // Object files will be written to members of out. Returns true on success.
+  bool compileOptimized(ArrayRef<raw_pwrite_stream *> out, std::string &errMsg);
+
   void setDiagnosticHandler(lto_diagnostic_handler_t, void *);
 
   LLVMContext &getContext() { return Context; }
 
 private:
   void initializeLTOPasses();
 
-  bool compileOptimized(raw_pwrite_stream &out, std::string &errMsg);
   bool compileOptimizedToFile(const char **name, std::string &errMsg);
   void applyScopeRestrictions();
   void applyRestriction(GlobalValue &GV, ArrayRef<StringRef> Libcalls,
                         std::vector<const char *> &MustPreserveList,
                         SmallPtrSetImpl<GlobalValue *> &AsmUsed,
                         Mangler &Mangler);
   bool determineTarget(std::string &errMsg);
 

llvm/trunk/lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   MachineTraceMetrics.cpp
   MachineVerifier.cpp
   MIRPrinter.cpp
   MIRPrintingPass.cpp
   OcamlGC.cpp
   OptimizePHIs.cpp
   PHIElimination.cpp
   PHIEliminationUtils.cpp
+  ParallelCG.cpp
   Passes.cpp
   PeepholeOptimizer.cpp
   PostRASchedulerList.cpp
   ProcessImplicitDefs.cpp
   PrologEpilogInserter.cpp
   PseudoSourceValue.cpp
   RegAllocBase.cpp
   RegAllocBasic.cpp

llvm/trunk/lib/CodeGen/ParallelCG.cpp

+//===-- ParallelCG.cpp ----------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines functions that can be used for parallel code generation.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/ParallelCG.h"
+#include "llvm/Bitcode/ReaderWriter.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/LegacyPassManager.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/ErrorOr.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/thread.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Transforms/Utils/SplitModule.h"
+
+using namespace llvm;
+
+static void codegen(Module *M, llvm::raw_pwrite_stream &OS,
+                    const Target *TheTarget, StringRef CPU, StringRef Features,
+                    const TargetOptions &Options, Reloc::Model RM,
+                    CodeModel::Model CM, CodeGenOpt::Level OL) {
+  std::unique_ptr<TargetMachine> TM(TheTarget->createTargetMachine(
+      M->getTargetTriple(), CPU, Features, Options, RM, CM, OL));
+
+  legacy::PassManager CodeGenPasses;
+  if (TM->addPassesToEmitFile(CodeGenPasses, OS,
+                              TargetMachine::CGFT_ObjectFile))
+    report_fatal_error("Failed to setup codegen");
+  CodeGenPasses.run(*M);
+}
+
+std::unique_ptr<Module>
+llvm::splitCodeGen(std::unique_ptr<Module> M,
+                   ArrayRef<llvm::raw_pwrite_stream *> OSs, StringRef CPU,
+                   StringRef Features, const TargetOptions &Options,
+                   Reloc::Model RM, CodeModel::Model CM, CodeGenOpt::Level OL) {
+  StringRef TripleStr = M->getTargetTriple();
+  std::string ErrMsg;
+  const Target *TheTarget = TargetRegistry::lookupTarget(TripleStr, ErrMsg);
+  if (!TheTarget)
+    report_fatal_error(Twine("Target not found: ") + ErrMsg);
+
+  if (OSs.size() == 1) {
+    codegen(M.get(), *OSs[0], TheTarget, CPU, Features, Options, RM, CM,
+            OL);
+    return M;
+  }
+
+  std::vector<std::thread> Threads;
+  SplitModule(std::move(M), OSs.size(), [&](std::unique_ptr<Module> MPart) {
+    // We want to clone the module in a new context to multi-thread the codegen.
+    // We do it by serializing partition modules to bitcode (while still on the
+    // main thread, in order to avoid data races) and spinning up new threads
+    // which deserialize the partitions into separate contexts.
+    // FIXME: Provide a more direct way to do this in LLVM.
+    SmallVector<char, 0> BC;
+    raw_svector_ostream BCOS(BC);
+    WriteBitcodeToFile(MPart.get(), BCOS);
+
+    llvm::raw_pwrite_stream *ThreadOS = OSs[Threads.size()];
+    Threads.emplace_back(
+        [TheTarget, CPU, Features, Options, RM, CM, OL,
+         ThreadOS](const SmallVector<char, 0> &BC) {
+          LLVMContext Ctx;
+          ErrorOr<std::unique_ptr<Module>> MOrErr =
+              parseBitcodeFile(MemoryBufferRef(StringRef(BC.data(), BC.size()),
+                                               "<split-module>"),
+                               Ctx);
+          if (!MOrErr)
+            report_fatal_error("Failed to read bitcode");
+          std::unique_ptr<Module> MPartInCtx = std::move(MOrErr.get());
+
+          codegen(MPartInCtx.get(), *ThreadOS, TheTarget, CPU, Features,
+                  Options, RM, CM, OL);
+        },
+        // Pass BC using std::move to ensure that it get moved rather than
+        // copied into the thread's context.
+        std::move(BC));
+  });
+
+  for (std::thread &T : Threads)
+    T.join();
+
+  return {};
+}

llvm/trunk/lib/LTO/LTOCodeGenerator.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/LTO/LTOCodeGenerator.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Analysis/Passes.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Bitcode/ReaderWriter.h"
+#include "llvm/CodeGen/ParallelCG.h"
 #include "llvm/CodeGen/RuntimeLibcalls.h"
 #include "llvm/Config/config.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/DiagnosticPrinter.h"
 #include "llvm/IR/LLVMContext.h"
bool LTOCodeGenerator::compileOptimizedToFile(const char **name,
   if (EC) {
     errMsg = EC.message();
     return false;
   }
 
   // generate object file
   tool_output_file objFile(Filename.c_str(), FD);
 
-  bool genResult = compileOptimized(objFile.os(), errMsg);
+  bool genResult = compileOptimized(&objFile.os(), errMsg);
   objFile.os().close();
   if (objFile.os().has_error()) {
     objFile.os().clear_error();
     sys::fs::remove(Twine(Filename));
     return false;
   }
 
   objFile.keep();
bool LTOCodeGenerator::optimize(bool DisableInline,
   PMB.populateLTOPassManager(passes);
 
   // Run our queue of passes all at once now, efficiently.
   passes.run(*MergedModule);
 
   return true;
 }
 
-bool LTOCodeGenerator::compileOptimized(raw_pwrite_stream &out,
+bool LTOCodeGenerator::compileOptimized(ArrayRef<raw_pwrite_stream *> out,
                                         std::string &errMsg) {
   if (!this->determineTarget(errMsg))
     return false;
 
-  legacy::PassManager codeGenPasses;
+  legacy::PassManager preCodeGenPasses;
 
   // If the bitcode files contain ARC code and were compiled with optimization,
   // the ObjCARCContractPass must be run, so do it unconditionally here.
-  codeGenPasses.add(createObjCARCContractPass());
+  preCodeGenPasses.add(createObjCARCContractPass());
+  preCodeGenPasses.run(*MergedModule);
 
-  if (TargetMach->addPassesToEmitFile(codeGenPasses, out,
-                                      TargetMachine::CGFT_ObjectFile)) {
-    errMsg = "target file type not supported";
-    return false;
-  }
-
-  // Run the code generator, and write object file
-  codeGenPasses.run(*MergedModule);
+  // Do code generation. We need to preserve the module in case the client calls
+  // writeMergedModules() after compilation, but we only need to allow this at
+  // parallelism level 1. This is achieved by having splitCodeGen return the
+  // original module at parallelism level 1 which we then assign back to
+  // MergedModule.
+  MergedModule =
+      splitCodeGen(std::move(MergedModule), out, MCpu, FeatureStr, Options,
+                   RelocModel, CodeModel::Default, CGOptLevel);
 
   return true;
 }
 
 /// setCodeGenDebugOptions - Set codegen debugging options to aid in debugging
 /// LTO problems.
 void LTOCodeGenerator::setCodeGenDebugOptions(const char *options) {
   for (std::pair<StringRef, StringRef> o = getToken(options);

llvm/trunk/test/LTO/X86/parallel.ll

+; RUN: llvm-as -o %t.bc %s
+; RUN: llvm-lto -exported-symbol=foo -exported-symbol=bar -j2 -o %t.o %t.bc
+; RUN: llvm-nm %t.o.0 | FileCheck --check-prefix=CHECK0 %s
+; RUN: llvm-nm %t.o.1 | FileCheck --check-prefix=CHECK1 %s
+
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK0-NOT: bar
+; CHECK0: T foo
+; CHECK0-NOT: bar
+define void @foo() {
+  call void @bar()
+  ret void
+}
+
+; CHECK1-NOT: foo
+; CHECK1: T bar
+; CHECK1-NOT: foo
+define void @bar() {
+  call void @foo()
+  ret void
+}

llvm/trunk/tools/llvm-lto/llvm-lto.cpp

 #include "llvm/LTO/LTOCodeGenerator.h"
 #include "llvm/LTO/LTOModule.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/PrettyStackTrace.h"
 #include "llvm/Support/Signals.h"
 #include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/ToolOutputFile.h"
 #include "llvm/Support/raw_ostream.h"
+#include <list>
 
 using namespace llvm;
 
 static cl::opt<char>
 OptLevel("O",
          cl::desc("Optimization level. [-O0, -O1, -O2, or -O3] "
                   "(default = '-O2')"),
          cl::Prefix,

 static cl::opt<bool> ListSymbolsOnly(
     "list-symbols-only", cl::init(false),
     cl::desc("Instead of running LTO, list the symbols in each IR file"));
 
 static cl::opt<bool> SetMergedModule(
     "set-merged-module", cl::init(false),
     cl::desc("Use the first input module as the merged module"));
 
+static cl::opt<unsigned> Parallelism("j", cl::Prefix, cl::init(1),
+                                     cl::desc("Number of backend threads"));
+
 namespace {
 struct ModuleInfo {
   std::vector<bool> CanBeHidden;
 };
 }
 
 static void handleDiagnostics(lto_codegen_diagnostic_severity_t Severity,
                               const char *Msg, void *) {
for (unsigned i = 0; i < MAttrs.size(); ++i) {
     attrs.append(MAttrs[i]);
   }
 
   if (!attrs.empty())
     CodeGen.setAttr(attrs.c_str());
 
   if (!OutputFilename.empty()) {
     std::string ErrorInfo;
-    std::unique_ptr<MemoryBuffer> Code = CodeGen.compile(
-        DisableInline, DisableGVNLoadPRE, DisableLTOVectorization, ErrorInfo);
-    if (!Code) {
-      errs() << argv[0]
-             << ": error compiling the code: " << ErrorInfo << "\n";
+    if (!CodeGen.optimize(DisableInline, DisableGVNLoadPRE,
+                          DisableLTOVectorization, ErrorInfo)) {
+      errs() << argv[0] << ": error optimizing the code: " << ErrorInfo << "\n";
       return 1;
     }
 
+    std::list<tool_output_file> OSs;
+    std::vector<raw_pwrite_stream *> OSPtrs;
+    for (unsigned I = 0; I != Parallelism; ++I) {
+      std::string PartFilename = OutputFilename;
+      if (Parallelism != 1)
+        PartFilename += "." + utostr(I);
       std::error_code EC;
-    raw_fd_ostream FileStream(OutputFilename, EC, sys::fs::F_None);
+      OSs.emplace_back(PartFilename, EC, sys::fs::F_None);
       if (EC) {
-      errs() << argv[0] << ": error opening the file '" << OutputFilename
+        errs() << argv[0] << ": error opening the file '" << PartFilename
                << "': " << EC.message() << "\n";
         return 1;
       }
+      OSPtrs.push_back(&OSs.back().os());
+    }
 
-    FileStream.write(Code->getBufferStart(), Code->getBufferSize());
+    if (!CodeGen.compileOptimized(OSPtrs, ErrorInfo)) {
+      errs() << argv[0] << ": error compiling the code: " << ErrorInfo << "\n";
+      return 1;
+    }
+
+    for (tool_output_file &OS : OSs)
+      OS.keep();
   } else {
+    if (Parallelism != 1) {
+      errs() << argv[0] << ": -j must be specified together with -o\n";
+      return 1;
+    }
+
     std::string ErrorInfo;
     const char *OutputName = nullptr;
     if (!CodeGen.compile_to_file(&OutputName, DisableInline,
                                  DisableGVNLoadPRE, DisableLTOVectorization,
                                  ErrorInfo)) {
       errs() << argv[0]
              << ": error compiling the code: " << ErrorInfo
              << "\n";
       return 1;
     }
 
     outs() << "Wrote native object file '" << OutputName << "'\n";
   }
 
   return 0;
 }