Index: ELF/SyntheticSections.h
===================================================================
--- ELF/SyntheticSections.h
+++ ELF/SyntheticSections.h
@@ -420,6 +420,10 @@
   std::vector<SymbolTableEntry> Symbols;
 
   StringTableSection &StrTabSec;
+
+  llvm::once_flag InitSearchTableFlag;
+  llvm::DenseMap<SymbolBody *, size_t> SymbolToIndexMap;
+  llvm::DenseMap<OutputSection *, size_t> SectionToIndexMap;
 };
 
 template <class ELFT>
Index: ELF/SyntheticSections.cpp
===================================================================
--- ELF/SyntheticSections.cpp
+++ ELF/SyntheticSections.cpp
@@ -1354,18 +1354,30 @@
 }
 
 size_t SymbolTableBaseSection::getSymbolIndex(SymbolBody *Body) {
-  auto I = llvm::find_if(Symbols, [&](const SymbolTableEntry &E) {
-    if (E.Symbol == Body)
-      return true;
-    // This is used for -r, so we have to handle multiple section
-    // symbols being combined.
-    if (Body->Type == STT_SECTION && E.Symbol->Type == STT_SECTION)
-      return Body->getOutputSection() == E.Symbol->getOutputSection();
-    return false;
+  // Initialize symbol search table lazily. This is used only when -r or
+  // --emit-relocs is given and allows to find symbol table index without
+  // linear search what improves perfomance drastically in some cases.
+  llvm::call_once(InitSearchTableFlag, [&] {
+    SymbolToIndexMap.reserve(Symbols.size());
+    size_t I = 0;
+    for (const SymbolTableEntry &E : Symbols) {
+      if (E.Symbol->Type != STT_SECTION)
+        SymbolToIndexMap[E.Symbol] = ++I;
+      else
+        SectionToIndexMap[E.Symbol->getOutputSection()] = ++I;
+    }
   });
-  if (I == Symbols.end())
-    return 0;
-  return I - Symbols.begin() + 1;
+
+  // Handling STT_SECTION is special. We ignore section symbols when reading
+  // files and create a section symbol for each output section instead to merge
+  // them. That means we should distinguish STT_SECTION symbols by output
+  // sections they belongs to.
+  if (Body->Type == STT_SECTION) {
+    auto I = SectionToIndexMap.find(Body->getOutputSection());
+    return (I != SectionToIndexMap.end()) ? I->second : 0;
+  }
+  auto I = SymbolToIndexMap.find(Body);
+  return (I != SymbolToIndexMap.end()) ? I->second : 0;
 }
 
 template <class ELFT>