[ELF] - Linkerscript: add InputSectionDescription command to LS parser.

[grimar]

Summary

This adds InputSectionDescription command to represent
the input section declaration.

This leads to next cleanup:
SectionRule removed.
ScriptConfiguration::Sections mamber removed.
LinkerScript<ELFT>::getOutputSection() removed.

[evgeny777]

ELF/LinkerScript.cpp

220 ↗

(On Diff #64843)

It looks like a slow-down compared with previous one, no?

[grimar]

ELF/LinkerScript.cpp

220 ↗

(On Diff #64843)

That fits in new design. I am sure we will spend time on optimization of LS later,
when will be able to run benchmarks. And probably many places will need tweaking,
for now I don't think it is critical to change until major slowdown is proven.

[evgeny777]

ELF/LinkerScript.cpp

220 ↗

(On Diff #64843)

As far as I understand if --gc-sections command line switch is set, then markLive() calls LinkerScript::shouldKeep() for every input section. There could easily be millions of input sections in large projects like WebKit or LLVM itself. It might not be a good idea to sacrifice performance that much in favor of design improvements.

[grimar]

ELF/LinkerScript.cpp

220 ↗

(On Diff #64843)

I think the most slow here is the call of globMatch. Amount of calls remained the same.

[evgeny777]

ELF/LinkerScript.cpp

220 ↗

(On Diff #64843)

Well, the time complexity in your new code is O(I*R), I - number of sections, R - number of rules
Imagine you don't have any kept sections and don't call globMatch. Let's say you have 1 million sections and 10 rules total in script
Your for statements are actually for_each, at average you need about 20 instructions (with -O2 and 100 without optimization) for a single iteration (this is just 'for' statement without body).
Let's say you'll need 50 instructions for each rule (just assumption - can't tell the exact number), so

1 000 000 * 10 * 50 = 500 000 000
On 2 Ghz processor and 1 clock cycle per instruction

t = (5 * 10^8) / (2*10^9) = 0.25 sec.
for doing nothing

Is it worth that?

[ruiu]

ELF/LinkerScript.cpp

220 ↗

(On Diff #64843)

Yeah, I have a feeling that we should keep KeptSections mostly for simplicity. The reason why we want to construct an AST in a way that that reflects the structure of a given linker script is because we want to construct output sections in the same order as they appear in a linker script. On the other hand, "KEEP" seems to have been just piggybacking the grammar which they already had. It doesn't belong to this much deep data structure.

250 ↗

(On Diff #64843)

I think you still want to iterate over SECTIONS subcommands. Eventually we want to create output sections and add input sections to them while we are visiting SECTIONS subcommands so that the results are naturally sorted by the same order as they appear in a linker script, so that we don't need to sort the results afterwards.

745 ↗

(On Diff #64843)

Use auto.

754 ↗

(On Diff #64843)

Ditto

[grimar]

• Addressed review comments.

[evgeny777]

ELF/LinkerScript.h

45 ↗

(On Diff #64854)

See comment above:

This enum represents what we can observe in SECTIONS tag of script.
(https://sourceware.org/binutils/docs/ld/SECTIONS.html#SECTIONS)

If you follow the link:

Each sections-command may of be one of the following:

- an ENTRY command (see Entry command)
- a symbol assignment (see Assignments)
- an output section description
- an overlay description

[grimar]

ELF/LinkerScript.cpp

220 ↗

(On Diff #64843)

Reverted to KeptSections.

250 ↗

(On Diff #64843)

I see. Done. Looks a little bit more complicated now though.

745 ↗

(On Diff #64843)

Done.

754 ↗

(On Diff #64843)

Done.

ELF/LinkerScript.h

45 ↗

(On Diff #64854)

Well, comment is depricated. I guess we do not want to treat SectionsCommandKind as written anymore, so it can be removed completely,
Rui, what do you think ?

[ruiu]

ELF/LinkerScript.cpp

202 ↗

(On Diff #64854)

Do you still need this function?

247 ↗

(On Diff #64854)

OutSec as a name for a command is very confusing.

249 ↗

(On Diff #64854)

Flip if conditions and do continue to reduce indentation levels.

ELF/LinkerScript.h

45 ↗

(On Diff #64854)

We should just remove this comment and leave the link to the documentation.

76 ↗

(On Diff #64854)

Now you can remove this.

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

202 ↗

(On Diff #64854)

getOutputSection() was used in LinkerScript<ELFT>::isDiscarded().
I changed logic to avoid the using as "/DISCARD/" can just be processed as
special section kind.

247 ↗

(On Diff #64854)

Changed to OutSec.

249 ↗

(On Diff #64854)

Done.

ELF/LinkerScript.h

45 ↗

(On Diff #64854)

Done.

76 ↗

(On Diff #64854)

Done.

[grimar]

ELF/LinkerScript.cpp

247 ↗

(On Diff #64854)

I mean to OutCmd, sorry.

[ruiu]

ELF/LinkerScript.cpp

240 ↗

(On Diff #64860)

Again, InSec is a confusing name.

249–253 ↗

(On Diff #64860)

Regular for-each loop is probably easier to read.

ELF/LinkerScript.h

93–94 ↗

(On Diff #64860)

Remove.

[grimar]

• Addressed review comments.

ELF/LinkerScript.cpp

240 ↗

(On Diff #64860)

Fixed.

249–253 ↗

(On Diff #64860)

Changed.

ELF/LinkerScript.h

93–94 ↗

(On Diff #64860)

Done.

[ruiu]

ELF/LinkerScript.cpp

234 ↗

(On Diff #64865)

This change will make this function too long, but that's probably okay for now. I'll try to split it up.

259 ↗

(On Diff #64865)

break at end of a for-loop?

261–262 ↗

(On Diff #64865)

If you need {}, please put {} all inner loops.

[grimar]

ELF/LinkerScript.cpp

259 ↗

(On Diff #64865)

Yes, break. I need to exit this loop after first AddInputSec. As we do not want to add the section again if there are multiple pattern matches.
That was why I used std::find_if in previous iteration.
May be worth to revert to previous version ?

[ruiu]

ELF/LinkerScript.cpp

259 ↗

(On Diff #64865)

You can define a function taking two parameters, a stringref and an arrayref of stringref, which returns true if the former string glob-matches one of the latter strings.

[grimar]

ELF/LinkerScript.cpp

259 ↗

(On Diff #64865)

What about next ?

static bool hasGlobMatch(StringRef T, ArrayRef<StringRef> L) {
  for (StringRef S : L)
    if (globMatch(S, T))
      return true;
  return false;
}

[grimar]

• Addressed review comments.

[ruiu]

ELF/LinkerScript.cpp

259 ↗

(On Diff #64865)

That's what I meant. (a few nits are: I'd name the function match because "GlobMatch" is not an object or a thing, rename T Pattern, and swap T and L to match the parameter order of globMatch.)

[grimar]

ELF/LinkerScript.cpp

266 ↗

(On Diff #64871)

Afraid I am a bit lost in this puzzle :)
Is that what you mean ?

static bool match(StringRef T, ArrayRef<StringRef> Pattern) {
  for (StringRef S : Pattern)
    if (globMatch(S, T))
      return true;
  return false;
}

[ruiu]

LGTM with the change.

ELF/LinkerScript.cpp

266 ↗

(On Diff #64871)

1. I want parameters of similar functions be ordered in a consistent way. However, your new function takes [Pattern Target] although globMatch takes [Target Pattern]
2. T is too short and doesn't convey it is a glob pattern rather.
3. Apparently Pattern is not a right name for ArrayRef<StringRef> that doesn't contain patterns
   
   static bool match(StringRef Pattern, ArrayRef<StringRef> Arr) { for (StringRef S : Arr) if (globMatch(Pattern, S)) return true; return false; }

[grimar]

ELF/LinkerScript.cpp

266 ↗

(On Diff #64871)

Ok, now I see what you meant. Sorry for my confusion and thanks a lot for all reviews !

[grimar]

ELF/LinkerScript.cpp

266 ↗

(On Diff #64871)

// 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.
bool elf::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);
  }
}

1. According to comments S is pattern. So it takes [Pattern, Target].
2. My function searches Name in a list of wildcards, that mean second is a list of patterns, so ArrayRef<StringRef> *contains* patterns.

For function to work as I need, it needs to be:

if (globMatch(S, Pattern))

instead of

if (globMatch(Pattern, S))

And that is what inconsistent with globMatch,
which has Pattern as first argument.

I am really not trying to argue here. I`ll commit it and just please adjust the naming as you want after that.

lld/trunk/ELF/LinkerScript.h

 // Parses a linker script. Calling this function updates
 // Config and ScriptConfig.
 void readLinkerScript(MemoryBufferRef MB);
 
 class ScriptParser;
 template <class ELFT> class InputSectionBase;
 template <class ELFT> class OutputSectionBase;
 
-// This class represents each rule in SECTIONS command.
-struct SectionRule {
-  SectionRule(StringRef D, StringRef S)
-      : Dest(D), SectionPattern(S) {}
-
-  StringRef Dest;
-
-  StringRef SectionPattern;
-};
-
-// This enum represents what we can observe in SECTIONS tag of script.
-// Each sections-command may of be one of the following:
-// (https://sourceware.org/binutils/docs/ld/SECTIONS.html#SECTIONS)
-// * An ENTRY command.
-// * A symbol assignment.
-// * An output section description.
-// * An overlay description.
-// We support only AssignmentKind and OutputSectionKind for now.
-enum SectionsCommandKind { AssignmentKind, OutputSectionKind };
+// This enum is used to implement linker script SECTIONS command.
+// https://sourceware.org/binutils/docs/ld/SECTIONS.html#SECTIONS
+enum SectionsCommandKind {
+  AssignmentKind,
+  OutputSectionKind,
+  InputSectionKind
+};
 
 struct BaseCommand {
   BaseCommand(int K) : Kind(K) {}
   virtual ~BaseCommand() {}
   int Kind;
 };
 
 struct SymbolAssignment : BaseCommand {
   SymbolAssignment(StringRef Name, std::vector<StringRef> &Expr)
       : BaseCommand(AssignmentKind), Name(Name), Expr(std::move(Expr)) {}
   static bool classof(const BaseCommand *C);
   StringRef Name;
   std::vector<StringRef> Expr;
 };
 
 struct OutputSectionCommand : BaseCommand {
   OutputSectionCommand(StringRef Name)
       : BaseCommand(OutputSectionKind), Name(Name) {}
   static bool classof(const BaseCommand *C);
   StringRef Name;
+  std::vector<std::unique_ptr<BaseCommand>> Commands;
   std::vector<StringRef> Phdrs;
   std::vector<uint8_t> Filler;
 };
 
+struct InputSectionDescription : BaseCommand {
+  InputSectionDescription() : BaseCommand(InputSectionKind) {}
+  static bool classof(const BaseCommand *C);
+  std::vector<StringRef> Patterns;
+};
+
 struct PhdrsCommand {
   StringRef Name;
   unsigned Type;
   bool HasFilehdr;
   bool HasPhdrs;
   unsigned Flags;
 };
 
 // ScriptConfiguration holds linker script parse results.
 struct ScriptConfiguration {
-  // SECTIONS commands.
-  std::vector<SectionRule> Sections;
-
   // Used to assign addresses to sections.
   std::vector<std::unique_ptr<BaseCommand>> Commands;
 
   // Used to assign sections to headers.
   std::vector<PhdrsCommand> PhdrsCommands;
 
   bool DoLayout = false;
 
template <class ELFT> class LinkerScript {
   typedef typename ELFT::uint uintX_t;
 
 public:
   typedef PhdrEntry<ELFT> Phdr;
 
   std::vector<OutputSectionBase<ELFT> *>
   createSections(OutputSectionFactory<ELFT> &Factory);
 
-  StringRef getOutputSection(InputSectionBase<ELFT> *S);
   ArrayRef<uint8_t> getFiller(StringRef Name);
   bool isDiscarded(InputSectionBase<ELFT> *S);
   bool shouldKeep(InputSectionBase<ELFT> *S);
   void assignAddresses(ArrayRef<OutputSectionBase<ELFT> *> S);
   int compareSections(StringRef A, StringRef B);
   void addScriptedSymbols();
   std::vector<Phdr> createPhdrs(ArrayRef<OutputSectionBase<ELFT> *> S);
   bool hasPhdrsCommands();

lld/trunk/ELF/LinkerScript.cpp

 bool SymbolAssignment::classof(const BaseCommand *C) {
   return C->Kind == AssignmentKind;
 }
 
 bool OutputSectionCommand::classof(const BaseCommand *C) {
   return C->Kind == OutputSectionKind;
 }
 
+bool InputSectionDescription::classof(const BaseCommand *C) {
+  return C->Kind == InputSectionKind;
+}
+
 // This is an operator-precedence parser to parse and evaluate
 // a linker script expression. For each linker script arithmetic
 // expression (e.g. ". = . + 0x1000"), a new instance of ExprParser
 // is created and ran.
 namespace {
 class ExprParser : public ScriptParserBase {
 public:
   ExprParser(std::vector<StringRef> &Tokens, uint64_t Dot)
uint64_t ExprParser::parseExpr1(uint64_t Lhs, int MinPrec) {
   }
   return Lhs;
 }
 
 // Reads and evaluates an arithmetic expression.
 uint64_t ExprParser::parseExpr() { return parseExpr1(parsePrimary(), 0); }
 
 template <class ELFT>
-StringRef LinkerScript<ELFT>::getOutputSection(InputSectionBase<ELFT> *S) {
-  for (SectionRule &R : Opt.Sections)
-    if (globMatch(R.SectionPattern, S->getSectionName()))
-      return R.Dest;
-  return "";
-}
-
-template <class ELFT>
 bool LinkerScript<ELFT>::isDiscarded(InputSectionBase<ELFT> *S) {
-  return !S || !S->Live || getOutputSection(S) == "/DISCARD/";
+  return !S || !S->Live;
 }
 
 template <class ELFT>
 bool LinkerScript<ELFT>::shouldKeep(InputSectionBase<ELFT> *S) {
   for (StringRef Pat : Opt.KeptSections)
     if (globMatch(Pat, S->getSectionName()))
       return true;
   return false;
 }
 
+static bool match(StringRef Pattern, ArrayRef<StringRef> Arr) {
+  for (StringRef S : Arr)
+    if (globMatch(S, Pattern))
+      return true;
+  return false;
+}
+
 template <class ELFT>
 std::vector<OutputSectionBase<ELFT> *>
 LinkerScript<ELFT>::createSections(OutputSectionFactory<ELFT> &Factory) {
+  typedef const std::unique_ptr<ObjectFile<ELFT>> ObjectFile;
   std::vector<OutputSectionBase<ELFT> *> Result;
 
   // Add input section to output section. If there is no output section yet,
   // then create it and add to output section list.
   auto AddInputSec = [&](InputSectionBase<ELFT> *C, StringRef Name) {
     OutputSectionBase<ELFT> *Sec;
     bool IsNew;
     std::tie(Sec, IsNew) = Factory.create(C, Name);
     if (IsNew)
       Result.push_back(Sec);
     Sec->addSection(C);
   };
 
   // Select input sections matching rule and add them to corresponding
   // output section. Section rules are processed in order they're listed
   // in script, so correct input section order is maintained by design.
-  for (SectionRule &R : Opt.Sections)
-    for (const std::unique_ptr<ObjectFile<ELFT>> &F :
-         Symtab<ELFT>::X->getObjectFiles())
-      for (InputSectionBase<ELFT> *S : F->getSections())
-        if (!isDiscarded(S) && !S->OutSec &&
-            globMatch(R.SectionPattern, S->getSectionName()))
-          // Add single input section to output section.
-          AddInputSec(S, R.Dest);
+  for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands) {
+    auto *OutCmd = dyn_cast<OutputSectionCommand>(Base.get());
+    if (!OutCmd)
+      continue;
+
+    for (const std::unique_ptr<BaseCommand> &Cmd : OutCmd->Commands) {
+      auto *InCmd = dyn_cast<InputSectionDescription>(Cmd.get());
+      if (!InCmd)
+        continue;
+
+      for (ObjectFile &F : Symtab<ELFT>::X->getObjectFiles()) {
+        for (InputSectionBase<ELFT> *S : F->getSections()) {
+          if (isDiscarded(S) || S->OutSec)
+            continue;
+
+          if (match(S->getSectionName(), InCmd->Patterns)) {
+            if (OutCmd->Name == "/DISCARD/")
+              S->Live = false;
+            else
+              AddInputSec(S, OutCmd->Name);
+          }
+        }
+      }
+    }
+  }
 
   // Add all other input sections, which are not listed in script.
-  for (const std::unique_ptr<ObjectFile<ELFT>> &F :
-       Symtab<ELFT>::X->getObjectFiles())
+  for (ObjectFile &F : Symtab<ELFT>::X->getObjectFiles())
     for (InputSectionBase<ELFT> *S : F->getSections())
       if (!isDiscarded(S)) {
         if (!S->OutSec)
           AddInputSec(S, getOutputSectionName(S));
       } else
         reportDiscarded(S, F);
 
   return Result;
void ScriptParser::readOutputSectionDescription(StringRef OutSec) {
   OutputSectionCommand *Cmd = new OutputSectionCommand(OutSec);
   Opt.Commands.emplace_back(Cmd);
   expect(":");
   expect("{");
 
   while (!Error && !skip("}")) {
     StringRef Tok = next();
     if (Tok == "*") {
+      auto *InCmd = new InputSectionDescription();
+      Cmd->Commands.emplace_back(InCmd);
       expect("(");
       while (!Error && !skip(")"))
-        Opt.Sections.emplace_back(OutSec, next());
+        InCmd->Patterns.push_back(next());
     } else if (Tok == "KEEP") {
       expect("(");
       expect("*");
       expect("(");
+      auto *InCmd = new InputSectionDescription();
+      Cmd->Commands.emplace_back(InCmd);
       while (!Error && !skip(")")) {
-        StringRef Sec = next();
-        Opt.Sections.emplace_back(OutSec, Sec);
-        Opt.KeptSections.push_back(Sec);
+        Opt.KeptSections.push_back(peek());
+        InCmd->Patterns.push_back(next());
       }
       expect(")");
     } else {
       setError("unknown command " + Tok);
     }
   }
   Cmd->Phdrs = readOutputSectionPhdrs();
 

lld/trunk/ELF/Writer.cpp

private:
 
   uintX_t FileSize;
   uintX_t SectionHeaderOff;
 };
 } // anonymous namespace
 
 template <class ELFT>
 StringRef elf::getOutputSectionName(InputSectionBase<ELFT> *S) {
-  StringRef Dest = Script<ELFT>::X->getOutputSection(S);
-  if (!Dest.empty())
-    return Dest;
-
   StringRef Name = S->getSectionName();
   for (StringRef V : {".text.", ".rodata.", ".data.rel.ro.", ".data.", ".bss.",
                       ".init_array.", ".fini_array.", ".ctors.", ".dtors.",
                       ".tbss.", ".gcc_except_table.", ".tdata."})
     if (Name.startswith(V))
       return V.drop_back();
   return Name;
 }