Index: lld/trunk/ELF/LinkerScript.h =================================================================== --- lld/trunk/ELF/LinkerScript.h +++ lld/trunk/ELF/LinkerScript.h @@ -16,6 +16,7 @@ #include "llvm/ADT/MapVector.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/MemoryBuffer.h" +#include namespace lld { namespace elf { @@ -23,6 +24,8 @@ template class OutputSectionBase; template class OutputSectionFactory; +typedef std::function Expr; + // Parses a linker script. Calling this function updates // Config and ScriptConfig. void readLinkerScript(MemoryBufferRef MB); @@ -46,11 +49,11 @@ }; struct SymbolAssignment : BaseCommand { - SymbolAssignment(StringRef Name, std::vector &Expr) - : BaseCommand(AssignmentKind), Name(Name), Expr(std::move(Expr)) {} + SymbolAssignment(StringRef Name, Expr E) + : BaseCommand(AssignmentKind), Name(Name), Expression(E) {} static bool classof(const BaseCommand *C); StringRef Name; - std::vector Expr; + Expr Expression; bool Provide = false; // Hidden and Ignore can be true, only if Provide is true bool Hidden = false; Index: lld/trunk/ELF/LinkerScript.cpp =================================================================== --- lld/trunk/ELF/LinkerScript.cpp +++ lld/trunk/ELF/LinkerScript.cpp @@ -55,188 +55,6 @@ 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 &Tokens, uint64_t Dot) - : ScriptParserBase(Tokens), Dot(Dot) {} - - uint64_t run(); - -private: - uint64_t parsePrimary(); - uint64_t parseTernary(uint64_t Cond); - uint64_t apply(StringRef Op, uint64_t L, uint64_t R); - uint64_t parseExpr1(uint64_t Lhs, int MinPrec); - uint64_t parseExpr(); - - uint64_t Dot; -}; -} - -static int precedence(StringRef Op) { - return StringSwitch(Op) - .Case("*", 4) - .Case("/", 4) - .Case("+", 3) - .Case("-", 3) - .Case("<", 2) - .Case(">", 2) - .Case(">=", 2) - .Case("<=", 2) - .Case("==", 2) - .Case("!=", 2) - .Case("&", 1) - .Default(-1); -} - -static uint64_t evalExpr(std::vector &Tokens, uint64_t Dot) { - return ExprParser(Tokens, Dot).run(); -} - -uint64_t ExprParser::run() { - uint64_t V = parseExpr(); - if (!atEOF() && !Error) - setError("stray token: " + peek()); - return V; -} - -uint64_t static getConstantValue(StringRef C) { - if (C == "COMMONPAGESIZE" || C == "MAXPAGESIZE") - return Target->PageSize; - error("unknown constant: " + C); - return 0; -} - -// 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, the ALIGN function, -// or the special variable ".". -uint64_t ExprParser::parsePrimary() { - StringRef Tok = next(); - if (Tok == ".") - return Dot; - if (Tok == "(") { - uint64_t V = parseExpr(); - expect(")"); - return V; - } - if (Tok == "ALIGN") { - expect("("); - uint64_t V = parseExpr(); - expect(")"); - return alignTo(Dot, V); - } - if (Tok == "CONSTANT") { - expect("("); - uint64_t V = getConstantValue(next()); - expect(")"); - return V; - } - // Documentations says there are two ways to compute - // the value of DATA_SEGMENT_ALIGN command, depending on whether the second - // uses fewer COMMONPAGESIZE sized pages for the data segment(area between the - // result of this expression and `DATA_SEGMENT_END') than the first or not. - // That is possible optimization, that we do not support, so we compute that - // function always as (ALIGN(MAXPAGESIZE) + (. & (MAXPAGESIZE - 1))) now. - if (Tok == "DATA_SEGMENT_ALIGN") { - expect("("); - uint64_t L = parseExpr(); - expect(","); - parseExpr(); - expect(")"); - return alignTo(Dot, L) + (Dot & (L - 1)); - } - // Since we do not support the optimization from comment above, - // we can just ignore that command. - if (Tok == "DATA_SEGMENT_END") { - expect("("); - expect("."); - expect(")"); - return Dot; - } - uint64_t V = 0; - if (Tok.getAsInteger(0, V)) - setError("malformed number: " + Tok); - return V; -} - -uint64_t ExprParser::parseTernary(uint64_t Cond) { - next(); - uint64_t V = parseExpr(); - expect(":"); - uint64_t W = parseExpr(); - return Cond ? V : W; -} - -uint64_t ExprParser::apply(StringRef Op, uint64_t L, uint64_t 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; - if (Op == "-") - return L - R; - if (Op == "<") - return L < R; - if (Op == ">") - return L > R; - if (Op == ">=") - return L >= R; - if (Op == "<=") - return L <= R; - if (Op == "==") - return L == R; - if (Op == "!=") - return L != R; - if (Op == "&") - return L & R; - llvm_unreachable("invalid operator"); -} - -// This is a part of the operator-precedence parser. -// This function assumes that the remaining token stream starts -// with an operator. -uint64_t ExprParser::parseExpr1(uint64_t Lhs, int MinPrec) { - while (!atEOF()) { - // Read an operator and an expression. - StringRef Op1 = peek(); - if (Op1 == "?") - return parseTernary(Lhs); - if (precedence(Op1) < MinPrec) - return Lhs; - next(); - uint64_t Rhs = parsePrimary(); - - // 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 (!atEOF()) { - StringRef Op2 = peek(); - if (precedence(Op2) <= precedence(Op1)) - break; - Rhs = parseExpr1(Rhs, precedence(Op2)); - } - - Lhs = apply(Op1, Lhs, Rhs); - } - return Lhs; -} - -// Reads and evaluates an arithmetic expression. -uint64_t ExprParser::parseExpr() { return parseExpr1(parsePrimary(), 0); } - template static bool isDiscarded(InputSectionBase *S) { return !S || !S->Live; } @@ -334,7 +152,7 @@ template void LinkerScript::dispatchAssignment(SymbolAssignment *Cmd) { - uint64_t Val = evalExpr(Cmd->Expr, Dot); + uint64_t Val = Cmd->Expression(Dot); if (Cmd->Name == ".") { Dot = Val; } else if (!Cmd->Ignore) { @@ -597,13 +415,18 @@ void readSearchDir(); void readSections(); - void readLocationCounterValue(); + void readAssignment(); void readOutputSectionDescription(StringRef OutSec); std::vector readOutputSectionPhdrs(); unsigned readPhdrType(); void readProvide(bool Hidden); SymbolAssignment *readSymbolAssignment(StringRef Name); - std::vector readSectionsCommandExpr(); + + Expr readExpr(); + Expr readExpr1(Expr Lhs, int MinPrec); + Expr readPrimary(); + Expr readTernary(Expr Cond); + Expr combine(StringRef Op, Expr Lhs, Expr Rhs); const static StringMap Cmd; ScriptConfiguration &Opt = *ScriptConfig; @@ -795,29 +618,45 @@ while (!Error && !skip("}")) { StringRef Tok = peek(); if (Tok == ".") { - readLocationCounterValue(); + readAssignment(); continue; } next(); - if (Tok == "PROVIDE") + if (Tok == "PROVIDE") { readProvide(false); - else if (Tok == "PROVIDE_HIDDEN") + } else if (Tok == "PROVIDE_HIDDEN") { readProvide(true); - else if (peek() == "=") + } else if (peek() == "=") { readSymbolAssignment(Tok); - else + expect(";"); + } else { readOutputSectionDescription(Tok); + } } } -void ScriptParser::readLocationCounterValue() { +static int precedence(StringRef Op) { + return StringSwitch(Op) + .Case("*", 4) + .Case("/", 4) + .Case("+", 3) + .Case("-", 3) + .Case("<", 2) + .Case(">", 2) + .Case(">=", 2) + .Case("<=", 2) + .Case("==", 2) + .Case("!=", 2) + .Case("&", 1) + .Default(-1); +} + +void ScriptParser::readAssignment() { expect("."); expect("="); - std::vector Expr = readSectionsCommandExpr(); - if (Expr.empty()) - error("error in location counter expression"); - else - Opt.Commands.push_back(llvm::make_unique(".", Expr)); + Expr E = readExpr(); + expect(";"); + Opt.Commands.push_back(llvm::make_unique(".", E)); } void ScriptParser::readOutputSectionDescription(StringRef OutSec) { @@ -881,35 +720,142 @@ SymbolAssignment *ScriptParser::readSymbolAssignment(StringRef Name) { expect("="); - std::vector Expr = readSectionsCommandExpr(); - if (Expr.empty()) { - error("error in symbol assignment expression"); - } else { - Opt.Commands.push_back(llvm::make_unique(Name, Expr)); - return static_cast(Opt.Commands.back().get()); - } - return nullptr; + Expr E = readExpr(); + Opt.Commands.push_back(llvm::make_unique(Name, E)); + return static_cast(Opt.Commands.back().get()); } -// This function reads balanced expression until semicolon is seen. -std::vector ScriptParser::readSectionsCommandExpr() { - int Braces = 0; - std::vector Expr; - while (!Error) { - StringRef Tok = peek(); +// This is an operator-precedence parser to parse a linker +// script expression. +Expr ScriptParser::readExpr() { return readExpr1(readPrimary(), 0); } + +// This is a part of the operator-precedence parser. This function +// assumes that the remaining token stream starts with an operator. +Expr ScriptParser::readExpr1(Expr Lhs, int MinPrec) { + while (!atEOF() && !Error) { + // Read an operator and an expression. + StringRef Op1 = peek(); + if (Op1 == "?") + return readTernary(Lhs); + if (precedence(Op1) < MinPrec) + break; + next(); + Expr Rhs = readPrimary(); - if (Tok == "(") - Braces++; - else if (Tok == ")") - if (--Braces < 0) + // 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 (!atEOF()) { + StringRef Op2 = peek(); + if (precedence(Op2) <= precedence(Op1)) break; + Rhs = readExpr1(Rhs, precedence(Op2)); + } - next(); - if (Tok == ";") - break; - Expr.push_back(Tok); + Lhs = combine(Op1, Lhs, Rhs); + } + return Lhs; +} + +uint64_t static getConstant(StringRef S) { + if (S == "COMMONPAGESIZE" || S == "MAXPAGESIZE") + return Target->PageSize; + error("unknown constant: " + S); + return 0; +} + +Expr ScriptParser::readPrimary() { + StringRef Tok = next(); + + if (Tok == ".") + return [](uint64_t Dot) { return Dot; }; + + if (Tok == "(") { + Expr E = readExpr(); + expect(")"); + return E; + } + + // Built-in functions are parsed here. + // https://sourceware.org/binutils/docs/ld/Builtin-Functions.html. + if (Tok == "ALIGN") { + expect("("); + Expr E = readExpr(); + expect(")"); + return [=](uint64_t Dot) { return alignTo(Dot, E(Dot)); }; + } + if (Tok == "CONSTANT") { + expect("("); + StringRef Tok = next(); + expect(")"); + return [=](uint64_t Dot) { return getConstant(Tok); }; + } + if (Tok == "DATA_SEGMENT_ALIGN") { + expect("("); + Expr E = readExpr(); + expect(","); + readExpr(); + expect(")"); + return [=](uint64_t Dot) -> uint64_t { + uint64_t Val = E(Dot); + return alignTo(Dot, Val) + (Dot & (Val - 1)); + }; + } + if (Tok == "DATA_SEGMENT_END") { + expect("("); + expect("."); + expect(")"); + return [](uint64_t Dot) { return Dot; }; } - return Expr; + + // Parse a number literal + uint64_t V = 0; + if (Tok.getAsInteger(0, V)) + setError("malformed number: " + Tok); + return [=](uint64_t Dot) { return V; }; +} + +Expr ScriptParser::readTernary(Expr Cond) { + next(); + Expr L = readExpr(); + expect(":"); + Expr R = readExpr(); + return [=](uint64_t Dot) { return Cond(Dot) ? L(Dot) : R(Dot); }; +} + +Expr ScriptParser::combine(StringRef Op, Expr L, Expr R) { + if (Op == "*") + return [=](uint64_t Dot) { return L(Dot) * R(Dot); }; + if (Op == "/") { + return [=](uint64_t Dot) -> uint64_t { + uint64_t RHS = R(Dot); + if (RHS == 0) { + error("division by zero"); + return 0; + } + return L(Dot) / RHS; + }; + } + if (Op == "+") + return [=](uint64_t Dot) { return L(Dot) + R(Dot); }; + if (Op == "-") + return [=](uint64_t Dot) { return L(Dot) - R(Dot); }; + if (Op == "<") + return [=](uint64_t Dot) { return L(Dot) < R(Dot); }; + if (Op == ">") + return [=](uint64_t Dot) { return L(Dot) > R(Dot); }; + if (Op == ">=") + return [=](uint64_t Dot) { return L(Dot) >= R(Dot); }; + if (Op == "<=") + return [=](uint64_t Dot) { return L(Dot) <= R(Dot); }; + if (Op == "==") + return [=](uint64_t Dot) { return L(Dot) == R(Dot); }; + if (Op == "!=") + return [=](uint64_t Dot) { return L(Dot) != R(Dot); }; + if (Op == "&") + return [=](uint64_t Dot) { return L(Dot) & R(Dot); }; + llvm_unreachable("invalid operator"); } std::vector ScriptParser::readOutputSectionPhdrs() { Index: lld/trunk/test/ELF/linkerscript-locationcounter.s =================================================================== --- lld/trunk/test/ELF/linkerscript-locationcounter.s +++ lld/trunk/test/ELF/linkerscript-locationcounter.s @@ -311,7 +311,7 @@ # RUN: }" > %t.script # RUN: not ld.lld %t --script %t.script -o %t2 2>&1 | \ # RUN: FileCheck --check-prefix=BRACKETERR %s -# BRACKETERR: unexpected EOF +# BRACKETERR: ) expected, but got ; ## Missing opening bracket. # RUN: echo "SECTIONS { \ @@ -319,7 +319,7 @@ # RUN: }" > %t.script # RUN: not ld.lld %t --script %t.script -o %t2 2>&1 | \ # RUN: FileCheck --check-prefix=BRACKETERR2 %s -# BRACKETERR2: expected, but got * +# BRACKETERR2: ; expected, but got ) ## Empty expression. # RUN: echo "SECTIONS { \ @@ -327,7 +327,7 @@ # 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 +# ERREXPR: malformed number: ; ## Div by zero error. # RUN: echo "SECTIONS { \ @@ -343,7 +343,7 @@ # RUN: }" > %t.script # RUN: not ld.lld %t --script %t.script -o %t2 2>&1 | \ # RUN: FileCheck --check-prefix=TERNERR %s -# TERNERR: unexpected EOF +# TERNERR: : expected, but got ; .globl _start _start: