Index: lld/trunk/ELF/LinkerScript.h =================================================================== --- lld/trunk/ELF/LinkerScript.h +++ lld/trunk/ELF/LinkerScript.h @@ -72,7 +72,6 @@ bool DoLayout = false; private: - uint64_t evaluate(std::vector &Tokens, uint64_t LocCounter); template SectionRule *find(InputSectionBase *S); // SECTIONS commands. Index: lld/trunk/ELF/LinkerScript.cpp =================================================================== --- lld/trunk/ELF/LinkerScript.cpp +++ lld/trunk/ELF/LinkerScript.cpp @@ -20,6 +20,7 @@ #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" @@ -43,27 +44,106 @@ return V; } -// Evaluates the expression given by list of tokens. -uint64_t LinkerScript::evaluate(std::vector &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"); +static int precedence(StringRef Op) { + return StringSwitch(Op) + .Case("*", 4) + .Case("/", 3) + .Case("+", 2) + .Case("-", 2) + .Case("&", 1) + .Default(-1); +} + +static StringRef next(ArrayRef &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 &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 &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); + return 0; +} + +// This is an operator-precedence parser to evaluate +// arithmetic expressions in SECTIONS command. +static uint64_t parseExpr(uint64_t Lhs, int MinPrec, + ArrayRef &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); + } - StringRef Tok = Tokens[I]; - if (Tok == ".") - Result += LocCounter; - else - Result += getInteger(Tok); + Lhs = apply(Op1, Lhs, Rhs); } - return Result; + return Lhs; +} + +// Evaluates the expression given by list of tokens. +uint64_t evaluate(ArrayRef 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 Index: lld/trunk/test/ELF/linkerscript-locationcounter.s =================================================================== --- lld/trunk/test/ELF/linkerscript-locationcounter.s +++ lld/trunk/test/ELF/linkerscript-locationcounter.s @@ -1,63 +1,115 @@ # 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 @@ -65,10 +117,56 @@ # 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