From 6715d6ec2eeaebd160bdc598c52ffa95c51a82ac Mon Sep 17 00:00:00 2001
From: David Blaikie <dblaikie@gmail.com>
Date: Fri, 25 Apr 2014 00:48:01 +0000
Subject: [PATCH] Fix quadratic performance during debug compression due to
 sections x symbols iteration.

When fixing the symbols in each compressed section we were iterating
over all symbols for each compressed section. In extreme cases this
could snowball severely (5min uncompressed -> 35min compressed) due to
iterating over all symbols for each compressed section (large numbers of
compressed sections can be generated by DWARF type units).

To address this, build a map of the symbols in each section ahead of
time, and access that map if a section is being compressed. This brings
compile time for the aforementioned example down to ~6 minutes.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207167 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/MC/ELFObjectWriter.cpp | 33 +++++++++++++++++++++------------
 1 file changed, 21 insertions(+), 12 deletions(-)

diff --git a/lib/MC/ELFObjectWriter.cpp b/lib/MC/ELFObjectWriter.cpp
index 06f295c249e..e8b34d56f5b 100644
--- a/lib/MC/ELFObjectWriter.cpp
+++ b/lib/MC/ELFObjectWriter.cpp
@@ -1250,20 +1250,21 @@ getCompressedFragment(MCAsmLayout &Layout,
   return CompressedFragment;
 }
 
-static void UpdateSymbols(const MCAsmLayout &Layout, const MCSectionData &SD,
-                          MCAssembler::symbol_range Symbols,
-                          MCFragment *NewFragment) {
-  for (MCSymbolData &Data : Symbols) {
-    MCFragment *F = Data.getFragment();
-    if (F && F->getParent() == &SD) {
-      Data.setOffset(Data.getOffset() +
-                     Layout.getFragmentOffset(Data.Fragment));
-      Data.setFragment(NewFragment);
-    }
+typedef DenseMap<const MCSectionData *, std::vector<MCSymbolData *>>
+DefiningSymbolMap;
+
+static void UpdateSymbols(const MCAsmLayout &Layout,
+                          const std::vector<MCSymbolData *> &Symbols,
+                          MCFragment &NewFragment) {
+  for (MCSymbolData *Sym : Symbols) {
+    Sym->setOffset(Sym->getOffset() +
+                   Layout.getFragmentOffset(Sym->getFragment()));
+    Sym->setFragment(&NewFragment);
   }
 }
 
 static void CompressDebugSection(MCAssembler &Asm, MCAsmLayout &Layout,
+                                 const DefiningSymbolMap &DefiningSymbols,
                                  const MCSectionELF &Section,
                                  MCSectionData &SD) {
   StringRef SectionName = Section.getSectionName();
@@ -1278,7 +1279,9 @@ static void CompressDebugSection(MCAssembler &Asm, MCAsmLayout &Layout,
 
   // Update the fragment+offsets of any symbols referring to fragments in this
   // section to refer to the new fragment.
-  UpdateSymbols(Layout, SD, Asm.symbols(), CompressedFragment.get());
+  auto I = DefiningSymbols.find(&SD);
+  if (I != DefiningSymbols.end())
+    UpdateSymbols(Layout, I->second, *CompressedFragment);
 
   // Invalidate the layout for the whole section since it will have new and
   // different fragments now.
@@ -1300,6 +1303,12 @@ void ELFObjectWriter::CompressDebugSections(MCAssembler &Asm,
   if (!Asm.getContext().getAsmInfo()->compressDebugSections())
     return;
 
+  DefiningSymbolMap DefiningSymbols;
+
+  for (MCSymbolData &SD : Asm.symbols())
+    if (MCFragment *F = SD.getFragment())
+      DefiningSymbols[F->getParent()].push_back(&SD);
+
   for (MCSectionData &SD : Asm) {
     const MCSectionELF &Section =
         static_cast<const MCSectionELF &>(SD.getSection());
@@ -1311,7 +1320,7 @@ void ELFObjectWriter::CompressDebugSections(MCAssembler &Asm,
     if (!SectionName.startswith(".debug_") || SectionName == ".debug_frame")
       continue;
 
-    CompressDebugSection(Asm, Layout, Section, SD);
+    CompressDebugSection(Asm, Layout, DefiningSymbols, Section, SD);
   }
 }
 
-- 
2.34.1