Index: ELF/InputSection.cpp
===================================================================
--- ELF/InputSection.cpp
+++ ELF/InputSection.cpp
@@ -378,17 +378,35 @@
   return Sections[this->Info];
 }
 
+static DenseMap<SymbolBody *, size_t> createSymbolToIndexMap() {
+  DenseMap<SymbolBody *, size_t> Ret(InX::SymTab->getSymbols().size());
+  uint64_t I = 0;
+  for (const SymbolTableEntry &S : InX::SymTab->getSymbols())
+    Ret.insert({S.Symbol, ++I});
+  return Ret;
+}
+
+static DenseMap<OutputSection *, size_t> createSectionToIndexMap() {
+  ArrayRef<SymbolTableEntry> V = InX::SymTab->getSymbols();
+  DenseMap<OutputSection *, size_t> Ret(V.size());
+  for (size_t I = 0, E = V.size(); I != E; ++I)
+    if (V[I].Symbol->Type == STT_SECTION)
+      Ret.insert({V[I].Symbol->getOutputSection(), I + 1});
+  return Ret;
+}
+
 // This is used for -r and --emit-relocs. We can't use memcpy to copy
 // relocations because we need to update symbol table offset and section index
 // for each relocation. So we copy relocations one by one.
 template <class ELFT, class RelTy>
 void InputSection::copyRelocations(uint8_t *Buf, ArrayRef<RelTy> Rels) {
+  // Next mappings used for optimization. We have to create separate mapping for
+  // section symbols, because want to handle case when multiple section symbols
+  // being combined and them are not in symbol table.
+  static DenseMap<SymbolBody *, size_t> SymbolToIndex = createSymbolToIndexMap();
+  static DenseMap<OutputSection *, size_t> SectionToIndex = createSectionToIndexMap();
   InputSectionBase *RelocatedSection = getRelocatedSection();
 
-  // Loop is slow and have complexity O(N*M), where N - amount of
-  // relocations and M - amount of symbols in symbol table.
-  // That happens because getSymbolIndex(...) call below performs
-  // simple linear search.
   for (const RelTy &Rel : Rels) {
     uint32_t Type = Rel.getType(Config->IsMips64EL);
     SymbolBody &Body = this->getFile<ELFT>()->getRelocTargetSym(Rel);
@@ -403,8 +421,11 @@
     // section, but for --emit-relocs it is an virtual address.
     P->r_offset = RelocatedSection->getOutputSection()->Addr +
                   RelocatedSection->getOffset(Rel.r_offset);
-    P->setSymbolAndType(InX::SymTab->getSymbolIndex(&Body), Type,
-                        Config->IsMips64EL);
+
+    size_t Sym = (Body.Type == STT_SECTION)
+                     ? SectionToIndex[Body.getOutputSection()]
+                     : SymbolToIndex[&Body];
+    P->setSymbolAndType(Sym, Type, Config->IsMips64EL);
 
     if (Body.Type == STT_SECTION) {
       // We combine multiple section symbols into only one per
Index: ELF/SyntheticSections.cpp
===================================================================
--- ELF/SyntheticSections.cpp
+++ ELF/SyntheticSections.cpp
@@ -1354,15 +1354,8 @@
 }
 
 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;
-  });
+  auto I = llvm::find_if(
+      Symbols, [&](const SymbolTableEntry &E) { return E.Symbol == Body; });
   if (I == Symbols.end())
     return 0;
   return I - Symbols.begin() + 1;