[ELF] - implemented ternary operator for linkerscript expressions

[grimar]

Summary

Patch implements ternary operator for linkerscript expressions.
Like:

SECTIONS {
 . = 0x1 ? 0x2 : 0x3;
...
}

[davide]

I have a question (mostly, curiosity). Are you trying to support enough to correctly parse a given linker script (e.g. Linux/FreeBSD kernel) or you're picking features according to some other criterion?

Cheers,

[ruiu]

ELF/LinkerScript.cpp

94–104 ↗

(On Diff #54387)

Please sync after r266912. I defined expect and redefined readExpr. Now you can write this as

next(Tokens);
uint64_t V = parseExpr(Tokens, Dot);
if (expect(Tokens, ":")
  return 0;
uint64_t W = parseExpr(Tokens, Dot);
return Cond ? V : W;

[grimar]

In D19332#406689, @davide wrote:

I have a question (mostly, curiosity). Are you trying to support enough to correctly parse a given linker script (e.g. Linux/FreeBSD kernel) or you're picking features according to some other criterion?

Cheers,

I am using bsd script as reference (https://svnweb.freebsd.org/base/head/sys/conf/ldscript.amd64?view=markup), so I am trying to support features it uses, assuming that it is reasonable subset.

[grimar]

• Rebased

[ruiu]

LGTM with a nit.

ELF/LinkerScript.cpp

138 ↗

(On Diff #54472)

Swap Tokens and Lhs so that the order matches with parseExpr1.

[grimar]

ELF/LinkerScript.cpp

138 ↗

(On Diff #54472)

r267086 changed signature to:

uint64_t LinkerScript<ELFT>::parseExpr1(ArrayRef<StringRef> &Tokens,
                                        uint64_t Lhs, int MinPrec) {

So leaved without changes the order.
But I made it a member of class and changed signature to:

uint64_t LinkerScript<ELFT>::parseTernary(ArrayRef<StringRef> &Tokens, uint64_t Cond)

(to match latest changes about Dot)

lld/trunk/ELF/LinkerScript.h

private:
   ScriptConfiguration &Opt = *ScriptConfig;
 
   int getSectionIndex(StringRef Name);
 
   uint64_t evaluate(ArrayRef<StringRef> Tokens);
   uint64_t parseExpr(ArrayRef<StringRef> &Tokens);
   uint64_t parsePrimary(ArrayRef<StringRef> &Tokens);
   uint64_t parseExpr1(ArrayRef<StringRef> &Tokens, uint64_t Lhs, int MinPrec);
+  uint64_t parseTernary(ArrayRef<StringRef> &Tokens, uint64_t Cond);
   typename ELFT::uint Dot;
 };
 
 // Variable template is a C++14 feature, so we can't template
 // a global variable. Use a struct to workaround.
 template <class ELFT> struct Script { static LinkerScript<ELFT> *X; };
 template <class ELFT> LinkerScript<ELFT> *Script<ELFT>::X;
 
 } // namespace elf
 } // namespace lld
 
 #endif

lld/trunk/ELF/LinkerScript.cpp

if (Tok == "(") {
     uint64_t V = parseExpr(Tokens);
     if (!expect(Tokens, ")"))
       return 0;
     return V;
   }
   return getInteger(Tok);
 }
 
+template <class ELFT>
+uint64_t LinkerScript<ELFT>::parseTernary(ArrayRef<StringRef> &Tokens,
+                                          uint64_t Cond) {
+  next(Tokens);
+  uint64_t V = parseExpr(Tokens, Dot);
+  if (!expect(Tokens, ":"))
+    return 0;
+  uint64_t W = parseExpr(Tokens, Dot);
+  return Cond ? V : W;
+}
+
 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 == "/") {

 // arithmetic expressions in SECTIONS command.
 // Tokens should start with an operator.
 template <class ELFT>
 uint64_t LinkerScript<ELFT>::parseExpr1(ArrayRef<StringRef> &Tokens,
                                         uint64_t Lhs, int MinPrec) {
   while (!Tokens.empty()) {
     // Read an operator and an expression.
     StringRef Op1 = Tokens.front();
+    if (Op1 == "?")
+      return parseTernary(Tokens, Lhs, Dot);
+
     if (precedence(Op1) < MinPrec)
       return Lhs;
     next(Tokens);
     uint64_t Rhs = parsePrimary(Tokens);
 
     // 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

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:  . = 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:  . = 0x1 ? 0x16000 : 0x999999; \
+# RUN:  .ternary1 : { *(.ternary1) } \
+# RUN:  . = 0x0 ? 0x999999 : 0x17000; \
+# RUN:  .ternary2 : { *(.ternary2) } \
 # RUN: }" > %t.script
 # RUN: ld.lld %t --script %t.script -o %t2
 # RUN: llvm-readobj -s %t2 | FileCheck %s
 
 # CHECK: Section {
 # CHECK:   Index: 1
 # CHECK:   Name: .plus
 # CHECK-NEXT:   Type: SHT_PROGBITS

 # CHECK-NEXT:   Address: 0x15000
 # 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: .ternary1
+# CHECK-NEXT:   Type: SHT_PROGBITS
+# CHECK-NEXT:   Flags [
+# CHECK-NEXT:     SHF_ALLOC
+# CHECK-NEXT:   ]
+# CHECK-NEXT:   Address: 0x16000
+# 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: .ternary2
+# CHECK-NEXT:   Type: SHT_PROGBITS
+# CHECK-NEXT:   Flags [
+# CHECK-NEXT:     SHF_ALLOC
+# CHECK-NEXT:   ]
+# CHECK-NEXT:   Address: 0x17000
+# 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

 ## 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
 
+## Broken ternary operator expression.
+# RUN: echo "SECTIONS { \
+# RUN:  . = 0x1 ? 0x2; \
+# RUN: }" > %t.script
+# RUN: not ld.lld %t --script %t.script -o %t2 2>&1 | \
+# RUN:  FileCheck --check-prefix=TERNERR %s
+# TERNERR: : expected
+
 .globl _start;
 _start:
 nop
 
 .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
+
+.section .ternary1, "a"
+.quad 0
+
+.section .ternary2, "a"
+.quad 0