[LLD][ELF] Fix performance of MarkLive::scanEhFrameSection

[andrewng]

Summary

MarkLive::scanEhFrameSection is used to retain personality/LSDA
functions when --gc-sections is enabled.

Improve its performance by only iterating over the .eh_frame relocations
that need to be resolved for an EhSectionPiece. This optimization makes
the same assumption as elsewhere in LLD that the .eh_frame relocations
are sorted by r_offset.

This appears to be a performance regression introduced in commit
e6c24299d237 (https://reviews.llvm.org/D59800).

This change has been seen to reduce link time by up to ~50%.

[MaskRay]

Thanks for noting this issue! Were you profiling ld.lld?

Here we are making a little assumption that a FDE's relocations are contiguous. The same assumption is made by InputSections getReloc (called by EhInputSection::split), so I think it is fine.
(A more robust approach is to sort relocations by r_offset, but it is cumbersome/slow to do that here as rels are raw Elf*_Rel[a] records.)

Worth mentioning that this function is used to retain personality/LSDA functions.

lld/ELF/MarkLive.cpp

156

parentheses beside && are not needed

[andrewng]

Address review comments.

[andrewng]

In D87245#2259958, @MaskRay wrote:

Thanks for noting this issue! Were you profiling ld.lld?

We have a game link that was taking an unusually long time to link with our downstream linker when --gc-sections was enabled. So I ran this link through the profiler and it identified this function as the primary hot spot which led me to find this issue.

[MaskRay]

Looks great!

lld/ELF/MarkLive.cpp

if (read32<ELFT::TargetEndianness>(piece.data().data() + 4) == 0) {
       resolveReloc(eh, rels[firstRelI], false);
       continue;
     }
 
     // This is a FDE. The relocations point to the described function or to
     // a LSDA. We only need to keep the LSDA alive, so ignore anything that
     // points to executable sections.
     uint64_t pieceEnd = piece.inputOff + piece.size;
-    for (size_t j = firstRelI, end2 = rels.size(); j < end2; ++j)
-      if (rels[j].r_offset < pieceEnd)
-        resolveReloc(eh, rels[j], true);
+    for (size_t j = firstRelI, end2 = rels.size();
+         j < end2 && rels[j].r_offset < pieceEnd; ++j)
   }
 }
 
 // Some sections are used directly by the loader, so they should never be
 // garbage-collected. This function returns true if a given section is such
 // section.
 static bool isReserved(InputSectionBase *sec) {
   switch (sec->type) {