[ELF] Speed-up lld up to 5 times by replacing llvm:regex with simple string matcher.

[evgeny777]

Summary

This patch reduces linking time of libcxx (libcxx.llvm.org) test suite from 11.1 sec to 2.3 sec on my PC (i7-2600K, 16GB RAM, SSD).
Can provide VSP (Visual Studio performance report) files on request.

[grimar]

I wonder if that really passes all the tests ?
My concern comes from https://reviews.llvm.org/D23803?vs=on&id=68992&whitespace=ignore-most#toc which was initially posted to implement
[char].
That patch later was converted to use regexps instead of initial implementation. Though implementation in your patch seems does not handle [char]. Don't our tests should catch that ?

[evgeny777]

Can you point out the test which should fail? I have all them passing (Ubuntu host).
Also it looks like globMatch does support character wildcard (see Strings.cpp:41)

[grimar]

So if only linker script was switched to use globMatch(), then other places will not fail. Like version-script-complex-wildcards.s.
There is some inconsistency though, may be we might want to switch all places from using regexp after that one ?

[joerg]

Wouldn't it be better in general to handle fixed string prefixes directly in the matcher and only fallback to a more generic matcher if the prefix check passes? Independent of glob or regex, there are three basic situations:

• fixed string match --> done after the prefix match
• fixed prefix, wildcard rest --> done after the prefix match
• rest

I wonder how much of the performance benefit is obtained by just doing this peephole optimisation.

[evgeny777]

That probably makes sense, because globMatch still consumes about 11% of running time in my case. But I'd do this in separate patch if this one lands.

[AntonBikineev]

ELF/Strings.h

34 ↗

(On Diff #76696)

Pat is not a forwarding reference in this context, so just move can be used here

[ruiu]

I think the problem is that llvm::regex is slow. If you want to optimize something, you might want to do that in llvm::regex instead of doing it on LLD side. For example, if a pattern doesn't contain any meta character, llvm::regex can use a simple string comparison. Or, if a pattern doesn't contain a substring-capturing patterns (e.g. /(.*)/), it can compile the regex into a DFA instead of NFA (I don't know if llvm::regex does this already).

[evgeny777]

If you want to optimize something, you might want to do that in llvm::regex

AFAIK llvm::regex is NFA (it's actually a rip from OpenBSD). Are you suggesting to implement additional DFA engine for this purpose?

[ruiu]

ELF/Strings.h

32–33 ↗

(On Diff #76696)

Add explicit.

36 ↗

(On Diff #76696)

Move this definition to Strings.cpp and make globMatch static, so that we can keep globMatch inside a file-scope.

42 ↗

(On Diff #76696)

Make this private.

[ruiu]

You need to handle [characters] as George pointed out. Don't we have a test for that?

[ruiu]

LGTM. Let's land this and improve in follow-up patches.

lld/trunk/ELF/LinkerScript.h

 #include "Strings.h"
 #include "Writer.h"
 #include "lld/Core/LLVM.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/MemoryBuffer.h"
-#include "llvm/Support/Regex.h"
 #include <functional>
 
 namespace lld {
 namespace elf {
 class DefinedCommon;
 class ScriptParser;
 class SymbolBody;
 template <class ELFT> class InputSectionBase;
struct OutputSectionCommand : BaseCommand {
   std::vector<uint8_t> Filler;
   ConstraintKind Constraint = ConstraintKind::NoConstraint;
 };
 
 // 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 {
-  SectionPattern(llvm::Regex &&Re1, llvm::Regex &&Re2)
-      : ExcludedFileRe(std::forward<llvm::Regex>(Re1)),
-        SectionRe(std::forward<llvm::Regex>(Re2)) {}
+  SectionPattern(StringMatcher &&Re1, StringMatcher &&Re2)
+      : ExcludedFileRe(std::forward<StringMatcher>(Re1)),
+        SectionRe(std::forward<StringMatcher>(Re2)) {}
 
   SectionPattern(SectionPattern &&Other) {
     std::swap(ExcludedFileRe, Other.ExcludedFileRe);
     std::swap(SectionRe, Other.SectionRe);
     std::swap(SortOuter, Other.SortOuter);
     std::swap(SortInner, Other.SortInner);
   }
 
-  llvm::Regex ExcludedFileRe;
-  llvm::Regex SectionRe;
+  StringMatcher ExcludedFileRe;
+  StringMatcher SectionRe;
   SortSectionPolicy SortOuter;
   SortSectionPolicy SortInner;
 };
 
 struct InputSectionDescription : BaseCommand {
   InputSectionDescription(StringRef FilePattern)
-      : BaseCommand(InputSectionKind),
-        FileRe(compileGlobPatterns({FilePattern})) {}
+      : BaseCommand(InputSectionKind), FileRe(FilePattern) {}
   static bool classof(const BaseCommand *C);
-  llvm::Regex FileRe;
+  StringMatcher FileRe;
 
   // Input sections that matches at least one of SectionPatterns
   // will be associated with this InputSectionDescription.
   std::vector<SectionPattern> SectionPatterns;
 
   std::vector<InputSectionData *> Sections;
 };
 

lld/trunk/ELF/LinkerScript.cpp

private:
 
   SymbolAssignment *readAssignment(StringRef Name);
   BytesDataCommand *readBytesDataCommand(StringRef Tok);
   std::vector<uint8_t> readFill();
   OutputSectionCommand *readOutputSectionDescription(StringRef OutSec);
   std::vector<uint8_t> readOutputSectionFiller(StringRef Tok);
   std::vector<StringRef> readOutputSectionPhdrs();
   InputSectionDescription *readInputSectionDescription(StringRef Tok);
-  Regex readFilePatterns();
+  StringMatcher readFilePatterns();
   std::vector<SectionPattern> readInputSectionsList();
   InputSectionDescription *readInputSectionRules(StringRef FilePattern);
   unsigned readPhdrType();
   SortSectionPolicy readSortKind();
   SymbolAssignment *readProvideHidden(bool Provide, bool Hidden);
   SymbolAssignment *readProvideOrAssignment(StringRef Tok);
   void readSort();
   Expr readAssert();
return StringSwitch<int>(Op)
       .Cases("*", "/", 5)
       .Cases("+", "-", 4)
       .Cases("<<", ">>", 3)
       .Cases("<", "<=", ">", ">=", "==", "!=", 2)
       .Cases("&", "|", 1)
       .Default(-1);
 }
 
-Regex ScriptParser::readFilePatterns() {
+StringMatcher ScriptParser::readFilePatterns() {
   std::vector<StringRef> V;
   while (!Error && !consume(")"))
     V.push_back(next());
-  return compileGlobPatterns(V);
+  return StringMatcher(std::move(V));
 }
 
 SortSectionPolicy ScriptParser::readSortKind() {
   if (consume("SORT") || consume("SORT_BY_NAME"))
     return SortSectionPolicy::Name;
   if (consume("SORT_BY_ALIGNMENT"))
     return SortSectionPolicy::Alignment;
   if (consume("SORT_BY_INIT_PRIORITY"))
     return SortSectionPolicy::Priority;
   if (consume("SORT_NONE"))
     return SortSectionPolicy::None;
   return SortSectionPolicy::Default;
 }
 
 // Method reads a list of sequence of excluded files and section globs given in
 // a following form: ((EXCLUDE_FILE(file_pattern+))? section_pattern+)+
 // Example: *(.foo.1 EXCLUDE_FILE (*a.o) .foo.2 EXCLUDE_FILE (*b.o) .foo.3)
 // The semantics of that is next:
 // * Include .foo.1 from every file.
 // * Include .foo.2 from every file but a.o
 // * Include .foo.3 from every file but b.o
 std::vector<SectionPattern> ScriptParser::readInputSectionsList() {
   std::vector<SectionPattern> Ret;
   while (!Error && peek() != ")") {
-    Regex ExcludeFileRe;
+    StringMatcher ExcludeFileRe;
     if (consume("EXCLUDE_FILE")) {
       expect("(");
       ExcludeFileRe = readFilePatterns();
     }
 
     std::vector<StringRef> V;
     while (!Error && peek() != ")" && peek() != "EXCLUDE_FILE")
       V.push_back(next());
 
     if (!V.empty())
-      Ret.push_back({std::move(ExcludeFileRe), compileGlobPatterns(V)});
+      Ret.push_back({std::move(ExcludeFileRe), StringMatcher(std::move(V))});
     else
       setError("section pattern is expected");
   }
   return Ret;
 }
 
 // Section pattern grammar can have complex expressions, for example:
 // *(SORT(.foo.* EXCLUDE_FILE (*file1.o) .bar.*) .bar.* SORT(.zed.*))

lld/trunk/ELF/Strings.h

 namespace elf {
 llvm::Regex compileGlobPatterns(ArrayRef<StringRef> V);
 int getPriority(StringRef S);
 bool hasWildcard(StringRef S);
 std::vector<uint8_t> parseHex(StringRef S);
 bool isValidCIdentifier(StringRef S);
 StringRef unquote(StringRef S);
 
+class StringMatcher {
+public:
+  StringMatcher() = default;
+  explicit StringMatcher(StringRef P) : Patterns({P}) {}
+  explicit StringMatcher(std::vector<StringRef> &&Pat)
+      : Patterns(std::move(Pat)) {}
+
+  bool match(StringRef S);
+private:
+  std::vector<StringRef> Patterns;
+};
+
 // Returns a demangled C++ symbol name. If Name is not a mangled
 // name or the system does not provide __cxa_demangle function,
 // it returns an unmodified string.
 std::string demangle(StringRef Name);
 
 // Demangle if Config->Demangle is true.
 std::string maybeDemangle(StringRef Name);
 
 inline StringRef toStringRef(ArrayRef<uint8_t> Arr) {
   return {(const char *)Arr.data(), Arr.size()};
 }
 }
 }
 
 #endif

lld/trunk/ELF/Strings.cpp

 #include "llvm/Config/config.h"
 #include "llvm/Demangle/Demangle.h"
 #include <algorithm>
 
 using namespace llvm;
 using namespace lld;
 using namespace lld::elf;
 
+// Returns true if S matches T. S can contain glob meta-characters.
+// The asterisk ('*') matches zero or more characters, and the question
+// mark ('?') matches one character.
+static bool globMatch(StringRef S, StringRef T) {
+  for (;;) {
+    if (S.empty())
+      return T.empty();
+    if (S[0] == '*') {
+      S = S.substr(1);
+      if (S.empty())
+        // Fast path. If a pattern is '*', it matches anything.
+        return true;
+      for (size_t I = 0, E = T.size(); I < E; ++I)
+        if (globMatch(S, T.substr(I)))
+          return true;
+      return false;
+    }
+    if (T.empty() || (S[0] != T[0] && S[0] != '?'))
+      return false;
+    S = S.substr(1);
+    T = T.substr(1);
+  }
+}
+
+bool StringMatcher::match(StringRef S) {
+  for (StringRef P : Patterns)
+    if (globMatch(P, S))
+      return true;
+  return false;
+}
 // If an input string is in the form of "foo.N" where N is a number,
 // return N. Otherwise, returns 65536, which is one greater than the
 // lowest priority.
 int elf::getPriority(StringRef S) {
   size_t Pos = S.rfind('.');
   if (Pos == StringRef::npos)
     return 65536;
   int V;