[ELF/LTO] Parallel Codegen for LLD

[davide]

Summary

This should be ready'ish for review now.

[davide]

With/without patch (4 threads with the patch): Release + DebugInfo (without assert) linking clang.

real    22m27.724s
user    34m21.325s
sys     0m28.535s

real    28m10.310s
user    27m59.016s
sys     0m10.189s

[pcc]

What program is that?

[davide]

In D18999#397971, @pcc wrote:

What program is that?

Updated comment, sorry hit 'submit' too quickly.

[davide]

Release without debug info (clang):

real    14m56.917s
user    23m47.331s
sys     0m8.045s

real    23m17.522s
user    23m13.189s
sys     0m3.422s

[ruiu]

ELF/LTO.cpp

166

Because NumThreads is 1, nothing would run in parallel?

[davide]

ELF/LTO.cpp

166

Yes, I have another patch to add an option to specify the number of threads. I put this up to review to understand if the logic is sound.
I'm collecting numbers in multiple configurations (1,2,3,4 threads).
The previous comments in the review have some very early numbers using 4 threads.

Cheers,

Davide

[davide]

On a second thought, added the option (in case also somebody wants to play with it).

[• rafael]

From 28m10.310s to 22m27.724s when using 4 threads is a pretty small speedup.

Any idea what is slow? Is it just that each of the 1/4 sized chunks is still slow? Is the split not even in compile time?

What is the impact in output size. Even better if you have performance numbers of the linked program.

ELF/LTO.cpp

44

Drop the () around many.

143

Is this related to parallel LTO?

[davide]

I agree I expected a bigger speedup. I'll investigate further (and post more precise numbers) ASAP.

ELF/LTO.cpp

143

you use the returned type as argument to codeine.

[davide]

ELF/LTO.cpp

143

*codegen.

[pcc]

Any idea what is slow? Is it just that each of the 1/4 sized chunks is still slow? Is the split not even in compile time?

Parallel LTO codegen is highly beholden to Amdahl's law. With parallel LTO codegen there is by default a large serial optimization phase at the start, which is basically the regular LTO optimization pipeline. The only part we parallelize is the backend. Davide's numbers seem about right if he was not using an --lto-O flag to reduce the opt level (which basically turns off most of the LTO-stage optimizers, so it's most useful if you're using something like -fsanitize=cfi).

Even at lower LTO opt levels, there's a significant amount of serial time spent splitting, serializing and deserializing the partitions. With debug info enabled, the debug info needs to be duplicated between the partitions as well. The best numbers we saw were a roughly 2x speedup with >4 threads, without debug info and at opt level 1.

What we found was that parallel LTO codegen is most useful when you don't mind throwing CPU and RAM at the problem of saving a moderately sized amount of time linking your program. It doesn't completely solve the scalability problem, which is why I've been working towards getting ThinLTO supported in LLD, as the scalability story is much better there.

[ruiu]

ELF/Driver.cpp

324

Move this before Config->Optimize to sort these lines.

ELF/LTO.cpp

42–43

Move this line just before raw_fd_ostream OS... so that the definition gets closer to use.

43

I'd spell this variable Filename as one word.

44

I found that appending an empty string is a bit confusing here. I'd probably do

if (Many)
  Filename += utostr(I);

143

This function needs a comment.

146

Where does this MAttrs come from?

166

Why don't you just use Config->CGThreads as the number of threads?

185

Remove {}.

ELF/Options.td

241–242

I prefer --thread-count because gold has that option.

ELF/SymbolTable.cpp

132

Move this code before the enclosing for-loop. (Because the entire for-loop is to replace bitcode symbols.)

[pcc]

ELF/Options.td

241–242

Gold's --thread-count does not affect LTO. Furthermore, parallel LTO codegen can result in the linker producing different binaries based on the number of threads, and users of --thread-count probably wouldn't expect that option to change the binary. I think this should probably be something prefixed with --lto-.

[davide]

ELF/Options.td

241–242

That option has a different semantic. -jobs is what the plugin uses.
If you prefer another name, I'm all for it, but I wouldn't clash.

ELF/SymbolTable.cpp

132

Which code in particular?

[ruiu]

ELF/Options.td

241–242

Then maybe --lto-thread-count or --lto-jobs?

ELF/SymbolTable.cpp

132

Sorry, I meant this comment.

[• rafael]

I cced Eric who seems to think that it should be possible to avoid having multiple TargetMachines, which would be the perfect solution to this problem.

[echristo]

You should be able to avoid it, you just need to handle resetTargetOptions first (at least). You'll also need an optional lock on getSubtarget to deal with that. Those are the only problems I can think of off the top of my head.

-eric

[llvm-commits]

What about the subtargets themselves?

[echristo]

Probably should check, but I don't -think- there's anything mutable there. If there is it should be fixed.

[davide]

Apparently I and pcc replied at the same time.

In D18999#400612, @rafael wrote:

I cced Eric who seems to think that it should be possible to avoid having multiple TargetMachines, which would be the perfect solution to this problem.

In D18999#400612, @rafael wrote:

I cced Eric who seems to think that it should be possible to avoid having multiple TargetMachines, which would be the perfect solution to this problem.

So, we currently work around the problem with a Factory.
I opened https://llvm.org/bugs/show_bug.cgi?id=27361 so we don't lose track of this possible work (and I hope I or somebody else can get to it at some point)

[• rafael]

So, we currently work around the problem with a Factory.

You mean we *can* work around it, right? In this change we still have
two code paths that create a TargetMachine.

What we can do to work around the problem if fixing pr27361 is too
much work for now is passing a std::function() with no arguments that
returns a std::unique_ptr<TargetMachine> to splitCodeGen.

That way we can use the same code to create a TargetMachine is both places.

Cheers,
Rafael

[davide]

Addressed everybody's comments hopefully. The patch is smaller now.

[ruiu]

ELF/Config.h

97

Since this is for --lto-jobs, I'd name LtoJobs.

ELF/LTO.cpp

144

Instead of defining NumThreads, use Config->LtoJobs directly.

155

Does

[&]() { return getTargetMachine; }

work?

[mehdi_amini]

ELF/LTO.cpp

155

Rather: [this] () { return getTargetMachine(); }

[davide]

ELF/LTO.cpp

144

No, NumThreads is also used later in the function.

[ruiu]

This is looking fine, but I'll let someone who's working on LTO to sign off.

[pcc]

Please add a test showing that we can link a program with 2 or more partitions.

[davide]

Add a test as requested by Peter.

[pcc]

LGTM

[davide]

Committed thusly (r266484)

ELF/Config.h

struct Configuration {
   bool ZNodelete;
   bool ZNow;
   bool ZOrigin;
   bool ZRelro;
   BuildIdKind BuildId = BuildIdKind::None;
   ELFKind EKind = ELFNoneKind;
   uint16_t EMachine = llvm::ELF::EM_NONE;
   uint64_t EntryAddr = -1;
+  unsigned LtoJobs;
   unsigned LtoO;
   unsigned Optimize;
 };
 
 // The only instance of Configuration struct.
 extern Configuration *Config;
 
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/Driver.cpp

void LinkerDriver::readConfigs(opt::InputArgList &Args) {
   Config->OutputFile = getString(Args, OPT_o);
   Config->SoName = getString(Args, OPT_soname);
   Config->Sysroot = getString(Args, OPT_sysroot);
 
   Config->Optimize = getInteger(Args, OPT_O, 0);
   Config->LtoO = getInteger(Args, OPT_lto_O, 2);
   if (Config->LtoO > 3)
     error("invalid optimization level for LTO: " + getString(Args, OPT_lto_O));
+  Config->LtoJobs = getInteger(Args, OPT_lto_jobs, 1);
+  if (Config->LtoJobs == 0)
+    error("number of threads must be > 0");
 
   Config->ZExecStack = hasZOption(Args, "execstack");
   Config->ZNodelete = hasZOption(Args, "nodelete");
   Config->ZNow = hasZOption(Args, "now");
   Config->ZOrigin = hasZOption(Args, "origin");
   Config->ZRelro = !hasZOption(Args, "norelro");
 
   if (Config->Relocatable)

ELF/LTO.h

 namespace elf {
 
 class BitcodeFile;
 class InputFile;
 
 class BitcodeCompiler {
 public:
   void add(BitcodeFile &F);
-  std::unique_ptr<InputFile> compile();
+  std::vector<std::unique_ptr<InputFile>> compile();
 
   BitcodeCompiler()
       : Combined(new llvm::Module("ld-temp.o", Context)), Mover(*Combined) {}
 
 private:
-  llvm::TargetMachine *getTargetMachine();
+  std::vector<std::unique_ptr<InputFile>> runSplitCodegen();
+  std::unique_ptr<llvm::TargetMachine> getTargetMachine();
 
   llvm::LLVMContext Context;
   std::unique_ptr<llvm::Module> Combined;
   llvm::IRMover Mover;
-  SmallString<0> OwningData;
+  std::vector<SmallString<0>> OwningData;
   std::unique_ptr<MemoryBuffer> MB;
   llvm::StringSet<> InternalizedSyms;
+  std::string TheTriple;
 };
 }
 }
 
 #endif

ELF/LTO.cpp

 #include "Config.h"
 #include "Error.h"
 #include "InputFiles.h"
 #include "Symbols.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Bitcode/ReaderWriter.h"
 #include "llvm/CodeGen/CommandFlags.h"
+#include "llvm/CodeGen/ParallelCG.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/Linker/IRMover.h"
 #include "llvm/Support/StringSaver.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/Utils/ModuleUtils.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
 
 using namespace llvm;
 using namespace llvm::object;
 using namespace llvm::ELF;
 
 using namespace lld;
 using namespace lld::elf;
 
 // This is for use when debugging LTO.
-static void saveLtoObjectFile(StringRef Buffer) {
+static void saveLtoObjectFile(StringRef Buffer, unsigned I, bool Many) {
+  SmallString<128> Filename = Config->OutputFile;
+  if (Many)
+    Filename += utostr(I);
+  Filename += ".lto.o";
   std::error_code EC;
-  raw_fd_ostream OS(Config->OutputFile.str() + ".lto.o", EC,
-                    sys::fs::OpenFlags::F_None);
+  raw_fd_ostream OS(Filename, EC, sys::fs::OpenFlags::F_None);
   check(EC);
   OS << Buffer;
 }
 
 // This is for use when debugging LTO.
 static void saveBCFile(Module &M, StringRef Suffix) {
   std::error_code EC;
   raw_fd_ostream OS(Config->OutputFile.str() + Suffix.str(), EC,
                     sys::fs::OpenFlags::F_None);

 }
 
 static void internalize(GlobalValue &GV) {
   assert(!GV.hasLocalLinkage() &&
          "Trying to internalize a symbol with local linkage!");
   GV.setLinkage(GlobalValue::InternalLinkage);
 }
 
+std::vector<std::unique_ptr<InputFile>> BitcodeCompiler::runSplitCodegen() {
+  unsigned NumThreads = Config->LtoJobs;
+  OwningData.resize(NumThreads);
+
+  std::list<raw_svector_ostream> OSs;
+  std::vector<raw_pwrite_stream *> OSPtrs;
+  for (SmallString<0> &Obj : OwningData) {
+    OSs.emplace_back(Obj);
+    OSPtrs.push_back(&OSs.back());
+  }
+
+  splitCodeGen(std::move(Combined), OSPtrs, {},
+               [this]() { return getTargetMachine(); });
+
+  std::vector<std::unique_ptr<InputFile>> ObjFiles;
+  for (SmallString<0> &Obj : OwningData)
+    ObjFiles.push_back(createObjectFile(
+        MemoryBufferRef(Obj, "LLD-INTERNAL-combined-lto-object")));
+
+  if (Config->SaveTemps)
+    for (unsigned I = 0; I < NumThreads; ++I)
+      saveLtoObjectFile(OwningData[I], I, NumThreads > 1);
+
+  return ObjFiles;
+}
+
 // Merge all the bitcode files we have seen, codegen the result
 // and return the resulting ObjectFile.
-std::unique_ptr<InputFile> BitcodeCompiler::compile() {
+std::vector<std::unique_ptr<InputFile>> BitcodeCompiler::compile() {
+  TheTriple = Combined->getTargetTriple();
   for (const auto &Name : InternalizedSyms) {
     GlobalValue *GV = Combined->getNamedValue(Name.first());
     assert(GV);
     internalize(*GV);
   }
 
   if (Config->SaveTemps)
     saveBCFile(*Combined, ".lto.bc");
 
   std::unique_ptr<TargetMachine> TM(getTargetMachine());
   runLTOPasses(*Combined, *TM);
 
-  raw_svector_ostream OS(OwningData);
-  legacy::PassManager CodeGenPasses;
-  if (TM->addPassesToEmitFile(CodeGenPasses, OS,
-                              TargetMachine::CGFT_ObjectFile))
-    fatal("failed to setup codegen");
-  CodeGenPasses.run(*Combined);
-  MB = MemoryBuffer::getMemBuffer(OwningData,
-                                  "LLD-INTERNAL-combined-lto-object", false);
-  if (Config->SaveTemps)
-    saveLtoObjectFile(MB->getBuffer());
-  return createObjectFile(*MB);
+  return runSplitCodegen();
 }
 
-TargetMachine *BitcodeCompiler::getTargetMachine() {
-  StringRef TripleStr = Combined->getTargetTriple();
+std::unique_ptr<TargetMachine> BitcodeCompiler::getTargetMachine() {
   std::string Msg;
-  const Target *T = TargetRegistry::lookupTarget(TripleStr, Msg);
+  const Target *T = TargetRegistry::lookupTarget(TheTriple, Msg);
   if (!T)
     fatal("target not found: " + Msg);
   TargetOptions Options = InitTargetOptionsFromCodeGenFlags();
   Reloc::Model R = Config->Pic ? Reloc::PIC_ : Reloc::Static;
-  return T->createTargetMachine(TripleStr, "", "", Options, R);
+  return std::unique_ptr<TargetMachine>(
+      T->createTargetMachine(TheTriple, "", "", Options, R));
 }

ELF/Options.td

 def version_script : Separate<["--"], "version-script">;
 def warn_execstack : Flag<["--"], "warn-execstack">;
 def warn_shared_textrel : Flag<["--"], "warn-shared-textrel">;
 def G : Separate<["-"], "G">;
 
 // Aliases for ignored options
 def alias_version_script_version_script : Joined<["--"], "version-script=">, Alias<version_script>;
 
-// Debugging/developer options
+// LTO-related options.
+def lto_jobs : Joined<["--"], "lto-jobs=">,
+  HelpText<"Number of threads to run codegen">;
 def disable_verify : Flag<["-"], "disable-verify">;
 def mllvm : Separate<["-"], "mllvm">;
 def save_temps : Flag<["-"], "save-temps">;

ELF/SymbolTable.cpp

 template <class ELFT> void SymbolTable<ELFT>::addCombinedLtoObject() {
   if (BitcodeFiles.empty())
     return;
 
   // Compile bitcode files.
   Lto.reset(new BitcodeCompiler);
   for (const std::unique_ptr<BitcodeFile> &F : BitcodeFiles)
     Lto->add(*F);
-  std::unique_ptr<InputFile> IF = Lto->compile();
-  ObjectFile<ELFT> *Obj = cast<ObjectFile<ELFT>>(IF.release());
+  std::vector<std::unique_ptr<InputFile>> IFs = Lto->compile();
 
   // Replace bitcode symbols.
+  for (auto &IF : IFs) {
+    ObjectFile<ELFT> *Obj = cast<ObjectFile<ELFT>>(IF.release());
+
     llvm::DenseSet<StringRef> DummyGroups;
     Obj->parse(DummyGroups);
     for (SymbolBody *Body : Obj->getNonLocalSymbols()) {
       Symbol *Sym = insert(Body);
       Sym->Body->setUsedInRegularObj();
       if (Sym->Body->isShared())
         Sym->Body->MustBeInDynSym = true;
       if (Sym->Body->MustBeInDynSym)
         Body->MustBeInDynSym = true;
       if (!Sym->Body->isUndefined() && Body->isUndefined())
         continue;
       Sym->Body = Body;
     }
     ObjectFiles.emplace_back(Obj);
   }
+}
 
 // Add an undefined symbol.
 template <class ELFT>
 SymbolBody *SymbolTable<ELFT>::addUndefined(StringRef Name) {
   auto *Sym = new (Alloc)
       UndefinedElf<ELFT>(Name, STB_GLOBAL, STV_DEFAULT, /*Type*/ 0, false);
   resolve(Sym);
   return Sym;

test/ELF/basic.s

 # UNKNOWN: unknown argument: --foo
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 # RUN: not ld.lld %t %t -o %t2 2>&1 | FileCheck --check-prefix=DUP %s
 # DUP: duplicate symbol: _start in {{.*}} and {{.*}}
 
 # RUN: not ld.lld %t -o %t -m wrong_emul 2>&1 | FileCheck --check-prefix=UNKNOWN_EMUL %s
 # UNKNOWN_EMUL: unknown emulation: wrong_emul
+
+# RUN: not ld.lld %t --lto-jobs=0 2>&1 | FileCheck --check-prefix=NOTHREADS %s
+# NOTHREADS: number of threads must be > 0

test/ELF/lto/parallel.ll

+; RUN: llvm-as -o %t.bc %s
+; RUN: ld.lld -m elf_x86_64 --lto-jobs=2 -save-temps -o %t %t.bc -shared
+; RUN: llvm-nm %t0.lto.o | FileCheck --check-prefix=CHECK0 %s
+; RUN: llvm-nm %t1.lto.o | 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
+}