[lld] COFF: Implement parallel LTO code generation.

[pcc]

Summary

This is exposed via a new flag /opt:lldltojobs=N, where N is the number of
code generation threads.

Depends on D12260

[ruiu]

COFF/Driver.cpp

382 ↗

(On Diff #33041)

Remove { and }.

COFF/SymbolTable.cpp

377 ↗

(On Diff #33041)

The type of Obj is not obvious from the context, so please use its real type.

377 ↗

(On Diff #33041)

Please use the real type instead of "auto".

418 ↗

(On Diff #33041)

Why std::list? (My understanding is std::list is generally slower than std::vector, and there seems no obvious reason to use that instead of std::vector here.)

420 ↗

(On Diff #33041)

Ditto

420 ↗

(On Diff #33041)

Use real type.

429 ↗

(On Diff #33041)

Ditto

429 ↗

(On Diff #33041)

Ditto

COFF/SymbolTable.h

111 ↗

(On Diff #33041)

Previously, LTOMB is a member of this class to keep the ownership of the memory buffer. Now this member owns nothing. Can we make this a function-local variable now?

[pcc]

• Address comments

COFF/Driver.cpp

382 ↗

(On Diff #33041)

Done, also for lldlto=.

COFF/SymbolTable.cpp

377 ↗

(On Diff #33041)

Done

418 ↗

(On Diff #33041)

Because I collect a vector of pointers in OSPtrs as I go. If I used std::vector here the pointers to the vector elements could be invalidated on insertion. I've added a comment here for clarity. (This is a little awkward. I posted an idea for a better API in D12260.)

420 ↗

(On Diff #33041)

Done

429 ↗

(On Diff #33041)

Done.

COFF/SymbolTable.h

111 ↗

(On Diff #33041)

We still need to own the memory buffers; the ownership in this case comes from the SmallVector objects in this data member.

[ruiu]

COFF/SymbolTable.cpp

418 ↗

(On Diff #33049)

Aha, understood. Maybe I would give an initial capacity to avoid std::vector's resizing instead of std::list, but this code is okay.

lld/trunk/COFF/Config.h

struct Configuration {
   DefinedAbsolute *SEHCount = nullptr;
 
   // Used for /opt:icf
   bool ICF = false;
 
   // Used for /opt:lldlto=N
   unsigned LTOOptLevel = 2;
 
+  // Used for /opt:lldltojobs=N
+  unsigned LTOJobs = 1;
+
   // Used for /merge:from=to (e.g. /merge:.rdata=.text)
   std::map<StringRef, StringRef> Merge;
 
   // Options for manifest files.
   ManifestKind Manifest = SideBySide;
   int ManifestID = 1;
   StringRef ManifestDependency;
   bool ManifestUAC = true;

lld/trunk/COFF/Driver.cpp

for (auto *Arg : Args.filtered(OPT_opt)) {
     }
     if (S == "lldicf") {
       Config->ICF = true;
       continue;
     }
     if (StringRef(S).startswith("lldlto=")) {
       StringRef OptLevel = StringRef(S).substr(7);
       if (OptLevel.getAsInteger(10, Config->LTOOptLevel) ||
-          Config->LTOOptLevel > 3) {
+          Config->LTOOptLevel > 3)
         error("/opt:lldlto: invalid optimization level: " + OptLevel);
-      }
+      continue;
+    if (StringRef(S).startswith("lldltojobs=")) {
+      StringRef Jobs = StringRef(S).substr(11);
+      if (Jobs.getAsInteger(10, Config->LTOJobs) || Config->LTOJobs == 0)
+        error("/opt:lldltojobs: invalid job count: " + Jobs);
       continue;
     }
     if (S != "ref" && S != "icf" && S != "noicf" &&
         S != "lbr" && S != "nolbr" &&
         !StringRef(S).startswith("icf=")) {
       error(Twine("/opt: unknown option: ") + S);
     }
   }
for (;;) {
     if (Symtab.findUnderscore("_load_config_used"))
       addUndefined(mangle("_load_config_used"));
 
     if (Symtab.queueEmpty())
       break;
     Symtab.run();
   }
 
-  // Do LTO by compiling bitcode input files to a native COFF file
-  // then link that file.
-  Symtab.addCombinedLTOObject();
+  // Do LTO by compiling bitcode input files to a set of native COFF files then
+  // link those files.
+  Symtab.addCombinedLTOObjects();
 
   // Make sure we have resolved all symbols.
   Symtab.reportRemainingUndefines(/*Resolve=*/true);
 
   // Windows specific -- if no /subsystem is given, we need to infer
   // that from entry point name.
   if (Config->Subsystem == IMAGE_SUBSYSTEM_UNKNOWN) {
     Config->Subsystem = inferSubsystem();

lld/trunk/COFF/SymbolTable.h

public:
   // for U from the symbol table, and if found, set the symbol as
   // a weak alias for U.
   void mangleMaybe(Undefined *U);
   StringRef findMangle(StringRef Name);
 
   // Print a layout map to OS.
   void printMap(llvm::raw_ostream &OS);
 
-  // Build a COFF object representing the combined contents of BitcodeFiles
-  // and add it to the symbol table. Called after all files are added and
-  // before the writer writes results to a file.
-  void addCombinedLTOObject();
+  // Build a set of COFF objects representing the combined contents of
+  // BitcodeFiles and add them to the symbol table. Called after all files are
+  // added and before the writer writes results to a file.
+  void addCombinedLTOObjects();
 
   // The writer needs to handle DLL import libraries specially in
   // order to create the import descriptor table.
   std::vector<ImportFile *> ImportFiles;
 
   // The writer needs to infer the machine type from the object files.
   std::vector<ObjectFile *> ObjectFiles;
 
private:
   void readObjects();
 
   void addSymbol(SymbolBody *New);
   void addLazy(Lazy *New, std::vector<Symbol *> *Accum);
   Symbol *insert(SymbolBody *New);
   StringRef findByPrefix(StringRef Prefix);
 
   void addMemberFile(Lazy *Body);
-  ObjectFile *createLTOObject(llvm::LTOCodeGenerator *CG);
+  void addCombinedLTOObject(ObjectFile *Obj);
+  std::vector<ObjectFile *> createLTOObjects(llvm::LTOCodeGenerator *CG);
 
   llvm::DenseMap<StringRef, Symbol *> Symtab;
 
   std::vector<std::unique_ptr<InputFile>> Files;
   std::vector<ArchiveFile *> ArchiveQueue;
   std::vector<InputFile *> ObjectQueue;
 
   std::vector<BitcodeFile *> BitcodeFiles;
-  std::unique_ptr<MemoryBuffer> LTOMB;
+  std::vector<SmallVector<char, 0>> Objs;
   llvm::BumpPtrAllocator Alloc;
 };
 
 } // namespace coff
 } // namespace lld
 
 #endif

lld/trunk/COFF/SymbolTable.cpp

for (ObjectFile *File : ObjectFiles) {
     for (SymbolBody *Body : File->getSymbols())
       if (auto *R = dyn_cast<DefinedRegular>(Body))
         if (!R->isCOMDAT() || R->isLive())
           OS << Twine::utohexstr(Config->ImageBase + R->getRVA())
              << " " << R->getName() << "\n";
   }
 }
 
-void SymbolTable::addCombinedLTOObject() {
-  if (BitcodeFiles.empty())
-    return;
-
-  // Diagnose any undefined symbols early, but do not resolve weak externals,
-  // as resolution breaks the invariant that each Symbol points to a unique
-  // SymbolBody, which we rely on to replace DefinedBitcode symbols correctly.
-  reportRemainingUndefines(/*Resolve=*/false);
-
-  // Create an object file and add it to the symbol table by replacing any
-  // DefinedBitcode symbols with the definitions in the object file.
-  LTOCodeGenerator CG;
-  CG.setOptLevel(Config->LTOOptLevel);
-  ObjectFile *Obj = createLTOObject(&CG);
-
+void SymbolTable::addCombinedLTOObject(ObjectFile *Obj) {
   for (SymbolBody *Body : Obj->getSymbols()) {
     if (!Body->isExternal())
       continue;
     // We should not see any new undefined symbols at this point, but we'll
     // diagnose them later in reportRemainingUndefines().
     StringRef Name = Body->getName();
     Symbol *Sym = insert(Body);
 
for (SymbolBody *Body : Obj->getSymbols()) {
     }
     SymbolBody *Existing = Sym->Body;
     int Comp = Existing->compare(Body);
     if (Comp == 0)
       error(Twine("LTO: unexpected duplicate symbol: ") + Name);
     if (Comp < 0)
       Sym->Body = Body;
   }
+}
+
+void SymbolTable::addCombinedLTOObjects() {
+  if (BitcodeFiles.empty())
+    return;
+
+  // Diagnose any undefined symbols early, but do not resolve weak externals,
+  // as resolution breaks the invariant that each Symbol points to a unique
+  // SymbolBody, which we rely on to replace DefinedBitcode symbols correctly.
+  reportRemainingUndefines(/*Resolve=*/false);
+
+  // Create an object file and add it to the symbol table by replacing any
+  // DefinedBitcode symbols with the definitions in the object file.
+  LTOCodeGenerator CG;
+  CG.setOptLevel(Config->LTOOptLevel);
+  std::vector<ObjectFile *> Objs = createLTOObjects(&CG);
+
+  for (ObjectFile *Obj : Objs)
+    addCombinedLTOObject(Obj);
 
   size_t NumBitcodeFiles = BitcodeFiles.size();
   run();
   if (BitcodeFiles.size() != NumBitcodeFiles)
     error("LTO: late loaded symbol created new bitcode reference");
 }
 
 // Combine and compile bitcode files and then return the result
-// as a regular COFF object file.
-ObjectFile *SymbolTable::createLTOObject(LTOCodeGenerator *CG) {
+// as a vector of regular COFF object files.
+std::vector<ObjectFile *> SymbolTable::createLTOObjects(LTOCodeGenerator *CG) {
   // All symbols referenced by non-bitcode objects must be preserved.
   for (ObjectFile *File : ObjectFiles)
     for (SymbolBody *Body : File->getSymbols())
       if (auto *S = dyn_cast<DefinedBitcode>(Body->repl()))
         CG->addMustPreserveSymbol(S->getName());
 
   // Likewise for bitcode symbols which we initially resolved to non-bitcode.
   for (BitcodeFile *File : BitcodeFiles)
else if (auto *S = dyn_cast_or_null<DefinedBitcode>(U->getWeakAlias()))
       CG->addMustPreserveSymbol(S->getName());
   }
 
   CG->setModule(BitcodeFiles[0]->takeModule());
   for (unsigned I = 1, E = BitcodeFiles.size(); I != E; ++I)
     CG->addModule(BitcodeFiles[I]->getModule());
 
   std::string ErrMsg;
-  LTOMB = CG->compile(false, false, false, ErrMsg); // take MB ownership
-  if (!LTOMB)
+  if (!CG->optimize(false, false, false, ErrMsg))
+    error(ErrMsg);
+
+  Objs.resize(Config->LTOJobs);
+  // Use std::list to avoid invalidation of pointers in OSPtrs.
+  std::list<raw_svector_ostream> OSs;
+  std::vector<raw_pwrite_stream *> OSPtrs;
+  for (SmallVector<char, 0> &Obj : Objs) {
+    OSs.emplace_back(Obj);
+    OSPtrs.push_back(&OSs.back());
+  }
+
+  if (!CG->compileOptimized(OSPtrs, ErrMsg))
     error(ErrMsg);
-  auto *Obj = new ObjectFile(LTOMB->getMemBufferRef());
-  Files.emplace_back(Obj);
-  ObjectFiles.push_back(Obj);
-  Obj->parse();
-  return Obj;
+
+  std::vector<ObjectFile *> ObjFiles;
+  for (SmallVector<char, 0> &Obj : Objs) {
+    auto *ObjFile = new ObjectFile(
+        MemoryBufferRef(StringRef(Obj.data(), Obj.size()), "<LTO object>"));
+    Files.emplace_back(ObjFile);
+    ObjectFiles.push_back(ObjFile);
+    ObjFile->parse();
+    ObjFiles.push_back(ObjFile);
+  }
+
+  return ObjFiles;
 }
 
 } // namespace coff
 } // namespace lld

lld/trunk/test/COFF/lto-parallel.ll

+; RUN: llvm-as -o %t.obj %s
+; RUN: lld-link /out:%t.exe /entry:foo /include:bar /opt:lldltojobs=2 /subsystem:console /lldmap:%t.map %t.obj
+; RUN: FileCheck %s < %t.map
+
+target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc"
+
+; CHECK: <lto object>:
+; CHECK: foo
+define void @foo() {
+  call void @bar()
+  ret void
+}
+
+; CHECK: <lto object>:
+; CHECK: bar
+define void @bar() {
+  call void @foo()
+  ret void
+}

lld/trunk/test/COFF/weak-external.test

 # RUN: yaml2obj %s > %t.obj
 # RUN: llvm-as -o %t.lto.obj %S/Inputs/weak-external.ll
 # RUN: lld-link /out:%t1.exe /entry:g /subsystem:console %t.obj
 # RUN: lld-link /out:%t2.exe /entry:g /subsystem:console /lldmap:%t2.map %t.obj %t.lto.obj
 # RUN: FileCheck %s < %t2.map
 
-# CHECK: lto-llvm{{.*}}:
+# CHECK: <lto object>:
 # CHECK-NOT: :
 # CHECK: {{ g$}}
 
 ---
 header:
   Machine:         IMAGE_FILE_MACHINE_AMD64
   Characteristics: [  ]
 sections:

lld/trunk/test/COFF/weak-external3.test

 # RUN: yaml2obj %s > %t.obj
 # RUN: llvm-as -o %t.lto.obj %S/Inputs/weak-external3.ll
 # RUN: lld-link /out:%t1.exe /entry:f /subsystem:console /lldmap:%t1.map %t.lto.obj
 # RUN: FileCheck --check-prefix=CHECK1 %s < %t1.map
 # RUN: lld-link /out:%t2.exe /entry:f /subsystem:console /lldmap:%t2.map %t.obj %t.lto.obj
 # RUN: FileCheck --check-prefix=CHECK2 %s < %t2.map
 
-# CHECK1: lto-llvm{{.*}}:
+# CHECK1: <lto object>:
 # CHECK1-NOT: :
 # CHECK1: {{ g$}}
 
 # CHECK2: weak-external3{{.*}}:
 # CHECK2-NOT: :
 # CHECK2: {{ f$}}
 
 ---