Index: ELF/GdbIndex.h
===================================================================
--- ELF/GdbIndex.h
+++ ELF/GdbIndex.h
@@ -23,6 +23,15 @@
   InputSectionBase *Sec = nullptr;
 };
 
+struct RelocCache {
+  const void *FirstReloc;
+  uint64_t NumRelocs;
+  uint64_t NumProccessedRelocs;
+  llvm::DenseMap<uint64_t, uint64_t> OffsetToIndex;
+
+  template <class RelTy> uint64_t getIndex(uint64_t Offset);
+};
+
 template <class ELFT> class LLDDwarfObj final : public llvm::DWARFObject {
   ObjFile<ELFT> *Obj;
   LLDDWARFSection InfoSection;
@@ -31,11 +40,11 @@
   StringRef AbbrevSection;
   StringRef GnuPubNamesSection;
   StringRef GnuPubTypesSection;
+  llvm::DenseMap<const InputSectionBase *, RelocCache> RelocationsCache;
 
   template <class RelTy>
-  llvm::Optional<llvm::RelocAddrEntry> findAux(const InputSectionBase &Sec,
-                                               uint64_t Pos,
-                                               ArrayRef<RelTy> Rels) const;
+  llvm::Optional<llvm::RelocAddrEntry>
+  findAux(const InputSectionBase &Sec, uint64_t Pos, ArrayRef<RelTy> Rels);
 
 public:
   explicit LLDDwarfObj(ObjFile<ELFT> *Obj);
Index: ELF/GdbIndex.cpp
===================================================================
--- ELF/GdbIndex.cpp
+++ ELF/GdbIndex.cpp
@@ -71,19 +71,48 @@
   }
 }
 
+template <class RelTy> uint64_t RelocCache::getIndex(uint64_t Offset) {
+  auto It = OffsetToIndex.find(Offset);
+  if (It != OffsetToIndex.end())
+    return It->second;
+
+  ArrayRef<RelTy> V(static_cast<const RelTy *>(FirstReloc), NumRelocs);
+  V = V.drop_front(NumProccessedRelocs);
+
+  while (!V.empty()) {
+    const RelTy &Rel = V.front();
+    V = V.drop_front();
+    uint64_t Index = NumProccessedRelocs++;
+
+    OffsetToIndex[Rel.r_offset] = Index;
+    if (Rel.r_offset == Offset)
+      return Index;
+  }
+
+  return (uint64_t)-1;
+}
+
 // Find if there is a relocation at Pos in Sec.  The code is a bit
 // more complicated than usual because we need to pass a section index
 // to llvm since it has no idea about InputSection.
 template <class ELFT>
 template <class RelTy>
-Optional<RelocAddrEntry>
-LLDDwarfObj<ELFT>::findAux(const InputSectionBase &Sec, uint64_t Pos,
-                           ArrayRef<RelTy> Rels) const {
-  auto I = llvm::find_if(Rels,
-                         [=](const RelTy &Rel) { return Rel.r_offset == Pos; });
-  if (I == Rels.end())
-    return None;
-  const RelTy &Rel = *I;
+Optional<RelocAddrEntry> LLDDwarfObj<ELFT>::findAux(const InputSectionBase &Sec,
+                                                    uint64_t Pos,
+                                                    ArrayRef<RelTy> Rels) {
+  auto P = RelocationsCache.insert({&Sec, {}});
+  RelocCache &Cache = P.first->second;
+  if (P.second) {
+    Cache.FirstReloc = Rels.data();
+    Cache.NumRelocs = Rels.size();
+    Cache.NumProccessedRelocs = 0;
+  }
+
+  uint64_t Index = Cache.getIndex<RelTy>(Pos);
+  if (Index == (uint64_t)-1)
+      return None;
+
+  const RelTy &Rel = Rels[Index];
   const ObjFile<ELFT> *File = Sec.getFile<ELFT>();
   uint32_t SymIndex = Rel.getSymbol(Config->IsMips64EL);
   const typename ELFT::Sym &Sym = File->getELFSymbols()[SymIndex];
@@ -106,8 +135,10 @@
                                                  uint64_t Pos) const {
   auto &Sec = static_cast<const LLDDWARFSection &>(S);
   if (Sec.Sec->AreRelocsRela)
-    return findAux(*Sec.Sec, Pos, Sec.Sec->template relas<ELFT>());
-  return findAux(*Sec.Sec, Pos, Sec.Sec->template rels<ELFT>());
+    return const_cast<LLDDwarfObj<ELFT> *>(this)->findAux(
+        *Sec.Sec, Pos, Sec.Sec->template relas<ELFT>());
+  return const_cast<LLDDwarfObj<ELFT> *>(this)->findAux(
+      *Sec.Sec, Pos, Sec.Sec->template rels<ELFT>());
 }
 
 template class elf::LLDDwarfObj<ELF32LE>;