Index: ELF/InputSection.h
===================================================================
--- ELF/InputSection.h
+++ ELF/InputSection.h
@@ -123,12 +123,6 @@
 
   ArrayRef<uint8_t> getSectionData() const;
 
-  // Returns a section that Rel is pointing to. Used by the garbage collector.
-  std::pair<InputSectionBase<ELFT> *, uintX_t>
-  getRelocTarget(const Elf_Rel &Rel) const;
-  std::pair<InputSectionBase<ELFT> *, uintX_t>
-  getRelocTarget(const Elf_Rela &Rel) const;
-
   void relocate(uint8_t *Buf, uint8_t *BufEnd);
   std::vector<Relocation> Relocations;
 };
Index: ELF/InputSection.cpp
===================================================================
--- ELF/InputSection.cpp
+++ ELF/InputSection.cpp
@@ -78,43 +78,6 @@
 }
 
 template <class ELFT>
-static DefinedRegular<ELFT> *getRelocTargetSym(elf::ObjectFile<ELFT> *File,
-                                               const typename ELFT::Rel &Rel) {
-  uint32_t SymIndex = Rel.getSymbol(Config->Mips64EL);
-  SymbolBody &B = File->getSymbolBody(SymIndex).repl();
-  if (auto *D = dyn_cast<DefinedRegular<ELFT>>(&B))
-    if (D->Section)
-      return D;
-  return nullptr;
-}
-
-// Returns a section that Rel relocation is pointing to.
-template <class ELFT>
-std::pair<InputSectionBase<ELFT> *, typename ELFT::uint>
-InputSectionBase<ELFT>::getRelocTarget(const Elf_Rel &Rel) const {
-  auto *D = getRelocTargetSym(File, Rel);
-  if (!D)
-    return std::make_pair(nullptr, 0);
-  if (!D->isSection())
-    return std::make_pair(D->Section->Repl, D->Value);
-  const uint8_t *BufLoc = getSectionData().begin() + Rel.r_offset;
-  uintX_t Addend =
-      Target->getImplicitAddend(BufLoc, Rel.getType(Config->Mips64EL));
-  return std::make_pair(D->Section->Repl, D->Value + Addend);
-}
-
-template <class ELFT>
-std::pair<InputSectionBase<ELFT> *, typename ELFT::uint>
-InputSectionBase<ELFT>::getRelocTarget(const Elf_Rela &Rel) const {
-  auto *D = getRelocTargetSym(File, Rel);
-  if (!D)
-    return std::make_pair(nullptr, 0);
-  if (!D->isSection())
-    return std::make_pair(D->Section->Repl, D->Value);
-  return std::make_pair(D->Section->Repl, D->Value + Rel.r_addend);
-}
-
-template <class ELFT>
 InputSection<ELFT>::InputSection(elf::ObjectFile<ELFT> *F,
                                  const Elf_Shdr *Header)
     : InputSectionBase<ELFT>(F, Header, Base::Regular) {}
Index: ELF/MarkLive.cpp
===================================================================
--- ELF/MarkLive.cpp
+++ ELF/MarkLive.cpp
@@ -25,6 +25,7 @@
 #include "OutputSections.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
+#include "Target.h"
 #include "Writer.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Object/ELF.h"
@@ -38,31 +39,57 @@
 using namespace lld;
 using namespace lld::elf;
 
+// A resolved relocation. The Sec and Offset fields are set if the relocation
+// was resolved to an offset within a section. Otherwise the Sym field is set.
+template <class ELFT>
+struct ResolvedReloc {
+  SymbolBody *Sym;
+  InputSectionBase<ELFT> *Sec;
+  typename ELFT::uint Offset;
+};
+
+template <class ELFT>
+static typename ELFT::uint getAddend(InputSectionBase<ELFT> *Sec,
+                                     const typename ELFT::Rel &Rel) {
+  return Target->getImplicitAddend(Sec->getSectionData().begin(),
+                                   Rel.getType(Config->Mips64EL));
+}
+
+template <class ELFT>
+static typename ELFT::uint getAddend(InputSectionBase<ELFT> *Sec,
+                                     const typename ELFT::Rela &Rel) {
+  return Rel.r_addend;
+}
+
+template <class ELFT, class RelT>
+static ResolvedReloc<ELFT> resolveReloc(InputSection<ELFT> *Sec, RelT &Rel) {
+  uint32_t SymIndex = Rel.getSymbol(Config->Mips64EL);
+  SymbolBody &B = Sec->getFile()->getSymbolBody(SymIndex).repl();
+  auto *D = dyn_cast<DefinedRegular<ELFT>>(&B);
+  if (!D || !D->Section)
+    return {&B, nullptr, 0};
+  typename ELFT::uint Offset = D->Value;
+  if (D->isSection())
+    Offset += getAddend(Sec, Rel);
+  return {nullptr, D->Section->Repl, Offset};
+}
+
 // Calls Fn for each section that Sec refers to via relocations.
 template <class ELFT>
-static void forEachSuccessor(
-    InputSection<ELFT> *Sec,
-    std::function<void(InputSectionBase<ELFT> *, typename ELFT::uint Offset)>
-        Fn) {
+static void forEachSuccessor(InputSection<ELFT> *Sec,
+                             std::function<void(ResolvedReloc<ELFT>)> Fn) {
   typedef typename ELFT::Rel Elf_Rel;
   typedef typename ELFT::Rela Elf_Rela;
   typedef typename ELFT::Shdr Elf_Shdr;
-  typedef typename ELFT::uint uintX_t;
 
   ELFFile<ELFT> &Obj = Sec->getFile()->getObj();
   for (const Elf_Shdr *RelSec : Sec->RelocSections) {
     if (RelSec->sh_type == SHT_RELA) {
-      for (const Elf_Rela &RI : Obj.relas(RelSec)) {
-        std::pair<InputSectionBase<ELFT> *, uintX_t> P =
-            Sec->getRelocTarget(RI);
-        Fn(P.first, P.second);
-      }
+      for (const Elf_Rela &RI : Obj.relas(RelSec))
+        Fn(resolveReloc(Sec, RI));
     } else {
-      for (const Elf_Rel &RI : Obj.rels(RelSec)) {
-        std::pair<InputSectionBase<ELFT> *, uintX_t> P =
-            Sec->getRelocTarget(RI);
-        Fn(P.first, P.second);
-      }
+      for (const Elf_Rel &RI : Obj.rels(RelSec))
+        Fn(resolveReloc(Sec, RI));
     }
   }
 }
@@ -97,25 +124,30 @@
   typedef typename ELFT::uint uintX_t;
   SmallVector<InputSection<ELFT> *, 256> Q;
 
-  auto Enqueue = [&](InputSectionBase<ELFT> *Sec, uintX_t Offset) {
-    if (!Sec)
+  auto Enqueue = [&](ResolvedReloc<ELFT> R) {
+    if (R.Sym) {
+      if (R.Sym->isShared())
+        R.Sym->Backref->IsUsedInRegularObj = true;
       return;
-    if (auto *MS = dyn_cast<MergeInputSection<ELFT>>(Sec)) {
+    }
+    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(Offset);
+          MS->getRangeAndSize(R.Offset);
       T.first->second = 0;
     }
-    if (Sec->Live)
+    if (R.Sec->Live)
       return;
-    Sec->Live = true;
-    if (InputSection<ELFT> *S = dyn_cast<InputSection<ELFT>>(Sec))
+    R.Sec->Live = true;
+    if (InputSection<ELFT> *S = dyn_cast<InputSection<ELFT>>(R.Sec))
       Q.push_back(S);
   };
 
   auto MarkSymbol = [&](SymbolBody *Sym) {
     if (Sym)
       if (auto *D = dyn_cast<DefinedRegular<ELFT>>(Sym))
-        Enqueue(D->Section, D->Value);
+        Enqueue({nullptr, D->Section, D->Value});
   };
 
   // Add GC root symbols.
@@ -126,12 +158,15 @@
   for (StringRef S : Config->Undefined)
     MarkSymbol(Symtab->find(S));
 
-  // Preserve externally-visible symbols if the symbols defined by this
+  // Clear IsUsedInRegularObj bit on shared symbols; we use it as a live marker.
+  // Also preserve externally-visible symbols if the symbols defined by this
   // file can interrupt other ELF file's symbols at runtime.
-  if (Config->Shared || Config->ExportDynamic)
-    for (const Symbol *S : Symtab->getSymbols())
-      if (S->includeInDynsym())
-        MarkSymbol(S->Body);
+  for (Symbol *S : Symtab->getSymbols()) {
+    if (S->Body->isShared())
+      S->IsUsedInRegularObj = false;
+    else if (S->includeInDynsym())
+      MarkSymbol(S->Body);
+  }
 
   // Preserve special sections and those which are specified in linker
   // script KEEP command.
@@ -139,7 +174,7 @@
     for (InputSectionBase<ELFT> *Sec : F->getSections())
       if (Sec && Sec != &InputSection<ELFT>::Discarded)
         if (isReserved(Sec) || Script<ELFT>::X->shouldKeep(Sec))
-          Enqueue(Sec, 0);
+          Enqueue({nullptr, Sec, 0});
 
   // Mark all reachable sections.
   while (!Q.empty())
Index: ELF/OutputSections.cpp
===================================================================
--- ELF/OutputSections.cpp
+++ ELF/OutputSections.cpp
@@ -1132,15 +1132,20 @@
     } else {
       if (!HasReloc)
         fatal("FDE doesn't reference another section");
-      InputSectionBase<ELFT> *Target = S->getRelocTarget(*RelI).first;
-      if (Target && Target->Live) {
-        uint32_t CieOffset = Offset + 4 - ID;
-        auto I = OffsetToIndex.find(CieOffset);
-        if (I == OffsetToIndex.end())
-          fatal("invalid CIE reference");
-        Cies[I->second].Fdes.push_back(EHRegion<ELFT>(S, Index));
-        Out<ELFT>::EhFrameHdr->reserveFde();
-        this->Header.sh_size += alignTo(Length, sizeof(uintX_t));
+      uint32_t SymIndex = RelI->getSymbol(Config->Mips64EL);
+      SymbolBody &B = S->getFile()->getSymbolBody(SymIndex).repl();
+      auto *D = dyn_cast<DefinedRegular<ELFT>>(&B);
+      if (D && D->Section) {
+        InputSectionBase<ELFT> *Target = D->Section->Repl;
+        if (Target && Target->Live) {
+          uint32_t CieOffset = Offset + 4 - ID;
+          auto I = OffsetToIndex.find(CieOffset);
+          if (I == OffsetToIndex.end())
+            fatal("invalid CIE reference");
+          Cies[I->second].Fdes.push_back(EHRegion<ELFT>(S, Index));
+          Out<ELFT>::EhFrameHdr->reserveFde();
+          this->Header.sh_size += alignTo(Length, sizeof(uintX_t));
+        }
       }
     }
 
Index: test/ELF/gc-sections-shared.s
===================================================================
--- /dev/null
+++ test/ELF/gc-sections-shared.s
@@ -0,0 +1,28 @@
+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/shared.s -o %t2.o
+# RUN: ld.lld -shared %t2.o -o %t2.so
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
+# RUN: ld.lld --gc-sections --export-dynamic-symbol foo -o %t %t.o %t2.so
+# RUN: llvm-nm -D %t | FileCheck %s
+
+# CHECK: T bar
+# CHECK-NOT: bar2
+# CHECK: T foo
+
+.section .text.foo, "ax"
+.globl foo
+foo:
+call bar
+
+.section .text.bar, "ax"
+.globl bar
+bar:
+ret
+
+.section .text._start, "ax"
+.globl _start
+_start:
+ret
+
+.section .text.unused, "ax"
+call bar2