Index: ELF/InputSection.h
===================================================================
--- ELF/InputSection.h
+++ ELF/InputSection.h
@@ -12,9 +12,14 @@
 
 #include "Config.h"
 #include "lld/Core/LLVM.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Object/ELF.h"
 
+namespace llvm {
+class StringTableBuilder;
+}
+
 namespace lld {
 namespace elf {
 
@@ -146,18 +151,6 @@
   // in the output section.
   std::vector<std::pair<uintX_t, uintX_t>> Offsets;
 
-  // Merge input sections may use the following special values as the output
-  // section offset:
-  enum {
-    // The piece is dead.
-    PieceDead = uintX_t(-1),
-    // The piece is live, but an offset has not yet been assigned. After offsets
-    // have been assigned, if the output section uses tail merging, the field
-    // will still have this value and the output section offset is computed
-    // lazilly.
-    PieceLive = uintX_t(-2),
-  };
-
   std::pair<std::pair<uintX_t, uintX_t> *, uintX_t>
   getRangeAndSize(uintX_t Offset);
 };
@@ -174,6 +167,24 @@
   // Translate an offset in the input section to an offset in the output
   // section.
   uintX_t getOffset(uintX_t Offset);
+
+  void prepareRanges(llvm::StringTableBuilder &Builder, bool Lazy);
+
+  // Alive ranges should be marked early during GC.
+  void setRangeLive(uintX_t Offset);
+
+  bool isRangeLive(uintX_t Offset);
+
+  // Updates or create a new range with specified parameters. If GC is enabled,
+  // and range was not marked as live, it is not created.
+  bool checkInRange(uintX_t Offset, uintX_t Size, bool IsLazy);
+
+private:
+  struct Range {
+    uintX_t Size;
+    bool IsLazy;
+  };
+  llvm::DenseMap<uintX_t, Range> AliveRanges;
 };
 
 // This corresponds to a .eh_frame section of an input file.
Index: ELF/InputSection.cpp
===================================================================
--- ELF/InputSection.cpp
+++ ELF/InputSection.cpp
@@ -439,24 +439,29 @@
 template <class ELFT>
 MergeInputSection<ELFT>::MergeInputSection(elf::ObjectFile<ELFT> *F,
                                            const Elf_Shdr *Header)
-    : SplitInputSection<ELFT>(F, Header, InputSectionBase<ELFT>::Merge) {
+    : SplitInputSection<ELFT>(F, Header, InputSectionBase<ELFT>::Merge) {}
+
+template <class ELFT>
+void MergeInputSection<ELFT>::prepareRanges(llvm::StringTableBuilder &Builder,
+                                            bool Lazy) {
   uintX_t EntSize = Header->sh_entsize;
   ArrayRef<uint8_t> D = this->getSectionData();
   StringRef Data((const char *)D.data(), D.size());
   std::vector<std::pair<uintX_t, uintX_t>> &Offsets = this->Offsets;
 
-  uintX_t V = Config->GcSections ? MergeInputSection<ELFT>::PieceDead
-                                 : MergeInputSection<ELFT>::PieceLive;
   if (Header->sh_flags & SHF_STRINGS) {
     uintX_t Offset = 0;
     while (!Data.empty()) {
       size_t End = findNull(Data, EntSize);
       if (End == StringRef::npos)
         fatal("string is not null terminated");
-      Offsets.push_back(std::make_pair(Offset, V));
       uintX_t Size = End + EntSize;
+      StringRef Entry = Data.substr(0, Size);
       Data = Data.substr(Size);
       Offset += Size;
+
+      if (checkInRange(Offset - Size, Size, Lazy))
+        Offsets.push_back(std::make_pair(Offset - Size, Builder.add(Entry)));
     }
     return;
   }
@@ -464,8 +469,12 @@
   // If this is not of type string, every entry has the same size.
   size_t Size = Data.size();
   assert((Size % EntSize) == 0);
-  for (unsigned I = 0, N = Size; I != N; I += EntSize)
-    Offsets.push_back(std::make_pair(I, V));
+  for (unsigned I = 0, N = Size; I != N; I += EntSize) {
+    if (checkInRange(I, Size, false)) {
+      uintX_t V = Builder.add(Data.substr(I, EntSize));
+      Offsets.push_back(std::make_pair(I, V));
+    }
+  }
 }
 
 template <class ELFT>
@@ -499,26 +508,53 @@
   std::pair<std::pair<uintX_t, uintX_t> *, uintX_t> T =
       this->getRangeAndSize(Offset);
   std::pair<uintX_t, uintX_t> *I = T.first;
-  uintX_t End = T.second;
   uintX_t Start = I->first;
+  Range &R = AliveRanges[Start];
 
   // Compute the Addend and if the Base is cached, return.
   uintX_t Addend = Offset - Start;
   uintX_t &Base = I->second;
-  assert(Base != MergeInputSection<ELFT>::PieceDead);
-  if (Base != MergeInputSection<ELFT>::PieceLive)
+  if (!R.IsLazy)
     return Base + 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(Start, End - Start);
+  StringRef Entry = Data.substr(Start, R.Size);
   auto *MOS = static_cast<MergeOutputSection<ELFT> *>(this->OutSec);
   Base = MOS->getOffset(Entry);
   return Base + Addend;
 }
 
 template <class ELFT>
+void MergeInputSection<ELFT>::setRangeLive(uintX_t Offset) {
+  AliveRanges[Offset] = {(uintX_t)-1, false};
+}
+
+template <class ELFT>
+bool MergeInputSection<ELFT>::isRangeLive(uintX_t Offset) {
+  if (!Config->GcSections)
+    return true;
+  return AliveRanges.count(Offset) != 0;
+}
+
+template <class ELFT>
+bool MergeInputSection<ELFT>::checkInRange(uintX_t Offset, uintX_t Size,
+                                           bool IsLazy) {
+  auto I = AliveRanges.find(Offset);
+  if (I != AliveRanges.end()) {
+    I->second = {Size, IsLazy};
+    return true;
+  }
+
+  if (Config->GcSections)
+    return false;
+
+  AliveRanges[Offset] = {Size, IsLazy};
+  return true;
+}
+
+template <class ELFT>
 MipsReginfoInputSection<ELFT>::MipsReginfoInputSection(elf::ObjectFile<ELFT> *F,
                                                        const Elf_Shdr *Hdr)
     : InputSectionBase<ELFT>(F, Hdr, InputSectionBase<ELFT>::MipsReginfo) {
Index: ELF/MarkLive.cpp
===================================================================
--- ELF/MarkLive.cpp
+++ ELF/MarkLive.cpp
@@ -142,11 +142,8 @@
   auto Enqueue = [&](ResolvedReloc<ELFT> R) {
     if (!R.Sec)
       return;
-    if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(R.Sec)) {
-      std::pair<std::pair<uintX_t, uintX_t> *, uintX_t> T =
-          MS->getRangeAndSize(R.Offset);
-      T.first->second = MergeInputSection<ELFT>::PieceLive;
-    }
+    if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(R.Sec))
+      MS->setRangeLive(R.Offset);
     if (R.Sec->Live)
       return;
     R.Sec->Live = true;
Index: ELF/OutputSections.h
===================================================================
--- ELF/OutputSections.h
+++ ELF/OutputSections.h
@@ -320,8 +320,11 @@
   void finalize() override;
   bool shouldTailMerge() const;
 
+  void prepare();
+
 private:
   llvm::StringTableBuilder Builder;
+  std::vector<MergeInputSection<ELFT> *> InputSections;
 };
 
 // FDE or CIE
Index: ELF/OutputSections.cpp
===================================================================
--- ELF/OutputSections.cpp
+++ ELF/OutputSections.cpp
@@ -1272,38 +1272,13 @@
   auto *S = cast<MergeInputSection<ELFT>>(C);
   S->OutSec = this;
   this->updateAlign(S->Align);
+  InputSections.push_back(S);
+}
 
-  ArrayRef<uint8_t> D = S->getSectionData();
-  StringRef Data((const char *)D.data(), D.size());
-  uintX_t EntSize = S->getSectionHdr()->sh_entsize;
-  this->Header.sh_entsize = EntSize;
-  MutableArrayRef<std::pair<uintX_t, uintX_t>> Offsets = S->Offsets;
-
-  // If this is of type string, the contents are null-terminated strings.
-  if (this->Header.sh_flags & SHF_STRINGS) {
-    for (unsigned I = 0, N = Offsets.size(); I != N; ++I) {
-      auto &P = Offsets[I];
-      if (P.second == MergeInputSection<ELFT>::PieceDead)
-        continue;
-
-      uintX_t Start = P.first;
-      uintX_t End = (I == N - 1) ? Data.size() : Offsets[I + 1].first;
-      StringRef Entry = Data.substr(Start, End - Start);
-      uintX_t OutputOffset = Builder.add(Entry);
-      if (shouldTailMerge())
-        OutputOffset = MergeInputSection<ELFT>::PieceLive;
-      P.second = OutputOffset;
-    }
-    return;
-  }
-
-  // If this is not of type string, every entry has the same size.
-  for (auto &P : Offsets) {
-    if (P.second == (uintX_t)-1)
-      continue;
-    StringRef Entry = Data.substr(P.first, EntSize);
-    P.second = Builder.add(Entry);
-  }
+template <class ELFT> void MergeOutputSection<ELFT>::prepare() {
+  for (MergeInputSection<ELFT> *S : InputSections)
+    S->prepareRanges(Builder, shouldTailMerge());
+  this->Header.sh_entsize = InputSections[0]->getSectionHdr()->sh_entsize;
 }
 
 template <class ELFT>
Index: ELF/Writer.cpp
===================================================================
--- ELF/Writer.cpp
+++ ELF/Writer.cpp
@@ -855,9 +855,7 @@
     if (!D->Section->Live)
       return false;
     if (auto *S = dyn_cast<MergeInputSection<ELFT>>(D->Section))
-      if (S->getRangeAndSize(D->Value).first->second ==
-          MergeInputSection<ELFT>::PieceDead)
-        return false;
+      return S->isRangeLive(D->Value);
   }
   return true;
 }
@@ -1309,6 +1307,7 @@
 
   // Create output sections for input object file sections.
   std::vector<OutputSectionBase<ELFT> *> RegularSections;
+  std::vector<MergeOutputSection<ELFT> *> MergeOutputSections;
   OutputSectionFactory<ELFT> Factory;
   for (const std::unique_ptr<elf::ObjectFile<ELFT>> &F :
        Symtab.getObjectFiles()) {
@@ -1324,11 +1323,17 @@
         OwningSections.emplace_back(Sec);
         OutputSections.push_back(Sec);
         RegularSections.push_back(Sec);
+        if (C->SectionKind == InputSectionBase<ELFT>::Merge)
+          MergeOutputSections.push_back(
+              static_cast<MergeOutputSection<ELFT> *>(Sec));
       }
       Sec->addSection(C);
     }
   }
 
+  for (MergeOutputSection<ELFT> *MS : MergeOutputSections)
+    MS->prepare();
+
   Out<ELFT>::Bss = static_cast<OutputSection<ELFT> *>(
       Factory.lookup(".bss", SHT_NOBITS, SHF_ALLOC | SHF_WRITE));