Index: ELF/InputSection.h
===================================================================
--- ELF/InputSection.h
+++ ELF/InputSection.h
@@ -145,7 +145,10 @@
   // in the output section.
   uintX_t getOffset(uintX_t Offset);
 
+  void finalizePieces();
+
 private:
+  llvm::DenseMap<uintX_t, uintX_t> OffsetMap;
   llvm::DenseSet<uintX_t> LiveOffsets;
 };
 
Index: ELF/InputSection.cpp
===================================================================
--- ELF/InputSection.cpp
+++ ELF/InputSection.cpp
@@ -508,6 +508,7 @@
   return S->SectionKind == InputSectionBase<ELFT>::Merge;
 }
 
+// Do binary search to get a section piece at a given input offset.
 template <class ELFT>
 SectionPiece *SplitInputSection<ELFT>::getSectionPiece(uintX_t Offset) {
   ArrayRef<uint8_t> D = this->getSectionData();
@@ -524,23 +525,46 @@
   return &*I;
 }
 
+// Returns the offset in an output section for a given input offset.
+// Because contents of a mergeable section is not contiguous in output,
+// it is not just an addition to a base output offset.
 template <class ELFT>
 typename ELFT::uint MergeInputSection<ELFT>::getOffset(uintX_t Offset) {
+  auto It = OffsetMap.find(Offset);
+  if (It != OffsetMap.end())
+    return It->second;
+
+  // If Offset is not at beginning of a section piece, it is not in the map.
+  // In that case we need to search from the original section piece vector.
+  // It is a slow path because binary search is slower than hash table lookup
+  // due to CPU's branch misprediction.
   SectionPiece &Piece = *this->getSectionPiece(Offset);
   assert(Piece.Live);
-
-  // Compute the Addend and if the Base is cached, return.
   uintX_t Addend = Offset - Piece.InputOff;
-  if (Piece.OutputOff != size_t(-1))
-    return Piece.OutputOff + Addend;
-
-  // Map the base to the offset in the output section and cache it.
-  ArrayRef<uint8_t> D = this->getSectionData();
-  StringRef Data((const char *)D.data(), D.size());
-  StringRef Entry = Data.substr(Piece.InputOff, Piece.size());
-  auto *MOS = static_cast<MergeOutputSection<ELFT> *>(this->OutSec);
-  Piece.OutputOff = MOS->getOffset(Entry);
-  return Piece.OutputOff + Addend;
+  uintX_t Ret = Piece.OutputOff + Addend;
+
+  // Cache the result if it's safe to do so.
+  if (!Config->Threads)
+    OffsetMap[Offset] = Ret;
+  return Ret;
+}
+
+// Create a map from input offsets to output offsets for all section pieces.
+// It is called after finalize().
+template <class ELFT> void  MergeInputSection<ELFT>::finalizePieces() {
+  OffsetMap.grow(this->Pieces.size());
+  for (SectionPiece &Piece : this->Pieces) {
+    if (!Piece.Live)
+      continue;
+    if (Piece.OutputOff == size_t(-1)) {
+      // Offsets of tail-merged strings are computed lazily.
+      auto *OutSec = static_cast<MergeOutputSection<ELFT> *>(this->OutSec);
+      ArrayRef<uint8_t> D = Piece.data();
+      StringRef S((const char *)D.data(), D.size());
+      Piece.OutputOff = OutSec->getOffset(S);
+    }
+    OffsetMap[Piece.InputOff] = Piece.OutputOff;
+  }
 }
 
 template <class ELFT>
Index: ELF/OutputSections.h
===================================================================
--- ELF/OutputSections.h
+++ ELF/OutputSections.h
@@ -93,6 +93,7 @@
   bool PageAlign = false;
 
   virtual void finalize() {}
+  virtual void finalizePieces() {}
   virtual void
   forEachInputSection(std::function<void(InputSectionBase<ELFT> *)> F) {}
   virtual void writeTo(uint8_t *Buf) {}
@@ -320,10 +321,12 @@
   void writeTo(uint8_t *Buf) override;
   unsigned getOffset(StringRef Val);
   void finalize() override;
+  void finalizePieces() override;
   bool shouldTailMerge() const;
 
 private:
   llvm::StringTableBuilder Builder;
+  std::vector<MergeInputSection<ELFT> *> Sections;
 };
 
 struct CieRecord {
Index: ELF/OutputSections.cpp
===================================================================
--- ELF/OutputSections.cpp
+++ ELF/OutputSections.cpp
@@ -1164,6 +1164,7 @@
   Sec->OutSec = this;
   this->updateAlign(Sec->Align);
   this->Header.sh_entsize = Sec->getSectionHdr()->sh_entsize;
+  Sections.push_back(Sec);
 
   bool IsString = this->Header.sh_flags & SHF_STRINGS;
 
@@ -1191,6 +1192,11 @@
   this->Header.sh_size = Builder.getSize();
 }
 
+template <class ELFT> void MergeOutputSection<ELFT>::finalizePieces() {
+  for (MergeInputSection<ELFT> *Sec : Sections)
+    Sec->finalizePieces();
+}
+
 template <class ELFT>
 StringTableSection<ELFT>::StringTableSection(StringRef Name, bool Dynamic)
     : OutputSectionBase<ELFT>(Name, SHT_STRTAB,
Index: ELF/Writer.cpp
===================================================================
--- ELF/Writer.cpp
+++ ELF/Writer.cpp
@@ -873,6 +873,11 @@
 
   if (isOutputDynamic())
     Out<ELFT>::Dynamic->finalize();
+
+  // Now that all output offsets are fixed. Finalize mergeable sections
+  // to fix their maps from input offsets to output offsets.
+  for (OutputSectionBase<ELFT> *Sec : OutputSections)
+    Sec->finalizePieces();
 }
 
 template <class ELFT> bool Writer<ELFT>::needsGot() {