Index: lld/trunk/COFF/Chunks.h
===================================================================
--- lld/trunk/COFF/Chunks.h
+++ lld/trunk/COFF/Chunks.h
@@ -10,8 +10,10 @@
 #ifndef LLD_COFF_CHUNKS_H
 #define LLD_COFF_CHUNKS_H
 
+#include "InputFiles.h"
 #include "lld/Core/LLVM.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Object/COFF.h"
 #include <map>
@@ -32,6 +34,7 @@
 class DefinedImportData;
 class ObjectFile;
 class OutputSection;
+class SymbolBody;
 
 // A Chunk represents a chunk of data that will occupy space in the
 // output (if the resolver chose that). It may or may not be backed by
@@ -106,6 +109,24 @@
 // A chunk corresponding a section of an input file.
 class SectionChunk : public Chunk {
 public:
+  class symbol_iterator : public llvm::iterator_adaptor_base<
+                              symbol_iterator, const coff_relocation *,
+                              std::random_access_iterator_tag, SymbolBody *> {
+    friend SectionChunk;
+
+    ObjectFile *File;
+
+    symbol_iterator(ObjectFile *File, const coff_relocation *I)
+        : symbol_iterator::iterator_adaptor_base(I), File(File) {}
+
+  public:
+    symbol_iterator() = default;
+
+    SymbolBody *operator*() const {
+      return File->getSymbolBody(I->SymbolTableIndex);
+    }
+  };
+
   SectionChunk(ObjectFile *File, const coff_section *Header);
   static bool classof(const Chunk *C) { return C->kind() == SectionKind; }
   size_t getSize() const override { return Header->SizeOfRawData; }
@@ -130,7 +151,19 @@
   // Used by the garbage collector.
   bool isRoot() { return Root; }
   bool isLive() { return Live; }
-  void markLive() { if (!Live) mark(); }
+  void markLive() {
+    assert(!Live && "Cannot mark an already live section!");
+    Live = true;
+  }
+
+  // Allow iteration over the bodies of this chunk's relocated symbols.
+  llvm::iterator_range<symbol_iterator> symbols() const {
+    return llvm::make_range(symbol_iterator(File, Relocs.begin()),
+                            symbol_iterator(File, Relocs.end()));
+  }
+
+  // Allow iteration over the associated child chunks for this section.
+  ArrayRef<SectionChunk *> children() const { return AssocChildren; }
 
   // Used for ICF (Identical COMDAT Folding)
   void replaceWith(SectionChunk *Other);
@@ -156,7 +189,6 @@
   size_t NumRelocs;
 
   // Used by the garbage collector.
-  void mark();
   bool Live = false;
   bool Root;
 
Index: lld/trunk/COFF/Chunks.cpp
===================================================================
--- lld/trunk/COFF/Chunks.cpp
+++ lld/trunk/COFF/Chunks.cpp
@@ -80,23 +80,6 @@
   }
 }
 
-void SectionChunk::mark() {
-  assert(!Live);
-  Live = true;
-
-  // Mark all symbols listed in the relocation table for this section.
-  for (const coff_relocation &Rel : Relocs) {
-    SymbolBody *B = File->getSymbolBody(Rel.SymbolTableIndex)->getReplacement();
-    if (auto *D = dyn_cast<DefinedRegular>(B))
-      D->markLive();
-  }
-
-  // Mark associative sections if any.
-  for (Chunk *C : AssocChildren)
-    if (auto *SC = dyn_cast<SectionChunk>(C))
-      SC->markLive();
-}
-
 void SectionChunk::addAssociative(SectionChunk *Child) {
   AssocChildren.push_back(Child);
   // Associative sections are live if their parent COMDATs are live,
Index: lld/trunk/COFF/Symbols.h
===================================================================
--- lld/trunk/COFF/Symbols.h
+++ lld/trunk/COFF/Symbols.h
@@ -136,7 +136,7 @@
   bool isCOMDAT() { return IsCOMDAT; }
   bool isLive() const { return (*Data)->isLive(); }
   void markLive() { (*Data)->markLive(); }
-  Chunk *getChunk() { return *Data; }
+  SectionChunk *getChunk() { return *Data; }
   uint64_t getValue() { return Sym.getValue(); }
 
 private:
Index: lld/trunk/COFF/Writer.cpp
===================================================================
--- lld/trunk/COFF/Writer.cpp
+++ lld/trunk/COFF/Writer.cpp
@@ -111,13 +111,44 @@
 void Writer::markLive() {
   if (!Config->DoGC)
     return;
+
+  // We build up a worklist of sections which have been marked as live. We only
+  // push into the worklist when we discover an unmarked section, and we mark
+  // as we push, so sections never appear twice in the list.
+  SmallVector<SectionChunk *, 256> Worklist;
+
   for (StringRef Name : Config->GCRoots)
     if (auto *D = dyn_cast<DefinedRegular>(Symtab->find(Name)))
-      D->markLive();
+      if (!D->isLive()) {
+        D->markLive();
+        Worklist.push_back(D->getChunk());
+      }
   for (Chunk *C : Symtab->getChunks())
     if (auto *SC = dyn_cast<SectionChunk>(C))
-      if (SC->isRoot())
+      if (SC->isRoot() && !SC->isLive()) {
         SC->markLive();
+        Worklist.push_back(SC);
+      }
+
+  while (!Worklist.empty()) {
+    SectionChunk *SC = Worklist.pop_back_val();
+    assert(SC->isLive() && "We mark as live when pushing onto the worklist!");
+
+    // Mark all symbols listed in the relocation table for this section.
+    for (SymbolBody *S : SC->symbols())
+      if (auto *D = dyn_cast<DefinedRegular>(S->getReplacement()))
+        if (!D->isLive()) {
+          D->markLive();
+          Worklist.push_back(D->getChunk());
+        }
+
+    // Mark associative sections if any.
+    for (SectionChunk *ChildSC : SC->children())
+      if (!ChildSC->isLive()) {
+        ChildSC->markLive();
+        Worklist.push_back(ChildSC);
+      }
+  }
 }
 
 // Merge identical COMDAT sections.