Use globMatch() instead of llvm::regex in linker scripts
This can speed up lld up to 5 times when linking applications
with large number of sections and using linker script.
Differential revision: https://reviews.llvm.org/D26241
llvm-svn: 285895
diff --git a/lld/ELF/LinkerScript.cpp b/lld/ELF/LinkerScript.cpp
index b51cf80..1169f83 100644
--- a/lld/ELF/LinkerScript.cpp
+++ b/lld/ELF/LinkerScript.cpp
@@ -936,7 +936,7 @@
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();
@@ -1207,11 +1207,11 @@
.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() {
@@ -1236,7 +1236,7 @@
std::vector<SectionPattern> ScriptParser::readInputSectionsList() {
std::vector<SectionPattern> Ret;
while (!Error && peek() != ")") {
- Regex ExcludeFileRe;
+ StringMatcher ExcludeFileRe;
if (consume("EXCLUDE_FILE")) {
expect("(");
ExcludeFileRe = readFilePatterns();
@@ -1247,7 +1247,7 @@
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");
}
diff --git a/lld/ELF/LinkerScript.h b/lld/ELF/LinkerScript.h
index 8ab04ab..0503a6c 100644
--- a/lld/ELF/LinkerScript.h
+++ b/lld/ELF/LinkerScript.h
@@ -19,7 +19,6 @@
#include "llvm/ADT/MapVector.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/MemoryBuffer.h"
-#include "llvm/Support/Regex.h"
#include <functional>
namespace lld {
@@ -115,9 +114,9 @@
// 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);
@@ -126,18 +125,17 @@
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.
diff --git a/lld/ELF/Strings.cpp b/lld/ELF/Strings.cpp
index ffabd00..09459ab 100644
--- a/lld/ELF/Strings.cpp
+++ b/lld/ELF/Strings.cpp
@@ -21,6 +21,36 @@
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.
diff --git a/lld/ELF/Strings.h b/lld/ELF/Strings.h
index 5b61325..3194b99 100644
--- a/lld/ELF/Strings.h
+++ b/lld/ELF/Strings.h
@@ -25,6 +25,18 @@
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.