Index: ELF/Config.h
===================================================================
--- ELF/Config.h
+++ ELF/Config.h
@@ -31,7 +31,7 @@
 };
 
 // For --build-id.
-enum class BuildIdKind { None, Fast, Md5, Sha1, Hexstring, Uuid };
+enum class BuildIdKind { None, Fast, Md5, Sha1, Tree, Hexstring, Uuid };
 
 // For --discard-{all,locals,none}.
 enum class DiscardPolicy { Default, All, Locals, None };
Index: ELF/Driver.cpp
===================================================================
--- ELF/Driver.cpp
+++ ELF/Driver.cpp
@@ -554,6 +554,8 @@
       Config->BuildId = BuildIdKind::Md5;
     } else if (S == "sha1") {
       Config->BuildId = BuildIdKind::Sha1;
+    } else if (S == "tree") {
+      Config->BuildId = BuildIdKind::Tree;
     } else if (S == "uuid") {
       Config->BuildId = BuildIdKind::Uuid;
     } else if (S == "none") {
Index: ELF/InputSection.h
===================================================================
--- ELF/InputSection.h
+++ ELF/InputSection.h
@@ -365,12 +365,20 @@
   void writeBuildId(ArrayRef<uint8_t> Buf) override;
 };
 
-template <class ELFT> class BuildIdSha1 final : public BuildIdSection<ELFT> {
+template <class ELFT> class BuildIdSha1 : public BuildIdSection<ELFT> {
 public:
   BuildIdSha1() : BuildIdSection<ELFT>(20) {}
   void writeBuildId(ArrayRef<uint8_t> Buf) override;
 };
 
+template <class ELFT> class BuildIdTree final : public BuildIdSha1<ELFT> {
+  typedef BuildIdSha1<ELFT> Base;
+
+public:
+  BuildIdTree() : BuildIdSha1<ELFT>() {}
+  void writeBuildId(ArrayRef<uint8_t> Buf) override;
+};
+
 template <class ELFT> class BuildIdUuid final : public BuildIdSection<ELFT> {
 public:
   BuildIdUuid() : BuildIdSection<ELFT>(16) {}
Index: ELF/InputSection.cpp
===================================================================
--- ELF/InputSection.cpp
+++ ELF/InputSection.cpp
@@ -13,10 +13,12 @@
 #include "Error.h"
 #include "InputFiles.h"
 #include "LinkerScript.h"
+#include "Memory.h"
 #include "OutputSections.h"
 #include "Target.h"
 #include "Thunks.h"
 
+#include "lld/Core/Parallel.h"
 #include "llvm/Support/Compression.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/RandomNumberGenerator.h"
@@ -891,6 +893,39 @@
   memcpy(this->OutputLoc + 16, Hash.final().data(), 20);
 }
 
+// If threads are used, --build-id=tree splits input data by chunks.
+// MD5 hash is calculated for each one and then SHA1 hash is
+// calculated for result sequence.
+// If threads are not used, --build-id=tree behaves as a regular sha1.
+template <class ELFT>
+void BuildIdTree<ELFT>::writeBuildId(ArrayRef<uint8_t> Buf) {
+  if (!Config->Threads) {
+    Base::writeBuildId(Buf);
+    return;
+  }
+
+  // Default chunk size is 1 megabyte.
+  const size_t ChunkSize = 1024 * 1024;
+  size_t NumChunks = (Buf.size() - 1) / ChunkSize + 1;
+
+  const size_t Md5Len = 16;
+  uint8_t *HashLine = BAlloc.template Allocate<uint8_t>(NumChunks * Md5Len);
+
+  std::vector<size_t> Hashes(NumChunks);
+  for (size_t I = 0; I < NumChunks; ++I)
+    Hashes[I] = I;
+
+  parallel_for_each(Hashes.begin(), Hashes.end(), [=](size_t Id) {
+    MD5 Hash;
+    Hash.update(Buf.drop_front(Id * ChunkSize).take_front(ChunkSize));
+    MD5::MD5Result Res;
+    Hash.final(Res);
+    memcpy(HashLine + Id * Md5Len, Res, Md5Len);
+  });
+
+  Base::writeBuildId(ArrayRef<uint8_t>(HashLine, NumChunks * Md5Len));
+}
+
 template <class ELFT>
 void BuildIdUuid<ELFT>::writeBuildId(ArrayRef<uint8_t> Buf) {
   if (getRandomBytes(this->OutputLoc + 16, 16))
@@ -962,6 +997,11 @@
 template class elf::BuildIdSha1<ELF64LE>;
 template class elf::BuildIdSha1<ELF64BE>;
 
+template class elf::BuildIdTree<ELF32LE>;
+template class elf::BuildIdTree<ELF32BE>;
+template class elf::BuildIdTree<ELF64LE>;
+template class elf::BuildIdTree<ELF64BE>;
+
 template class elf::BuildIdUuid<ELF32LE>;
 template class elf::BuildIdUuid<ELF32BE>;
 template class elf::BuildIdUuid<ELF64LE>;
Index: ELF/Writer.cpp
===================================================================
--- ELF/Writer.cpp
+++ ELF/Writer.cpp
@@ -170,6 +170,8 @@
     BuildId.reset(new BuildIdMd5<ELFT>);
   else if (Config->BuildId == BuildIdKind::Sha1)
     BuildId.reset(new BuildIdSha1<ELFT>);
+  else if (Config->BuildId == BuildIdKind::Tree)
+    BuildId.reset(new BuildIdTree<ELFT>);
   else if (Config->BuildId == BuildIdKind::Uuid)
     BuildId.reset(new BuildIdUuid<ELFT>);
   else if (Config->BuildId == BuildIdKind::Hexstring)
Index: test/ELF/build-id.s
===================================================================
--- test/ELF/build-id.s
+++ test/ELF/build-id.s
@@ -7,6 +7,10 @@
 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=MD5 %s
 # RUN: ld.lld --build-id=sha1 %t -o %t2
 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=SHA1 %s
+# RUN: ld.lld --build-id=tree %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=SHA1 %s
+# RUN: ld.lld --build-id=tree -threads %t -o %t2
+# RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=TREE %s
 # RUN: ld.lld --build-id=uuid %t -o %t2
 # RUN: llvm-objdump -s %t2 | FileCheck -check-prefix=UUID %s
 # RUN: ld.lld --build-id=0x12345678 %t -o %t2
@@ -32,6 +36,11 @@
 
 # SHA1:      Contents of section .note.gnu.build-id:
 # SHA1-NEXT: 04000000 14000000 03000000 474e5500  ............GNU.
+# SHA1-NEXT: 58
+
+# 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.