ELF: Add +, -, *, / and & to SECTIONS linker script command.

[ruiu]

Summary

This patch is based heavily on George Rimar's patch
http://reviews.llvm.org/D19221.

In the linker script, you can write expressions to compute addresses.
Currently we only support "+" operator. This adds a few more operators.

Since this patch adds * and /, we need to handle operator precedences
properly. I implemented that using the operator-precedence grammar.

[grimar]

It was really interesting to debug for me.
But honestly speaking I find my version much more readable.
It does not have recursion, and it is straightforward:
it builds RPN and calculates it, 2 logically separated calls at fact.

Your code works and avoids building intermediate stuff,
but I found 3 call of parseExpr and 3 call of parsePrimary,
all from different places and also recursion involved and makes it hard to debug.
You pass MinPrec which changes because of recursion calls,
Dot is required parameter for each of 3 methods.
That does not look straightforward, in overall feels much more
complicated when debugging non trivial expressions for me.

At the same time both approach should work about the same speed
(and both are very fast), complexity of mine is also O(N),
the fact of building RPN in the middle is greatly improves readability.
Mine version has more code, but that can be solved by placing operators
handlers in one method, like you did.

So I would really prefer mine version here(after few tweaks). You deside.

[ruiu]

The operator precedence parsing is a pretty popular parsing technique to parse an operator-precedence grammar. Of course I didn't invent it, and it is not the first time for me to write it; it is a well known and well understood technique which is described in compiler textbooks. It's probably not an unreasonable assumption that readers already know it. I believe that the algorithm is usually the first choice when you are to parse an arithmetic expression, so I wonder why you want to do that differently.

[grimar]

In D19237#405107, @ruiu wrote:

The operator precedence parsing is a pretty popular parsing technique to parse an operator-precedence grammar. Of course I didn't invent it, and it is not the first time for me to write it; it is a well known and well understood technique which is described in compiler textbooks. It's probably not an unreasonable assumption that readers already know it. I believe that the algorithm is usually the first choice when you are to parse an arithmetic expression, so I wonder why you want to do that differently.

I have no doubt its popular and was used in many compilers, I just find this implementation not so straightforward due to lots of cross calls and recursion in compare with my version. And I really see no benefits to use it then.

[grimar]

not so straightforward

[ruiu]

It uses recursion because the grammar is recursive. Do you find the recursive-descendent parser is hard to read because it uses recursion? Even if your code does not make recursive function calls, you have to handle recursive grammar using some recursive data structure (such as hand-crafted stack rather than call stack.)

Nothing is special in my code, it is a plain operator-precedence parser. If you write a parser for a calculator-ish grammer, and if you don't need a parser tree, then I think that the operator-precedence parser is usually the first choice. It is common technique so readers don't have to take a look at every detail of the code; it can be understood just by reading the comment that this is an operator-precedence grammar, because the implementation is obvious as long as you are familiar with the theory. If we have a reason to create an intermediate representation of an expression, then doing it in your way might make sense, but I think that's not the case.

[grimar]

In D19237#405186, @ruiu wrote:

It uses recursion because the grammar is recursive. Do you find the recursive-descendent parser is hard to read because it uses recursion? Even if your code does not make recursive function calls, you have to handle recursive grammar using some recursive data structure (such as hand-crafted stack rather than call stack.)

Nothing is special in my code, it is a plain operator-precedence parser. If you write a parser for a calculator-ish grammer, and if you don't need a parser tree, then I think that the operator-precedence parser is usually the first choice. It is common technique so readers don't have to take a look at every detail of the code; it can be understood just by reading the comment that this is an operator-precedence grammar, because the implementation is obvious as long as you are familiar with the theory. If we have a reason to create an intermediate representation of an expression, then doing it in your way might make sense, but I think that's not the case.

I can say the same about mine, RPN building and evaluating is also known and used often technique.
I see nothing bad in intermediate representation, it does not waste time to be created as complexity almost lowest possible and
I see no reasons why not to use it when overall readability is improved (IMO).
At the same time I am not sure this worth such long arguing. Lets go with your version if you want.
I`ll keep my opinion about mine one though :)

[ruiu]

If you are familiar with the both algorithms, then what's the reason to choose the one that needs more data types, more internal data structures and more iterations over the same data? If I were familiar with an algorithm but not with the other, then that could be a reason to choose one from the other, but I were not, then the choice is obvious. This patch is shorter and simpler. (Note that we could create a reverse-polish expression using the operator precedence parser instead of computing the value of an expression, but we wouldn't want to do that because it is redundant.)

[grimar]

In D19237#405288, @ruiu wrote:

If you are familiar with the both algorithms, then what's the reason to choose the one that needs more data types, more internal data structures and more iterations over the same data?

I was not familar with your algorithm when implemented my patch. And after I read about it, reviewed and debugged it, I find my version with more types and more structures much more readable exactly because it has all af that. May be not algorithm itself but at least implementation seems to me much simplier.

In D19237#405288, @ruiu wrote:

This patch is shorter and simpler.

I don't think so.

I have no arguments to continue. My best one was "I think that my version is better" seems not to work, though I really believe so.
Will you commit your one then ?

[ruiu]

I'll submit this patch since you have signed off. But I'd think you just need time to familiarize yourself with this algorithm, then you'd find this actually simpler to parse arithmetic expressions. This is really a good one. :)

lld/trunk/ELF/LinkerScript.h

public:
   template <class ELFT> bool shouldKeep(InputSectionBase<ELFT> *S);
   template <class ELFT>
   void assignAddresses(std::vector<OutputSectionBase<ELFT> *> &S);
   int compareSections(StringRef A, StringRef B);
 
   bool DoLayout = false;
 
 private:
-  uint64_t evaluate(std::vector<StringRef> &Tokens, uint64_t LocCounter);
   template <class ELFT> SectionRule *find(InputSectionBase<ELFT> *S);
 
   // SECTIONS commands.
   std::vector<SectionRule> Sections;
 
   // Output sections are sorted by this order.
   std::vector<StringRef> SectionOrder;
 

lld/trunk/ELF/LinkerScript.cpp

 
 #include "LinkerScript.h"
 #include "Config.h"
 #include "Driver.h"
 #include "InputSection.h"
 #include "OutputSections.h"
 #include "ScriptParser.h"
 #include "SymbolTable.h"
+#include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/ELF.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/StringSaver.h"
 
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace lld;
 using namespace lld::elf;
 
 LinkerScript *elf::Script;
 
 static uint64_t getInteger(StringRef S) {
   uint64_t V;
   if (S.getAsInteger(0, V)) {
     error("malformed number: " + S);
     return 0;
   }
   return V;
 }
 
-// Evaluates the expression given by list of tokens.
-uint64_t LinkerScript::evaluate(std::vector<StringRef> &Tokens,
-                                uint64_t LocCounter) {
-  uint64_t Result = 0;
-  for (size_t I = 0, E = Tokens.size(); I < E; ++I) {
-    // Each second token should be '+' as this is the
-    // only operator we support now.
-    if (I % 2 == 1) {
-      if (Tokens[I] == "+")
-        continue;
-      error("error in location counter expression");
-      return 0;
-    }
+static int precedence(StringRef Op) {
+  return StringSwitch<int>(Op)
+      .Case("*", 4)
+      .Case("/", 3)
+      .Case("+", 2)
+      .Case("-", 2)
+      .Case("&", 1)
+      .Default(-1);
+}
+
+static StringRef next(ArrayRef<StringRef> &Tokens) {
+  if (Tokens.empty()) {
+    error("no next token");
+    return "";
+  }
+  StringRef Tok = Tokens.front();
+  Tokens = Tokens.slice(1);
+  return Tok;
+}
+
+static uint64_t parseExpr(uint64_t Lhs, int MinPrec,
+                          ArrayRef<StringRef> &Tokens, uint64_t Dot);
+
+// This is a part of the operator-precedence parser to evaluate
+// arithmetic expressions in SECTIONS command. This function evaluates an
+// integer literal, a parenthesized expression or the special variable ".".
+static uint64_t parsePrimary(ArrayRef<StringRef> &Tokens, uint64_t Dot) {
+  StringRef Tok = next(Tokens);
+  if (Tok == ".")
+    return Dot;
+  if (Tok == "(") {
+    uint64_t V = parsePrimary(Tokens, Dot);
+    V = parseExpr(V, 0, Tokens, Dot);
+    if (Tokens.empty()) {
+      error(") expected");
+    } else {
+      Tok = next(Tokens);
+      if (Tok != ")")
+        error(") expected, but got " + Tok);
+    }
+    return V;
+  }
+  return getInteger(Tok);
+}
+
+static uint64_t apply(StringRef Op, uint64_t L, uint64_t R) {
+  if (Op == "+")
+    return L + R;
+  if (Op == "-")
+    return L - R;
+  if (Op == "*")
+    return L * R;
+  if (Op == "/") {
+    if (R == 0) {
+      error("division by zero");
+      return 0;
+    }
+    return L / R;
+  }
+  if (Op == "&")
+    return L & R;
+  llvm_unreachable("unknown operator " + Op);
 
-    StringRef Tok = Tokens[I];
-    if (Tok == ".")
-      Result += LocCounter;
-    else
-      Result += getInteger(Tok);
+// This is an operator-precedence parser to evaluate
+// arithmetic expressions in SECTIONS command.
+static uint64_t parseExpr(uint64_t Lhs, int MinPrec,
+                          ArrayRef<StringRef> &Tokens, uint64_t Dot) {
+  while (!Tokens.empty()) {
+    // Read an operator and an expression.
+    StringRef Op1 = Tokens.front();
+    if (precedence(Op1) < MinPrec)
+      return Lhs;
+    next(Tokens);
+    uint64_t Rhs = parsePrimary(Tokens, Dot);
+
+    // Evaluate the remaining part of the expression first if the
+    // next operator has greater precedence than the previous one.
+    // For example, if we have read "+" and "3", and if the next
+    // operator is "*", then we'll evaluate 3 * ... part first.
+    while (!Tokens.empty()) {
+      StringRef Op2 = Tokens.front();
+      if (precedence(Op2) <= precedence(Op1))
+        break;
+      Rhs = parseExpr(Rhs, precedence(Op2), Tokens, Dot);
     }
-  return Result;
+
+    Lhs = apply(Op1, Lhs, Rhs);
+  }
+  return Lhs;
+}
+
+// Evaluates the expression given by list of tokens.
+uint64_t evaluate(ArrayRef<StringRef> Tokens, uint64_t Dot) {
+  uint64_t V = parsePrimary(Tokens, Dot);
+  V = parseExpr(V, 0, Tokens, Dot);
+  if (!Tokens.empty())
+    error("stray token: " + Tokens[0]);
+  return V;
 }
 
 template <class ELFT>
 SectionRule *LinkerScript::find(InputSectionBase<ELFT> *S) {
   for (SectionRule &R : Sections)
     if (R.match(S))
       return &R;
   return nullptr;

lld/trunk/test/ELF/linkerscript-locationcounter.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 # RUN: echo "SECTIONS { \
-# RUN:  . = 0x12341; \
-# RUN:  .data : { *(.data) } \
-# RUN:  . = . + 0x10000; \
-# RUN:  .text : { *(.text) } \
+# RUN:  . = 0xFFF0; \
+# RUN:  . = . + 0x10; \
+# RUN:  .plus : { *(.plus) } \
+# RUN:  . = 0x11010 - 0x10; \
+# RUN:  .minus : { *(.minus) } \
+# RUN:  . = 0x24000 / 0x2; \
+# RUN:  .div : { *(.div) } \
+# RUN:  . = 0x11000 + 0x1000 * 0x2; \
+# RUN:  .mul : { *(.mul) } \
+# RUN:  . = 0x10000 + (0x1000 + 0x1000) * 0x2; \
+# RUN:  .bracket : { *(.bracket) } \
+# RUN:  . = 0x17000 & 0x15000; \
+# RUN:  .and : { *(.and) } \
 # RUN: }" > %t.script
-
 # RUN: ld.lld %t --script %t.script -o %t2
 # RUN: llvm-readobj -s %t2 | FileCheck %s
 
-# CHECK:      Sections [
-# CHECK-NEXT:   Section {
-# CHECK-NEXT:     Index: 0
-# CHECK-NEXT:     Name:  (0)
-# CHECK-NEXT:     Type: SHT_NULL
-# CHECK-NEXT:     Flags [
-# CHECK-NEXT:     ]
-# CHECK-NEXT:     Address: 0x0
-# CHECK-NEXT:     Offset: 0x0
-# CHECK-NEXT:     Size: 0
-# CHECK-NEXT:     Link: 0
-# CHECK-NEXT:     Info: 0
-# CHECK-NEXT:     AddressAlignment: 0
-# CHECK-NEXT:     EntrySize: 0
-# CHECK-NEXT:   }
-# CHECK-NEXT:   Section {
-# CHECK-NEXT:     Index: 1
-# CHECK-NEXT:     Name: .data
-# CHECK-NEXT:     Type: SHT_PROGBITS
-# CHECK-NEXT:     Flags [
-# CHECK-NEXT:       SHF_ALLOC
-# CHECK-NEXT:       SHF_WRITE
-# CHECK-NEXT:     ]
-# CHECK-NEXT:     Address: 0x12341
-# CHECK-NEXT:     Offset: 0x158
-# CHECK-NEXT:     Size: 8
-# CHECK-NEXT:     Link: 0
-# CHECK-NEXT:     Info: 0
-# CHECK-NEXT:     AddressAlignment: 1
-# CHECK-NEXT:     EntrySize: 0
-# CHECK-NEXT:   }
-# CHECK-NEXT:   Section {
-# CHECK-NEXT:     Index: 2
-# CHECK-NEXT:     Name: .text
-# CHECK-NEXT:     Type: SHT_PROGBITS
-# CHECK-NEXT:     Flags [
-# CHECK-NEXT:       SHF_ALLOC
-# CHECK-NEXT:       SHF_EXECINSTR
-# CHECK-NEXT:     ]
-# CHECK-NEXT:     Address: 0x2234C
-# CHECK-NEXT:     Offset: 0x160
-# CHECK-NEXT:     Size: 1
-# CHECK-NEXT:     Link: 0
-# CHECK-NEXT:     Info: 0
-# CHECK-NEXT:     AddressAlignment: 4
-# CHECK-NEXT:     EntrySize: 0
-# CHECK-NEXT:   }
+# CHECK: Section {
+# CHECK:   Index: 1
+# CHECK:   Name: .plus
+# CHECK-NEXT:   Type: SHT_PROGBITS
+# CHECK-NEXT:   Flags [
+# CHECK-NEXT:     SHF_ALLOC
+# CHECK-NEXT:   ]
+# CHECK-NEXT:   Address: 0x10000
+# CHECK-NEXT:   Offset:
+# CHECK-NEXT:   Size:
+# CHECK-NEXT:   Link:
+# CHECK-NEXT:   Info:
+# CHECK-NEXT:   AddressAlignment:
+# CHECK-NEXT:   EntrySize:
+# CHECK-NEXT: }
+# CHECK-NEXT: Section {
+# CHECK-NEXT:   Index: 2
+# CHECK-NEXT:   Name: .minus
+# CHECK-NEXT:   Type: SHT_PROGBITS
+# CHECK-NEXT:   Flags [
+# CHECK-NEXT:     SHF_ALLOC
+# CHECK-NEXT:   ]
+# CHECK-NEXT:   Address: 0x11000
+# CHECK-NEXT:   Offset:
+# CHECK-NEXT:   Size:
+# CHECK-NEXT:   Link:
+# CHECK-NEXT:   Info:
+# CHECK-NEXT:   AddressAlignment:
+# CHECK-NEXT:   EntrySize:
+# CHECK-NEXT: }
+# CHECK-NEXT: Section {
+# CHECK-NEXT:   Index: 3
+# CHECK-NEXT:   Name: .div
+# CHECK-NEXT:   Type: SHT_PROGBITS
+# CHECK-NEXT:   Flags [
+# CHECK-NEXT:     SHF_ALLOC
+# CHECK-NEXT:   ]
+# CHECK-NEXT:   Address: 0x12000
+# CHECK-NEXT:   Offset:
+# CHECK-NEXT:   Size:
+# CHECK-NEXT:   Link:
+# CHECK-NEXT:   Info:
+# CHECK-NEXT:   AddressAlignment:
+# CHECK-NEXT:   EntrySize:
+# CHECK-NEXT: }
+# CHECK-NEXT: Section {
+# CHECK-NEXT:   Index: 4
+# CHECK-NEXT:   Name: .mul
+# CHECK-NEXT:   Type: SHT_PROGBITS
+# CHECK-NEXT:   Flags [
+# CHECK-NEXT:     SHF_ALLOC
+# CHECK-NEXT:   ]
+# CHECK-NEXT:   Address: 0x13000
+# CHECK-NEXT:   Offset:
+# CHECK-NEXT:   Size:
+# CHECK-NEXT:   Link:
+# CHECK-NEXT:   Info:
+# CHECK-NEXT:   AddressAlignment:
+# CHECK-NEXT:   EntrySize:
+# CHECK-NEXT: }
+# CHECK-NEXT: Section {
+# CHECK-NEXT:   Index: 5
+# CHECK-NEXT:   Name: .bracket
+# CHECK-NEXT:   Type: SHT_PROGBITS
+# CHECK-NEXT:   Flags [
+# CHECK-NEXT:     SHF_ALLOC
+# CHECK-NEXT:   ]
+# CHECK-NEXT:   Address: 0x14000
+# CHECK-NEXT:   Offset:
+# CHECK-NEXT:   Size:
+# CHECK-NEXT:   Link:
+# CHECK-NEXT:   Info:
+# CHECK-NEXT:   AddressAlignment:
+# CHECK-NEXT:   EntrySize:
+# CHECK-NEXT: }
+# CHECK-NEXT: Section {
+# CHECK-NEXT:   Index:
+# CHECK-NEXT:   Name: .and
+# CHECK-NEXT:   Type: SHT_PROGBITS
+# CHECK-NEXT:   Flags [
+# CHECK-NEXT:     SHF_ALLOC
+# CHECK-NEXT:   ]
+# CHECK-NEXT:   Address: 0x15000
+# CHECK-NEXT:   Offset:
+# CHECK-NEXT:   Size:
+# CHECK-NEXT:   Link:
+# CHECK-NEXT:   Info:
+# CHECK-NEXT:   AddressAlignment:
+# CHECK-NEXT:   EntrySize:
+# CHECK-NEXT: }
 
+## Mailformed number error.
 # RUN: echo "SECTIONS { \
 # RUN:  . = 0x12Q41; \
 # RUN: }" > %t.script
 # RUN: not ld.lld %t --script %t.script -o %t2 2>&1 | \
 # RUN:  FileCheck --check-prefix=NUMERR %s
 # NUMERR: malformed number: 0x12Q41
 
+## Missing closing bracket.
+# RUN: echo "SECTIONS { \
+# RUN:  . = 0x10000 + (0x1000 + 0x1000 * 0x2; \
+# RUN: }" > %t.script
+# RUN: not ld.lld %t --script %t.script -o %t2 2>&1 | \
+# RUN:  FileCheck --check-prefix=BRACKETERR %s
+# BRACKETERR: ) expected
+
+## Missing opening bracket.
+# RUN: echo "SECTIONS { \
+# RUN:  . = 0x10000 + 0x1000 + 0x1000) * 0x2; \
+# RUN: }" > %t.script
+# RUN: not ld.lld %t --script %t.script -o %t2 2>&1 | \
+# RUN:  FileCheck --check-prefix=BRACKETERR2 %s
+# BRACKETERR2: stray token: )
+
+## Empty expression.
+# RUN: echo "SECTIONS { \
+# RUN:  . = ; \
+# RUN: }" > %t.script
+# RUN: not ld.lld %t --script %t.script -o %t2 2>&1 | \
+# RUN:  FileCheck --check-prefix=ERREXPR %s
+# ERREXPR: error in location counter expression
+
+## Div by zero error.
+# RUN: echo "SECTIONS { \
+# RUN:  . = 0x10000 / 0x0; \
+# RUN: }" > %t.script
+# RUN: not ld.lld %t --script %t.script -o %t2 2>&1 | \
+# RUN:  FileCheck --check-prefix=DIVZERO %s
+# DIVZERO: division by zero
+
 .globl _start;
 _start:
 nop
 
-.section .data
+.section .plus, "a"
+.quad 0
+
+.section .minus, "a"
+.quad 0
+
+.section .div, "a"
 .quad 0
 
+.section .mul, "a"
+.quad 0
+
+.section .bracket, "a"
+.quad 0
+
+.section .and, "a"
+.quad 0