[ELF] Refactor uses of getInputSections to improve efficiency NFC

[andrewng]

Summary

Add new method getFirstInputSection and use instead of getInputSections
where appropriate to avoid creation of an unneeded vector of input
sections.

[andrewng]

Noticed this again whilst working on D72775. Appears to have a minor performance benefit of ~2% for the same two links with stack sizes mentioned in D72775.

[peter.smith]

Not got any objections to the refactoring, I'm not sure we need to share the loop traversal between getInputSections and getFirstInputSections (see comment inline) but I'm willing to go with the consensus on that.

lld/ELF/OutputSections.cpp

469

It would definitely be worth adding a comment, explaining that f must return true to continue and false to early terminate. I didn't find it obvious until reading the loop body and the two examples.

I thought about trying a different name (there is an identically named helper in Relocations.cpp that does something similar) but I couldn't come up with anything succinct. The best I could come up with was forEachInputSectionDescriptionUntilFalse().

478

Given that we only have 2 clients of forEachInputSectionDescription and no nested loops , it might be worth having two simpler functions that have their own loop

InputSection *getFirstInputSection(const OutputSection *os) {
  for (BaseCommand *base : os->sectionCommands)
    if (auto *isd = dyn_cast<InputSectionDescription>(base))
      if (!isd->sections.empty())
        return isd->sections.front();
  return nullptr;
}

getInputSections can remain the same as before.

[grimar]

lld/ELF/OutputSections.cpp

469

StringRef has take_while and take_until
It could be forEachInputSectionDescriptionDoWhile probably.
But see below.

478

I agree. No need to introduce forEachInputSectionDescription probably.

[andrewng]

Updated patch to address review comments.

[grimar]

LGTM

[peter.smith]

LGTM too. Thanks for the update.

lld/ELF/LinkerScript.cpp

for (BaseCommand *&cmd : sectionCommands) {
 
     // The input section might have been removed (if it was an empty synthetic
     // section), but we at least know the flags.
     if (sec->hasInputSections)
       flags = sec->flags;
 
     // We do not want to keep any special flags for output section
     // in case it is empty.
-    bool isEmpty = getInputSections(sec).empty();
+    bool isEmpty = (getFirstInputSection(sec) == nullptr);
     if (isEmpty)
       sec->flags = flags & ((sec->nonAlloc ? 0 : (uint64_t)SHF_ALLOC) |
                             SHF_WRITE | SHF_EXECINSTR);
 
     if (isEmpty && isDiscardable(*sec)) {
       sec->markDead();
       cmd = nullptr;
     }

lld/ELF/OutputSections.h

private:
   std::vector<uint8_t> zDebugHeader;
   llvm::SmallVector<char, 1> compressedData;
 
   std::array<uint8_t, 4> getFiller();
 };
 
 int getPriority(StringRef s);
 
-std::vector<InputSection *> getInputSections(OutputSection* os);
+InputSection *getFirstInputSection(const OutputSection *os);
+std::vector<InputSection *> getInputSections(const OutputSection *os);
 
 // All output sections that are handled by the linker specially are
 // globally accessible. Writer initializes them, so don't use them
 // until Writer is initialized.
 struct Out {
   static uint8_t *bufferStart;
   static uint8_t first;
   static PhdrEntry *tlsPhdr;

lld/ELF/OutputSections.cpp

static void finalizeShtGroup(OutputSection *os,
 
   // sh_info then contain index of an entry in symbol table section which
   // provides signature of the section group.
   ArrayRef<Symbol *> symbols = section->file->getSymbols();
   os->info = in.symTab->getSymbolIndex(symbols[section->info]);
 }
 
 void OutputSection::finalize() {
-  std::vector<InputSection *> v = getInputSections(this);
-  InputSection *first = v.empty() ? nullptr : v[0];
+  InputSection *first = getFirstInputSection(this);
 
   if (flags & SHF_LINK_ORDER) {
     // We must preserve the link order dependency of sections with the
     // SHF_LINK_ORDER flag. The dependency is indicated by the sh_link field. We
     // need to translate the InputSection sh_link to the OutputSection sh_link,
     // all InputSections in the OutputSection have the same dependency.
     if (auto *ex = dyn_cast<ARMExidxSyntheticSection>(first))
       link = ex->getLinkOrderDep()->getParent()->sectionIndex;
int getPriority(StringRef s) {
   if (pos == StringRef::npos)
     return 65536;
   int v;
   if (!to_integer(s.substr(pos + 1), v, 10))
     return 65536;
   return v;
 }
 
-std::vector<InputSection *> getInputSections(OutputSection *os) {
-  std::vector<InputSection *> ret;
+namespace {
+void forEachInputSectionDescription(
+    const OutputSection *os, function_ref<bool(InputSectionDescription *)> f) {
   for (BaseCommand *base : os->sectionCommands)
     if (auto *isd = dyn_cast<InputSectionDescription>(base))
-      ret.insert(ret.end(), isd->sections.begin(), isd->sections.end());
+      if (!f(isd))
+        break;
+}
+} // namespace
+
+InputSection *getFirstInputSection(const OutputSection *os) {
+  InputSection *ret = nullptr;
+  forEachInputSectionDescription(os, [&](InputSectionDescription *isd) {
+    if (isd->sections.empty())
+      return true;
+    ret = isd->sections[0];
+    return false;
+  });
+  return ret;
+}
+
+std::vector<InputSection *> getInputSections(const OutputSection *os) {
+  std::vector<InputSection *> ret;
+  forEachInputSectionDescription(os, [&](InputSectionDescription *isd) {
+    return true;
+  });
   return ret;
 }
 
 // Sorts input sections by section name suffixes, so that .foo.N comes
 // before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
 // We want to keep the original order if the priorities are the same
 // because the compiler keeps the original initialization order in a
 // translation unit and we need to respect that.