Index: ELF/Config.h
===================================================================
--- ELF/Config.h
+++ ELF/Config.h
@@ -144,6 +144,7 @@
   uint64_t ImageBase;
   uint64_t MaxPageSize;
   uint64_t ZStackSize;
+  unsigned BuildIdChunkSize = 1024 * 1024;
   unsigned LtoPartitions;
   unsigned LtoO;
   unsigned Optimize;
Index: ELF/SyntheticSections.h
===================================================================
--- ELF/SyntheticSections.h
+++ ELF/SyntheticSections.h
@@ -25,6 +25,11 @@
 protected:
   BuildIdSection(size_t HashSize);
   std::vector<uint8_t> Buf;
+
+  void doTree(llvm::ArrayRef<uint8_t> Buf,
+              std::function<void(ArrayRef<uint8_t> Job, uint8_t *Dest)> Worker);
+
+  size_t HashSize;
 };
 
 template <class ELFT>
Index: ELF/SyntheticSections.cpp
===================================================================
--- ELF/SyntheticSections.cpp
+++ ELF/SyntheticSections.cpp
@@ -18,9 +18,11 @@
 #include "Config.h"
 #include "Error.h"
 #include "InputFiles.h"
+#include "Memory.h"
 #include "OutputSections.h"
 #include "Strings.h"
 
+#include "lld/Core/Parallel.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/MD5.h"
 #include "llvm/Support/RandomNumberGenerator.h"
@@ -39,7 +41,8 @@
 template <class ELFT>
 BuildIdSection<ELFT>::BuildIdSection(size_t HashSize)
     : InputSection<ELFT>(SHF_ALLOC, SHT_NOTE, 1, ArrayRef<uint8_t>(),
-                         ".note.gnu.build-id") {
+                         ".note.gnu.build-id"),
+      HashSize(HashSize) {
   Buf.resize(16 + HashSize);
   const endianness E = ELFT::TargetEndianness;
   write32<E>(Buf.data(), 4);                   // Name size
@@ -55,28 +58,66 @@
 }
 
 template <class ELFT>
+void BuildIdSection<ELFT>::doTree(
+    llvm::ArrayRef<uint8_t> Buf,
+    std::function<void(ArrayRef<uint8_t> Job, uint8_t *Dest)> Worker) {
+  size_t NumChunks = (Buf.size() - 1) / Config->BuildIdChunkSize + 1;
+  MutableArrayRef<uint8_t> Tree = {
+      BAlloc.template Allocate<uint8_t>(NumChunks * HashSize),
+      NumChunks * HashSize};
+
+  auto CallWorker = [&](size_t Id) {
+    ArrayRef<uint8_t> Part = Buf.drop_front(Id * Config->BuildIdChunkSize)
+                                 .take_front(Config->BuildIdChunkSize);
+    Worker(Part, Tree.data() + Id * HashSize);
+  };
+
+  std::vector<size_t> Tasks(NumChunks);
+  for (size_t I = 0; I < NumChunks; ++I)
+    Tasks[I] = I;
+
+  if (Config->Threads)
+    parallel_for_each(Tasks.begin(), Tasks.end(),
+                      [=](size_t Id) { CallWorker(Id); });
+  else
+    std::for_each(Tasks.begin(), Tasks.end(),
+                  [=](size_t Id) { CallWorker(Id); });
+
+  Worker(Tree, this->getOutputLoc((uint8_t *)Buf.begin()) + 16);
+}
+
+template <class ELFT>
 void BuildIdFastHash<ELFT>::writeBuildId(MutableArrayRef<uint8_t> Buf) {
-  const endianness E = ELFT::TargetEndianness;
+  auto DoHash = [this](ArrayRef<uint8_t> Job, uint8_t *Dest) {
+    uint64_t Hash = xxHash64(toStringRef(Job));
+    write64<ELFT::TargetEndianness>(Dest, Hash);
+  };
 
-  // 64-bit xxhash
-  uint64_t Hash = xxHash64(toStringRef(Buf));
-  write64<E>(this->getOutputLoc(Buf.begin()) + 16, Hash);
+  doTree(Buf, [&](ArrayRef<uint8_t> Job, uint8_t *Dest) { DoHash(Job, Dest); });
 }
 
 template <class ELFT>
 void BuildIdMd5<ELFT>::writeBuildId(MutableArrayRef<uint8_t> Buf) {
-  MD5 Hash;
-  Hash.update(Buf);
-  MD5::MD5Result Res;
-  Hash.final(Res);
-  memcpy(this->getOutputLoc(Buf.begin()) + 16, Res, 16);
+  auto DoHash = [this](ArrayRef<uint8_t> Job, uint8_t *Dest) {
+    MD5 Hash;
+    Hash.update(Job);
+    MD5::MD5Result Res;
+    Hash.final(Res);
+    memcpy(Dest, Res, HashSize);
+  };
+
+  doTree(Buf, [&](ArrayRef<uint8_t> Job, uint8_t *Dest) { DoHash(Job, Dest); });
 }
 
 template <class ELFT>
 void BuildIdSha1<ELFT>::writeBuildId(MutableArrayRef<uint8_t> Buf) {
-  SHA1 Hash;
-  Hash.update(Buf);
-  memcpy(this->getOutputLoc(Buf.begin()) + 16, Hash.final().data(), 20);
+  auto DoHash = [this](ArrayRef<uint8_t> Job, uint8_t *Dest) {
+    SHA1 Hash;
+    Hash.update(Job);
+    memcpy(Dest, Hash.final().data(), HashSize);
+  };
+
+  doTree(Buf, [&](ArrayRef<uint8_t> Job, uint8_t *Dest) { DoHash(Job, Dest); });
 }
 
 template <class ELFT>
Index: test/ELF/build-id.s
===================================================================
--- test/ELF/build-id.s
+++ test/ELF/build-id.s
@@ -16,6 +16,14 @@
 # RUN: ld.lld --build-id=md5 --build-id=none %t -o %t2
 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=NONE %s
 
+## Multithreaded cases:
+# RUN: ld.lld --build-id -threads %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=DEFAULT %s
+# RUN: ld.lld --build-id=md5 -threads %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=MD5 %s
+# RUN: ld.lld --build-id=sha1 -threads %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=SHA1 %s
+
 .globl _start
 _start:
   nop
@@ -26,12 +34,19 @@
 # DEFAULT:      Contents of section .note.test:
 # DEFAULT:      Contents of section .note.gnu.build-id:
 # DEFAULT-NEXT: 04000000 08000000 03000000 474e5500  ............GNU.
+# DEFAULT-NEXT: ab
 
 # MD5:      Contents of section .note.gnu.build-id:
 # MD5-NEXT: 04000000 10000000 03000000 474e5500  ............GNU.
+# MD5-NEXT: 29
 
 # SHA1:      Contents of section .note.gnu.build-id:
 # SHA1-NEXT: 04000000 14000000 03000000 474e5500  ............GNU.
+# SHA1-NEXT: b1
+
+# TREE:      Contents of section .note.gnu.build-id:
+# TREE-NEXT: 04000000 14000000 03000000 474e5500  ............GNU.
+# TREE-NEXT: 18
 
 # UUID:      Contents of section .note.gnu.build-id:
 # UUID-NEXT: 04000000 10000000 03000000 474e5500  ............GNU.