[LLD][ELF] Optimize linker script filename glob pattern matching NFC

[andrewng]

Summary

Optimize the filename glob pattern matching in
LinkerScript::computeInputSections() and LinkerScript::shouldKeep().

Add InputFile::getNameForScript() which gets and if required caches the
Inputfile's name used for linker script matching. This avoids the
overhead of name creation that was in getFilename() in LinkerScript.cpp.

Add InputSectionDescription::matchesFile() and
SectionPattern::excludesFile() which perform the glob pattern matching
for an InputFile and make use of a cache of the previous result. As both
computeInputSections() and shouldKeep() process sections in order and
the sections of the same InputFile are contiguous, these single entry
caches can significantly speed up performance for more complex glob
patterns.

These changes have been seen to reduce link time with --gc-sections by
up to ~40% with linker scripts that contain KEEP filename glob patterns
such as "*crtbegin*.o".

[andrewng]

This change requires D87468.

[MaskRay]

lld/ELF/LinkerScript.cpp

436

Is the string allocation the bottleneck?

[andrewng]

lld/ELF/LinkerScript.cpp

436

Yes, that is a small part of the overhead. For inputs from archives there's also the string concatenation.

The main overhead is the repeated glob pattern matching for the same input file, i.e. any input file that contains a large number of sections.

[grimar]

I think this is fine approach in general. I wonder if it should/could be splitted into 2 patches though:
one for InputSectionDescription and one for SectionPattern?

lld/ELF/LinkerScript.cpp

324

It feels that getFilename can instead be just inlined now, though?

332

You can just call emplace. (And below).

lld/ELF/LinkerScript.h

168

I'd add a comment.

185

Should we make InputSectionDescription to be class (because it has a member function now)
and make filePat private?

186

I'd add a comment here too probably.

[andrewng]

Update to address review comments and suggestions.

[andrewng]

In D87469#2267576, @grimar wrote:

I think this is fine approach in general. I wonder if it should/could be splitted into 2 patches though:
one for InputSectionDescription and one for SectionPattern?

I did consider this, but the changes for both are very similar, somewhat overlap and have the same justification, so that's why I've put them together. However, if the general consensus is that it should be split up, then I'm happy to do this.

lld/ELF/LinkerScript.cpp

324

I've inlined the function.

[grimar]

LGTM. Please wait for @MaskRay opinion.

lld/ELF/LinkerScript.cpp

324

I've meant it is a single line function and you can probably just remove it and inline its logic.
E.g:

if (!matchesFileCache || matchesFileCache->first != file)
  matchesFileCache.emplace(
      file, filePat.match(getFilename(file ? file->getNameForScript() : "")));

Up to you.

A bit unrelated to this diff: thinking more I wonder if we want to assume an empty file name at all for matching.
We perhaps can be more explicit. Something like:

bool InputSectionDescription::matchesFile(const InputFile *file) const {
  if (filePat.isTrivialMatchAll())
    return true;

  if (!file)
    return false;
...

bool SectionPattern::excludesFile(const InputFile *file) const {
  if (!file || excludedFilePat.empty())
    return false;
...

[MaskRay]

lld/ELF/InputFiles.cpp

282

Twine(':')

lld/ELF/LinkerScript.cpp

327–338

Delete the two lines.

lld/ELF/LinkerScript.h

153

... and the argument.

173

... and the argument.

[MaskRay]

lld/ELF/LinkerScript.cpp

324

getFilename is called twice. Having it separate looks good to me.

if (filePat.isTrivialMatchAll())

Avoiding the single-element cache with just (filePat.isTrivialMatchAll())? I think that will not speed up KEEP (*crtbegin.o(.ctors)) as in GNU ld's internal linker scripts. The idea is, in computeInputSections, when testing sections. The sections of the same file are contiguous. So a single-element cache can speed up.

The description should be modified to mention this point.

[MaskRay]

In D87469#2266164, @andrewng wrote:

This change requires D87468.

You can click Edit Related Revisions... to make this clearer in Phab.

[andrewng]

Update to address review comments.

[andrewng]

lld/ELF/LinkerScript.cpp

324

@grimar, the null InputFile for matchesFile() isn't quite so straightforward because isTrivialMatchAll() only currently identifies "*" and not "**" (or any other sequence of '*'). But yes, something like you suggest could be done as another change if desired.

@MaskRay, the isTrivialMatchAll() is there to catch the common case of the file glob pattern being "*". This was more important before I added getNameForScript() but it is still beneficial which is why I have left it in. I have updated the description regarding the speed up due to the caching of the glob pattern match.

[MaskRay]

LGTM.

lld/ELF/AArch64ErrataFix.h

 #include <map>
 #include <vector>
 
 namespace lld {
 namespace elf {
 
 class Defined;
 class InputSection;
-struct InputSectionDescription;
+class InputSectionDescription;
 class OutputSection;
 class Patch843419Section;
 
 class AArch64Err843419Patcher {
 public:
   // return true if Patches have been added to the OutputSections.
   bool createFixes();
 

lld/ELF/ARMErrataFix.h

 #include <map>
 #include <vector>
 
 namespace lld {
 namespace elf {
 
 class Defined;
 class InputSection;
-struct InputSectionDescription;
+class InputSectionDescription;
 class OutputSection;
 class Patch657417Section;
 
 class ARMErr657417Patcher {
 public:
   // Return true if Patches have been added to the OutputSections.
   bool createFixes();
 

lld/ELF/InputFiles.h

public:
   ArrayRef<Symbol *> getSymbols() { return getMutableSymbols(); }
 
   MutableArrayRef<Symbol *> getMutableSymbols() {
     assert(fileKind == BinaryKind || fileKind == ObjKind ||
            fileKind == BitcodeKind);
     return symbols;
   }
 
+  // Get filename to use for linker script processing.
+  StringRef getNameForScript() const;
+
   // Filename of .a which contained this file. If this file was
   // not in an archive file, it is the empty string. We use this
   // string for creating error messages.
   std::string archiveName;
 
   // If this is an architecture-specific file, the following members
   // have ELF type (i.e. ELF{32,64}{LE,BE}) and target machine type.
   ELFKind ekind = ELFNoneKind;
public:
   std::vector<Symbol *> symbols;
 
 protected:
   InputFile(Kind k, MemoryBufferRef m);
   std::vector<InputSectionBase *> sections;
 
 private:
   const Kind fileKind;
+
+  // Cache for getNameForScript().
+  mutable std::string nameForScriptCache;
 };
 
 class ELFFileBase : public InputFile {
 public:
   ELFFileBase(Kind k, MemoryBufferRef m);
   static bool classof(const InputFile *f) { return f->isElf(); }
 
   template <typename ELFT> llvm::object::ELFFile<ELFT> getObj() const {

lld/ELF/InputFiles.cpp

case ELF32BEKind:
     return getSrcMsgAux(cast<ObjFile<ELF32BE>>(*this), sym, sec, offset);
   case ELF64LEKind:
     return getSrcMsgAux(cast<ObjFile<ELF64LE>>(*this), sym, sec, offset);
   case ELF64BEKind:
     return getSrcMsgAux(cast<ObjFile<ELF64BE>>(*this), sym, sec, offset);
   }
 }
 
+StringRef InputFile::getNameForScript() const {
+  if (archiveName.empty())
+    return getName();
+
+  if (nameForScriptCache.empty())
+    nameForScriptCache = (archiveName + Twine(':') + getName()).str();
+
+  return nameForScriptCache;
+}
+
 template <class ELFT> DWARFCache *ObjFile<ELFT>::getDwarf() {
   llvm::call_once(initDwarf, [this]() {
     dwarf = std::make_unique<DWARFCache>(std::make_unique<DWARFContext>(
         std::make_unique<LLDDwarfObj<ELFT>>(this), "",
         [&](Error err) { warn(getName() + ": " + toString(std::move(err))); },
         [&](Error warning) {
           warn(getName() + ": " + toString(std::move(warning)));
         }));

lld/ELF/LinkerScript.h

 #include <functional>
 #include <memory>
 #include <vector>
 
 namespace lld {
 namespace elf {
 
 class Defined;
+class InputFile;
 class InputSection;
 class InputSectionBase;
 class OutputSection;
 class SectionBase;
 class Symbol;
 class ThunkSection;
 
 // This represents an r-value in the linker script.
struct MemoryRegion {
   uint32_t flags;
   uint32_t negFlags;
   uint64_t curPos = 0;
 };
 
 // This struct represents one section match pattern in SECTIONS() command.
 // It can optionally have negative match pattern for EXCLUDED_FILE command.
 // Also it may be surrounded with SORT() command, so contains sorting rules.
-struct SectionPattern {
+class SectionPattern {
+  StringMatcher excludedFilePat;
+
+  // Cache of the most recent input argument and result of excludesFile().
+  mutable llvm::Optional<std::pair<const InputFile *, bool>> excludesFileCache;
+
+public:
   SectionPattern(StringMatcher &&pat1, StringMatcher &&pat2)
       : excludedFilePat(pat1), sectionPat(pat2),
         sortOuter(SortSectionPolicy::Default),
         sortInner(SortSectionPolicy::Default) {}
 
-  StringMatcher excludedFilePat;
+  bool excludesFile(const InputFile *file) const;
+
   StringMatcher sectionPat;
   SortSectionPolicy sortOuter;
   SortSectionPolicy sortInner;
 };
 
-struct InputSectionDescription : BaseCommand {
+class InputSectionDescription : public BaseCommand {
+  SingleStringMatcher filePat;
+
+  // Cache of the most recent input argument and result of matchesFile().
+  mutable llvm::Optional<std::pair<const InputFile *, bool>> matchesFileCache;
+
+public:
   InputSectionDescription(StringRef filePattern, uint64_t withFlags = 0,
                           uint64_t withoutFlags = 0)
       : BaseCommand(InputSectionKind), filePat(filePattern),
         withFlags(withFlags), withoutFlags(withoutFlags) {}
 
   static bool classof(const BaseCommand *c) {
     return c->kind == InputSectionKind;
   }
 
-  SingleStringMatcher filePat;
+  bool matchesFile(const InputFile *file) const;
 
   // Input sections that matches at least one of SectionPatterns
   // will be associated with this InputSectionDescription.
   std::vector<SectionPattern> sectionPatterns;
 
   // Includes InputSections and MergeInputSections. Used temporarily during
   // assignment of input sections to output sections.
   std::vector<InputSectionBase *> sectionBases;
 

lld/ELF/LinkerScript.cpp

if (v.isAbsolute()) {
     cmd->sym->value = v.getValue();
   } else {
     cmd->sym->section = v.sec;
     cmd->sym->value = v.getSectionOffset();
   }
   cmd->sym->type = v.type;
 }
 
-static std::string getFilename(InputFile *file) {
-  if (!file)
-    return "";
-  if (file->archiveName.empty())
-    return std::string(file->getName());
-  return (file->archiveName + ':' + file->getName()).str();
+static inline StringRef getFilename(const InputFile *file) {
+  return file ? file->getNameForScript() : StringRef();
 }
 
-bool LinkerScript::shouldKeep(InputSectionBase *s) {
-  if (keptSections.empty())
+bool InputSectionDescription::matchesFile(const InputFile *file) const {
+  if (filePat.isTrivialMatchAll())
+    return true;
+
+  if (!matchesFileCache || matchesFileCache->first != file)
+    matchesFileCache.emplace(file, filePat.match(getFilename(file)));
+
+  return matchesFileCache->second;
+}
+
+bool SectionPattern::excludesFile(const InputFile *file) const {
+  if (excludedFilePat.empty())
     return false;
-  std::string filename = getFilename(s->file);
+
+  if (!excludesFileCache || excludesFileCache->first != file)
+    excludesFileCache.emplace(file, excludedFilePat.match(getFilename(file)));
+
+  return excludesFileCache->second;
+}
+
+bool LinkerScript::shouldKeep(InputSectionBase *s) {
   for (InputSectionDescription *id : keptSections)
-    if (id->filePat.match(filename))
+    if (id->matchesFile(s->file))
       for (SectionPattern &p : id->sectionPatterns)
         if (p.sectionPat.match(s->name) &&
             (s->flags & id->withFlags) == id->withFlags &&
             (s->flags & id->withoutFlags) == 0)
           return true;
   return false;
 }
 
for (InputSectionBase *sec : sections) {
       if (isa<InputSection>(sec) &&
           cast<InputSection>(sec)->getRelocatedSection())
         continue;
 
       // Check the name early to improve performance in the common case.
       if (!pat.sectionPat.match(sec->name))
         continue;
 
-      std::string filename = getFilename(sec->file);
-      if (!cmd->filePat.match(filename) ||
-          pat.excludedFilePat.match(filename) ||
+      if (!cmd->matchesFile(sec->file) || pat.excludesFile(sec->file) ||
           (sec->flags & cmd->withFlags) != cmd->withFlags ||
           (sec->flags & cmd->withoutFlags) != 0)
         continue;
 
       ret.push_back(sec);
     }
 
     sortInputSections(

lld/ELF/Relocations.h

 
 template <class ELFT> void reportUndefinedSymbols();
 
 void hexagonTLSSymbolUpdate(ArrayRef<OutputSection *> outputSections);
 bool hexagonNeedsTLSSymbol(ArrayRef<OutputSection *> outputSections);
 
 class ThunkSection;
 class Thunk;
-struct InputSectionDescription;
+class InputSectionDescription;
 
 class ThunkCreator {
 public:
   // Return true if Thunks have been added to OutputSections
   bool createThunks(ArrayRef<OutputSection *> outputSections);
 
   // The number of completed passes of createThunks this permits us
   // to do one time initialization on Pass 0 and put a limit on the

lld/include/lld/Common/Strings.h

 public:
   // Create a StringPattern from Pattern to be matched exactly irregardless
   // of globbing characters if ExactMatch is true.
   SingleStringMatcher(llvm::StringRef Pattern);
 
   // Match s against this pattern, exactly if ExactMatch is true.
   bool match(llvm::StringRef s) const;
 
+  // Returns true for pattern "*" which will match all inputs.
+  bool isTrivialMatchAll() const {
+    return !ExactMatch && GlobPatternMatcher.isTrivialMatchAll();
+  }
+
 private:
   // Whether to do an exact match irregardless of the presence of wildcard
   // character.
   bool ExactMatch;
 
   // GlobPattern object if not doing an exact match.
   llvm::GlobPattern GlobPatternMatcher;
 
public:
 
   // Matcher for a single pattern.
   StringMatcher(llvm::StringRef Pattern)
       : patterns({SingleStringMatcher(Pattern)}) {}
 
   // Add a new pattern to the existing ones to match against.
   void addPattern(SingleStringMatcher Matcher) { patterns.push_back(Matcher); }
 
-  bool empty() { return patterns.empty(); }
+  bool empty() const { return patterns.empty(); }
 
   // Match s against the patterns.
   bool match(llvm::StringRef s) const;
 };
 
 } // namespace lld
 
 #endif