Do not start over relocation search from beginning.

This patch addresses a post-commit review for r270325. r270325
introduced getReloc function that searches a relocation for a
given range. It always started searching from beginning of relocation
vector, so it was slower than before. Previously, we used to use
the fact that the relocations are sorted. This patch restore it.

llvm-svn: 270572

2 files changed, 18 insertions, 11 deletions

diff --git a/lld/ELF/OutputSections.cpp b/lld/ELF/OutputSections.cpp
index 743ca0dd8b5..dd2f8f69ccb 100644
--- a/lld/ELF/OutputSections.cpp
+++ b/lld/ELF/OutputSections.cpp
@@ -920,14 +920,21 @@ void EhOutputSection<ELFT>::forEachInputSection(
 // Returns the first relocation that points to a region
 // between Begin and Begin+Size.
 template <class IntTy, class RelTy>
-static const RelTy *getReloc(IntTy Begin, IntTy Size, ArrayRef<RelTy> Rels) {
-  size_t I = 0;
-  size_t E = Rels.size();
-  while (I != E && Rels[I].r_offset < Begin)
-    ++I;
-  if (I == E || Begin + Size <= Rels[I].r_offset)
+static const RelTy *getReloc(IntTy Begin, IntTy Size, ArrayRef<RelTy> &Rels) {
+  for (auto I = Rels.begin(), E = Rels.end(); I != E; ++I) {
+    if (I->r_offset < Begin)
+      continue;
+
+    // Truncate Rels for fast access. That means we expect that the
+    // relocations are sorted and we are looking up symbols in
+    // sequential order. It is naturally satisfied for .eh_frame.
+    Rels = Rels.slice(I - Rels.begin());
+    if (I->r_offset < Begin + Size)
+      return I;
     return nullptr;
-  return &Rels[I];
+  }
+  Rels = ArrayRef<RelTy>();
+  return nullptr;
 }
 
 // Search for an existing CIE record or create a new one.
@@ -937,7 +944,7 @@ template <class ELFT>
 template <class RelTy>
 CieRecord *EhOutputSection<ELFT>::addCie(SectionPiece &Piece,
                                          EhInputSection<ELFT> *Sec,
-                                         ArrayRef<RelTy> Rels) {
+                                         ArrayRef<RelTy> &Rels) {
   const endianness E = ELFT::TargetEndianness;
   if (read32<E>(Piece.Data.data() + 4) != 0)
     fatal("CIE expected at beginning of .eh_frame: " + Sec->getSectionName());
@@ -971,7 +978,7 @@ template <class ELFT>
 template <class RelTy>
 bool EhOutputSection<ELFT>::isFdeLive(SectionPiece &Piece,
                                       EhInputSection<ELFT> *Sec,
-                                      ArrayRef<RelTy> Rels) {
+                                      ArrayRef<RelTy> &Rels) {
   const RelTy *Rel = getReloc(Piece.InputOff, Piece.size(), Rels);
   if (!Rel)
     fatal("FDE doesn't reference another section");
diff --git a/lld/ELF/OutputSections.h b/lld/ELF/OutputSections.h
index d14867c77e5..33efe40d59f 100644
--- a/lld/ELF/OutputSections.h
+++ b/lld/ELF/OutputSections.h
@@ -357,11 +357,11 @@ private:
 
   template <class RelTy>
   CieRecord *addCie(SectionPiece &Piece, EhInputSection<ELFT> *Sec,
-                    ArrayRef<RelTy> Rels);
+                    ArrayRef<RelTy> &Rels);
 
   template <class RelTy>
   bool isFdeLive(SectionPiece &Piece, EhInputSection<ELFT> *Sec,
-                 ArrayRef<RelTy> Rels);
+                 ArrayRef<RelTy> &Rels);
 
   uintX_t getFdePc(uint8_t *Buf, size_t Off, uint8_t Enc);