Index: ELF/ICF.cpp
===================================================================
--- ELF/ICF.cpp
+++ ELF/ICF.cpp
@@ -59,10 +59,12 @@
 #include "Config.h"
 #include "SymbolTable.h"
 
+#include "lld/Core/Parallel.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/Object/ELF.h"
 #include "llvm/Support/ELF.h"
 #include <algorithm>
+#include <mutex>
 
 using namespace lld;
 using namespace lld::elf;
@@ -95,6 +97,7 @@
 
   std::vector<InputSection<ELFT> *> Sections;
   std::vector<Range> Ranges;
+  std::mutex Mu;
 
   // The main loop is repeated until we get a convergence.
   bool Repeat = false; // If Repeat is true, we need to repeat.
@@ -143,14 +146,31 @@
       return;
 
     // Now we split [R.Begin, R.End) into [R.Begin, Mid) and [Mid, R.End).
-    if (Mid - R->Begin > 1)
+    if (Mid - R->Begin > 1) {
+      std::lock_guard<std::mutex> Lock(Mu);
       Ranges.push_back({R->Begin, Mid});
+    }
     R->Begin = Mid;
 
     // Update GroupIds for the new group members. We use the index of
     // the group first member as a group ID because that is unique.
+    //
+    // Note on GroupId[0] and GroupId[1]: we have two storages for
+    // group ids, and we are using them alternately on each
+    // iteration. This is for concurrency. We use one of the two for
+    // reading, and the other for writing (which in turn will be used
+    // for reading on the next iteration.)
+    //
+    // Recall that other threads may be working on other ranges. They
+    // may be reading group ids that we are about to update. We cannot
+    // update group ids directly because it breaks the invariance that
+    // all sections in the same group have the same ID. In other
+    // words, the following for loop is not an atomic operation, and
+    // that is observable from other threads.
+    //
+    // By writing new ids to write-only places, we can keep the invariance.
     for (size_t I = Mid; I < R->End; ++I)
-      Sections[I]->GroupId = Mid;
+      Sections[I]->GroupId[(Cnt + 1) % 2] = Mid;
 
     // Since we have split a group, we need to repeat the main loop
     // later to obtain a convergence. Remember that.
@@ -211,7 +231,9 @@
     auto *Y = dyn_cast<InputSection<ELFT>>(DB->Section);
     if (!X || !Y)
       return false;
-    return X->GroupId != 0 && X->GroupId == Y->GroupId;
+    if (X->GroupId[Cnt % 2] == 0)
+      return false;
+    return X->GroupId[Cnt % 2] == Y->GroupId[Cnt % 2];
   };
 
   return std::equal(RelsA.begin(), RelsA.end(), RelsB.begin(), Eq);
@@ -239,14 +261,14 @@
   // guaranteed) to have the same static contents in terms of ICF.
   for (InputSection<ELFT> *S : Sections)
     // Set MSB to 1 to avoid collisions with non-hash IDs.
-    S->GroupId = getHash(S) | (uint64_t(1) << 63);
+    S->GroupId[0] = S->GroupId[1] = getHash(S) | (uint64_t(1) << 63);
 
   // From now on, sections in Sections are ordered so that sections in
   // the same group are consecutive in the vector.
   std::stable_sort(Sections.begin(), Sections.end(),
                    [](InputSection<ELFT> *A, InputSection<ELFT> *B) {
-                     if (A->GroupId != B->GroupId)
-                       return A->GroupId < B->GroupId;
+                     if (A->GroupId[0] != B->GroupId[0])
+                       return A->GroupId[0] < B->GroupId[0];
                      // Within a group, put the highest alignment
                      // requirement first, so that's the one we'll keep.
                      return B->Alignment < A->Alignment;
@@ -260,7 +282,7 @@
   for (size_t I = 0, E = Sections.size(); I < E - 1;) {
     // Let J be the first index whose element has a different ID.
     size_t J = I + 1;
-    while (J < E && Sections[I]->GroupId == Sections[J]->GroupId)
+    while (J < E && Sections[I]->GroupId[0] == Sections[J]->GroupId[0])
       ++J;
     if (J - I > 1)
       Ranges.push_back({I, J});
@@ -268,15 +290,15 @@
   }
 
   // Compare static contents and assign unique IDs for each static content.
-  std::for_each(Ranges.begin(), Ranges.end(),
-                [&](Range &R) { segregate(&R, true); });
+  parallel_for_each(Ranges.begin(), Ranges.end(),
+                    [&](Range &R) { segregate(&R, true); });
   ++Cnt;
 
   // Split groups by comparing relocations until convergence is obtained.
   do {
     Repeat = false;
-    std::for_each(Ranges.begin(), Ranges.end(),
-                  [&](Range &R) { segregate(&R, false); });
+    parallel_for_each(Ranges.begin(), Ranges.end(),
+                      [&](Range &R) { segregate(&R, false); });
     ++Cnt;
   } while (Repeat);
 
Index: ELF/InputSection.h
===================================================================
--- ELF/InputSection.h
+++ ELF/InputSection.h
@@ -289,7 +289,7 @@
   void relocateNonAlloc(uint8_t *Buf, llvm::ArrayRef<RelTy> Rels);
 
   // Used by ICF.
-  uint64_t GroupId = 0;
+  uint64_t GroupId[2] = {0, 0};
 
   // Called by ICF to merge two input sections.
   void replace(InputSection<ELFT> *Other);