Index: test/tools/llvm-objcopy/ELF/compress-debug-sections-relocations.test
===================================================================
--- /dev/null
+++ test/tools/llvm-objcopy/ELF/compress-debug-sections-relocations.test
@@ -0,0 +1,93 @@
+# REQUIRES: zlib
+
+# RUN: yaml2obj %s -o %t1.o
+# RUN: llvm-objcopy --compress-debug-sections %t1.o %t2.o
+# RUN: llvm-readobj -r -s %t2.o | FileCheck %s
+
+## Check that all of the debug sections were compressed and
+## we were able to produce an output with the relocations
+## pointed to correct compressed debug sections.
+
+# CHECK:      Name: .debug_str
+# CHECK-NEXT: Type: SHT_PROGBITS
+# CHECK-NEXT: Flags [
+# CHECK-NEXT:   SHF_COMPRESSED
+# CHECK-NEXT:   SHF_MERGE
+# CHECK-NEXT:   SHF_STRINGS
+# CHECK-NEXT: ]
+# CHECK:      Name: .debug_abbrev
+# CHECK-NEXT: Type: SHT_PROGBITS
+# CHECK-NEXT: Flags [
+# CHECK-NEXT:   SHF_COMPRESSED
+# CHECK-NEXT: ]
+# CHECK:      Name: .debug_info
+# CHECK-NEXT: Type: SHT_PROGBITS
+# CHECK-NEXT: Flags [
+# CHECK-NEXT:   SHF_COMPRESSED
+# CHECK-NEXT: ]
+# CHECK:      Name: .debug_line
+# CHECK-NEXT: Type: SHT_PROGBITS
+# CHECK-NEXT: Flags [
+# CHECK-NEXT:   SHF_COMPRESSED
+# CHECK-NEXT: ]
+
+# CHECK:      Relocations [
+# CHECK-NEXT:   Section {{.*}} .rela.debug_info {
+# CHECK-NEXT:     0x1 R_X86_64_32 .debug_abbrev 0x0
+# CHECK-NEXT:     0x2 R_X86_64_32 .debug_str 0x0
+# CHECK-NEXT:     0x3 R_X86_64_32 .debug_line 0x0
+# CHECK-NEXT:   }
+# CHECK-NEXT: ]
+
+--- !ELF
+FileHeader:      
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  Type:            ET_REL
+  Machine:         EM_X86_64
+Sections:        
+  - Name:            .debug_str
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_MERGE, SHF_STRINGS ]
+    AddressAlign:    0x0000000000000001
+    EntSize:         0x0000000000000001
+    Content:         "0000"
+  - Name:            .debug_abbrev
+    Type:            SHT_PROGBITS
+    AddressAlign:    0x0000000000000001
+    Content:         "0000"
+  - Name:            .debug_info
+    Type:            SHT_PROGBITS
+    AddressAlign:    0x0000000000000001
+    Content:         "0000"
+  - Name:            .rela.debug_info
+    Type:            SHT_RELA
+    Link:            .symtab
+    AddressAlign:    0x0000000000000008
+    EntSize:         0x0000000000000018
+    Info:            .debug_info
+    Relocations:     
+      - Offset:          0x0000000000000001
+        Symbol:          .debug_abbrev
+        Type:            R_X86_64_32
+      - Offset:          0x0000000000000002
+        Symbol:          .debug_str
+        Type:            R_X86_64_32
+      - Offset:          0x0000000000000003
+        Symbol:          .debug_line
+        Type:            R_X86_64_32
+  - Name:            .debug_line
+    Type:            SHT_PROGBITS
+    AddressAlign:    0x0000000000000001
+    Content:         "0000"
+Symbols:
+  Local:
+    - Name:            .debug_str
+      Type:            STT_SECTION
+      Section:         .debug_str
+    - Name:            .debug_abbrev
+      Type:            STT_SECTION
+      Section:         .debug_abbrev
+    - Name:            .debug_line
+      Type:            STT_SECTION
+      Section:         .debug_line
Index: tools/llvm-objcopy/ELF/ELFObjcopy.cpp
===================================================================
--- tools/llvm-objcopy/ELF/ELFObjcopy.cpp
+++ tools/llvm-objcopy/ELF/ELFObjcopy.cpp
@@ -241,27 +241,24 @@
     const CopyConfig &Config, Object &Obj, SectionPred &RemovePred,
     function_ref<bool(const SectionBase &)> shouldReplace,
     function_ref<SectionBase *(const SectionBase *)> addSection) {
+  // Build a list of the debug sections we are going to replace.
+  // We can't call `addSection` while iterating over sections,
+  // because it would mutate the sections array.
   SmallVector<SectionBase *, 13> ToReplace;
-  SmallVector<RelocationSection *, 13> RelocationSections;
-  for (auto &Sec : Obj.sections()) {
-    if (RelocationSection *R = dyn_cast<RelocationSection>(&Sec)) {
-      if (shouldReplace(*R->getSection()))
-        RelocationSections.push_back(R);
-      continue;
-    }
-
+  for (auto &Sec : Obj.sections())
     if (shouldReplace(Sec))
       ToReplace.push_back(&Sec);
-  }
 
-  for (SectionBase *S : ToReplace) {
-    SectionBase *NewSection = addSection(S);
+  // Build a mapping from original section to a new one.
+  DenseMap<SectionBase *, SectionBase *> FromTo;
+  for (SectionBase *S : ToReplace)
+    FromTo[S] = addSection(S);
 
-    for (RelocationSection *RS : RelocationSections) {
-      if (RS->getSection() == S)
-        RS->setSection(NewSection);
-    }
-  }
+  // Now we want to update target sections of relocation sections.
+  // Also we will update the relocations itself.
+  for (auto &Sec : Obj.sections())
+    if (RelocationSection *RS = dyn_cast<RelocationSection>(&Sec))
+      RS->replaceSections(FromTo);
 
   RemovePred = [shouldReplace, RemovePred](const SectionBase &Sec) {
     return shouldReplace(Sec) || RemovePred(Sec);
Index: tools/llvm-objcopy/ELF/Object.h
===================================================================
--- tools/llvm-objcopy/ELF/Object.h
+++ tools/llvm-objcopy/ELF/Object.h
@@ -596,6 +596,7 @@
       function_ref<bool(const SectionBase *)> ToRemove) override;
   Error removeSymbols(function_ref<bool(const Symbol &)> ToRemove) override;
   void markSymbols() override;
+  void replaceSections(const DenseMap<SectionBase *, SectionBase *> &FromTo);
 
   static bool classof(const SectionBase *S) {
     if (S->Flags & ELF::SHF_ALLOC)
Index: tools/llvm-objcopy/ELF/Object.cpp
===================================================================
--- tools/llvm-objcopy/ELF/Object.cpp
+++ tools/llvm-objcopy/ELF/Object.cpp
@@ -646,6 +646,19 @@
     Reloc.RelocSymbol->Referenced = true;
 }
 
+void RelocationSection::replaceSections(
+    const DenseMap<SectionBase *, SectionBase *> &FromTo) {
+  // Update the target section if it was replaced.
+  if (SectionBase *To = FromTo.lookup(SecToApplyRel))
+    SecToApplyRel = To;
+
+  // Change the sections where symbols are defined in if their
+  // original sections were replaced.
+  for (const Relocation &R : Relocations)
+    if (SectionBase *To = FromTo.lookup(R.RelocSymbol->DefinedIn))
+      R.RelocSymbol->DefinedIn = To;
+}
+
 void SectionWriter::visit(const DynamicRelocationSection &Sec) {
   llvm::copy(Sec.Contents,
             Out.getBufferStart() + Sec.Offset);