Index: ELF/LinkerScript.cpp =================================================================== --- ELF/LinkerScript.cpp +++ ELF/LinkerScript.cpp @@ -21,11 +21,246 @@ #include "llvm/Support/Path.h" #include "llvm/Support/StringSaver.h" +#include + using namespace llvm; using namespace lld; using namespace lld::elf2; namespace { +class ExpressionEvaluator { +public: + // Evaluates the expression given by list of tokens. Fills the Out + // with value of expression if succeded. Returns false on error. + bool evaluate(std::list &Tokens, int64_t *Out = nullptr) { + std::list RPN = buildRPN(Tokens); + std::list Stack; + std::list Temps; + + // Pushes integer value to stack. + auto PushStackVal = [&](int64_t Val) { + Temps.emplace_back(std::to_string(Val)); + Stack.push_back(Temps.back()); + }; + + // Checks that value is a valid integer + // or declared variable. + auto CheckDecl = [this](StringRef V) { + getValue(V); + return !HasError; + }; + + // Assigns result to values list and optional out variable. + // Returns true as assignment operation always means result. + auto AssignResultOp = [&](StringRef N, int64_t Val) { + Values[N] = Val; + if (Out) + *Out = Val; + return true; + }; + + // Tries to perform division operation. If returns true that means we + // have error result and do not need to continue. + auto DivOp = [this, PushStackVal](StringRef Arg1, StringRef Arg2) { + int64_t Val = getValue(Arg2); + if (!Val) { + error("Division by zero"); + return true; + } + PushStackVal(getValue(Arg1) / Val); + return false; + }; + + for (StringRef Op : RPN) { + if (!isOperator(Op)) { + Stack.push_back(Op); + continue; + } + + StringRef Arg2 = *std::prev(Stack.end(), 1); + StringRef Arg1 = *std::prev(Stack.end(), 2); + Stack.erase(std::prev(Stack.end(), 2), Stack.end()); + + // If this is not assignment we check that both + // operands are declared variables or a valid values. + if (Op != "=") + if (!CheckDecl(Arg1) || !CheckDecl(Arg2)) + return false; + + bool HaveResult = false; + if (Op == "=") + HaveResult = AssignResultOp(Arg1, toInteger(Arg2)); + else if (Op == "-=") + HaveResult = AssignResultOp(Arg1, getValue(Arg1) - toInteger(Arg2)); + else if (Op == "+=") + HaveResult = AssignResultOp(Arg1, getValue(Arg1) + toInteger(Arg2)); + else if (Op == "*=") + HaveResult = AssignResultOp(Arg1, getValue(Arg1) * toInteger(Arg2)); + else if (Op == "/=") + HaveResult = DivOp(Arg1, Arg2) + ? true + : AssignResultOp(Arg1, toInteger(Stack.back())); + else if (Op == "<<=") + HaveResult = AssignResultOp(Arg1, getValue(Arg1) << toInteger(Arg2)); + else if (Op == ">>=") + HaveResult = AssignResultOp(Arg1, getValue(Arg1) >> toInteger(Arg2)); + else if (Op == "|=") + HaveResult = AssignResultOp(Arg1, getValue(Arg1) | toInteger(Arg2)); + else if (Op == "&=") + HaveResult = AssignResultOp(Arg1, getValue(Arg1) & toInteger(Arg2)); + else if (Op == "+") + PushStackVal(getValue(Arg1) + getValue(Arg2)); + else if (Op == "-") + PushStackVal(getValue(Arg1) - getValue(Arg2)); + else if (Op == "*") + PushStackVal(getValue(Arg1) * getValue(Arg2)); + else if (Op == "/") + HaveResult = DivOp(Arg1, Arg2); + else if (Op == "^") + PushStackVal(pow(getValue(Arg1), getValue(Arg2))); + else if (Op == "<<") + PushStackVal(getValue(Arg1) << getValue(Arg2)); + else if (Op == ">>") + PushStackVal(getValue(Arg1) >> getValue(Arg2)); + else if (Op == "&") + PushStackVal(getValue(Arg1) & getValue(Arg2)); + else if (Op == "|") + PushStackVal(getValue(Arg1) | getValue(Arg2)); + else + assert(false && "Unknown operator"); + + if (HaveResult) + return !HasError; + } + + // If we reach here then that is expression without assignment, for example + // can be met in next statement: ASSERT(x + 5, "..."), where "x + 5" is it. + if (Stack.size() == 1) { + if (Out) + *Out = getValue(Stack.back()); + return !HasError; + } + + return false; + } + + int64_t getValue(StringRef V) { + int64_t Val; + if (!V.getAsInteger(0, Val)) + return Val; + auto I = Values.find(V); + if (I != Values.end()) + return I->second; + error("Undeclared variable " + V); + return 0; + } + +protected: + // Builds Reverse Polish Notation using + // shunting-yard algorithm by Edsger Dijkstra. + // https://en.wikipedia.org/wiki/Shunting-yard_algorithm + std::list buildRPN(std::list &Tokens) { + std::list OutString; + std::list Stack; + int32_t OpenedBrackets = 0; + + for (StringRef Tok : Tokens) { + // If the token is a number, then add it to the output queue. + if (!isOperator(Tok)) { + OutString.push_back(Tok); + continue; + } + + if (isBracket(Tok)) { + // If the token is a left parenthesis, then push it onto the stack. + if (Tok == "(") { + ++OpenedBrackets; + Stack.push_back(Tok); + } else { + // If the token is a right parenthesis: + // Until the token at the top of the stack is a left parenthesis, pop + // operators off the stack onto the output queue. + // Pop the left parenthesis from the stack, but not onto the output + // queue. + --OpenedBrackets; + if (OpenedBrackets < 0) + error("Inconsistent opening/closing bracket"); + while (!Stack.empty()) { + StringRef StackTok = Stack.back(); + Stack.pop_back(); + if (StackTok == "(") + break; + else + OutString.push_back(StackTok); + } + } + continue; + } + + // If the token is an operator, Tok, then: + // while there is an operator token St, at the top of the operator stack: + // if either + // 1) Tok is left associative and its precedence is less than or equal to + // that of St. + // 2) Tok is right associative, and has precedence less than that of St. + // Then pop StackTok off the operator stack, onto the output queue. + // At the end of iteration push Tok onto the operator stack. + auto ExtractStack = [this](StringRef Tok, StringRef StackTok) { + uint8_t Pr = getPriority(Tok); + bool LeftAssoc = isLeftAssoc(Tok); + uint8_t StackPr = getPriority(StackTok); + return (LeftAssoc && Pr <= StackPr) || (!LeftAssoc && Pr < StackPr); + }; + while (!Stack.empty()) { + StringRef St = Stack.back(); + if (ExtractStack(Tok, St)) { + OutString.push_back(St); + Stack.pop_back(); + continue; + } + break; + } + Stack.push_back(Tok); + } + + if (OpenedBrackets > 0) + error("Inconsistent opening/closing bracket"); + + // Add the remaining stack content to output string. + OutString.insert(OutString.end(), Stack.rbegin(), Stack.rend()); + return OutString; + } + + bool isOperator(StringRef O) { return Operators.find(O) != Operators.end(); } + bool isLeftAssoc(StringRef O) { return Operators.find(O)->second.second; } + uint8_t getPriority(StringRef O) { return Operators.find(O)->second.first; } + bool isBracket(StringRef B) { return B == "(" || B == ")"; } + + bool isInteger(StringRef Tok) { + int64_t Val; + return !Tok.getAsInteger(0, Val); + } + + int64_t toInteger(StringRef Tok) { + int64_t Val; + if (Tok.getAsInteger(0, Val)) + error("Integer can't be parsed: " + Tok); + return Val; + } + + // Operator Name->[Rank, IsLeftAssociative] pair. + std::map> Operators = { + {"^", {100, true}}, {"*", {80, true}}, {"/", {80, true}}, + {"+", {50, true}}, {"-", {50, true}}, {"<<", {30, true}}, + {">>", {30, true}}, {"&", {30, true}}, {"|", {30, true}}, + {"(", {20, true}}, {")", {20, true}}, {"=", {0, false}}, + {"+=", {0, false}}, {"-=", {0, false}}, {"*=", {0, false}}, + {"/=", {0, false}}, {"<<=", {0, false}}, {">>=", {0, false}}, + {"&=", {0, false}}, {"|=", {0, false}}}; + + std::map Values; +}; + class LinkerScript { public: LinkerScript(BumpPtrAllocator *A, StringRef S, bool B) @@ -44,7 +279,9 @@ void addFile(StringRef Path); void readAsNeeded(); + void readAssert(); void readEntry(); + bool readExpression(StringRef Tok); void readExtern(); void readGroup(); void readInclude(); @@ -61,6 +298,8 @@ bool Error = false; size_t Pos = 0; bool IsUnderSysroot; + + ExpressionEvaluator Eval; }; } @@ -69,7 +308,9 @@ StringRef Tok = next(); if (Tok == ";") continue; - if (Tok == "ENTRY") { + if (Tok == "ASSERT") { + readAssert(); + } else if (Tok == "ENTRY") { readEntry(); } else if (Tok == "EXTERN") { readExtern(); @@ -88,8 +329,10 @@ } else if (Tok == "SECTIONS") { readSections(); } else { - setError("unknown directive: " + Tok); - return; + if (!readExpression(Tok)) { + setError("unknown directive: " + Tok); + return; + } } } } @@ -125,7 +368,7 @@ // Unquoted token size_t Pos = S.find_first_not_of( "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" - "0123456789_.$/\\~=+[]*?-:"); + "0123456789_.$/\\~=+[]*?-:><|&"); // A character that cannot start a word (which is usually a // punctuation) forms a single character token. if (Pos == 0) @@ -231,6 +474,23 @@ Config->AsNeeded = Orig; } +void LinkerScript::readAssert() { + expect("("); + std::list ExpList; + while (!Error) { + StringRef Tok = next(); + if (Tok == ",") + break; + else + ExpList.push_back(Tok); + } + StringRef Text = next(); + expect(")"); + int64_t Cond; + if (Eval.evaluate(ExpList, &Cond) && !Cond) + error(Text); +} + void LinkerScript::readEntry() { // -e takes predecence over ENTRY(). expect("("); @@ -240,6 +500,19 @@ expect(")"); } +bool LinkerScript::readExpression(StringRef Tok) { + std::list ExpList; + ExpList.push_back(Tok); + while (!Error) { + StringRef Tok = next(); + if (Tok == ";") + break; + else + ExpList.push_back(Tok); + } + return !Error && Eval.evaluate(ExpList); +} + void LinkerScript::readExtern() { expect("("); while (!Error) { Index: test/ELF/linkerscript-expressions.s =================================================================== --- test/ELF/linkerscript-expressions.s +++ test/ELF/linkerscript-expressions.s @@ -0,0 +1,221 @@ +# REQUIRES: x86 +# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t + +## No errors when assert expression is not 0. +# RUN: echo "ASSERT(26, "OK"); \ +# RUN: " > %t.script +# RUN: ld.lld -o %t.out --script %t.script %t +# RUN: llvm-readobj %t.out > /dev/null + +## No errors when assert expression is not 0 +## and variable is used, also checks that +## assignment works. +# RUN: echo "x = 1; \ +# RUN: ASSERT(x, "OK"); \ +# RUN: " > %t.script +# RUN: ld.lld -o %t.out --script %t.script %t +# RUN: llvm-readobj %t.out > /dev/null + +## Error when assert expression is single undeclared variable. +# RUN: echo "ASSERT(undecl, "OK"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=UNDECLARED %s < %t.log +# UNDECLARED: Undeclared variable undecl + +## Error when assert expression is 0, also checks that +## text from assert is valid and customizable. +# RUN: echo "ASSERT(0, \"Custom assert fail text\"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE-CUSTOM %s < %t.log +# FALSE-CUSTOM: Custom assert fail text + +## Error when undeclared variable used. +# RUN: echo "x = 5; \ +# RUN: x = 10 + undecl; \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=UNDECLARED %s < %t.log + +## This check is used below to verify output from assert +## expression when it fails. +# FALSE: false + +## Check operation '+' works as expected. Also checks +## assignment of negative values. +# RUN: echo "x = -100; \ +# RUN: ASSERT(100 + x, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check operation '-' works as expected. +# RUN: echo "x = 100; \ +# RUN: ASSERT(100 - x, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check operation '-' works as expected. +# RUN: echo "x = 100; \ +# RUN: ASSERT(100 - x, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check operation '*' works as expected. +# RUN: echo "x = 10 * 5; \ +# RUN: ASSERT(50 - x - x * 0, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check operation '/' works as expected. +# RUN: echo "x = 10 / 5; \ +# RUN: ASSERT(x - 2, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check operation '^' works as expected. +# RUN: echo "x = 2 ^ 5; \ +# RUN: ASSERT(32 - x, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Division by 0 error +# RUN: echo "x = 10 / 0;" > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=DIV-ZERO %s < %t.log +# DIV-ZERO: Division by zero + +## Error - inconsistent closing bracket +# RUN: echo "x = 10 + 5);" > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=WRONG-BRACKETS %s < %t.log +# WRONG-BRACKETS: Inconsistent opening/closing bracket + +## Error - inconsistent opening bracket +# RUN: echo "x = (10 + 5;" > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=WRONG-BRACKETS %s < %t.log + +## Check ')' and '(' works as expected. +# RUN: echo "x = ((5 + 5) * 5) - 5 * 2 / (5 + 5); \ +# RUN: ASSERT(x - 49, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check '-=' works as expected. +# RUN: echo "x = 5; \ +# RUN: x -= 5; \ +# RUN: ASSERT(x, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check '+=' works as expected. +# RUN: echo "x = -5; \ +# RUN: x += 5; \ +# RUN: ASSERT(x, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check '*=' works as expected. +# RUN: echo "x = 5; \ +# RUN: x *= 5; \ +# RUN: ASSERT(x - 25, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check '/=' works as expected. +# RUN: echo "x = 25; \ +# RUN: x /= 5; \ +# RUN: ASSERT(x - 5, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check '/=' division by 0 error. +# RUN: echo "x = 25; \ +# RUN: x /= 0; \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=DIV-ZERO %s < %t.log + +## Check '<<' works as expected. +# RUN: echo "x = 10 - 2 * 4 << 1; \ +# RUN: ASSERT(x - 4, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check '>>' works as expected. +# RUN: echo "x = 10 - 2 * 4 >> 1; \ +# RUN: ASSERT(x - 1, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check '<<=' works as expected. +# RUN: echo "x = 1; \ +# RUN: x <<= 5; \ +# RUN: ASSERT(x - 32, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check '>>=' works as expected. +# RUN: echo "x = 32; \ +# RUN: x >>= 5; \ +# RUN: ASSERT(x - 1, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check '|=' works as expected. +# RUN: echo "x = 5; \ +# RUN: x |= 8; \ +# RUN: ASSERT(x - 13, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check '&=' works as expected. +# RUN: echo "x = 6; \ +# RUN: x &= 3; \ +# RUN: ASSERT(x - 2, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Check '&' works as expected. +# RUN: echo "x = 5 * 7 & 6; \ +# RUN: ASSERT(x - 2, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +## Complex test with many types of operators, several operands +## and with hex values. +# RUN: echo "x = 1 + 2 * 3 - (4 - 5) ^ 1; \ +# RUN: y = x << 2 & x | 15; \ +# RUN: z = (((x + y) - x) + y) * 2; \ +# RUN: x <<= (y + z / y); \ +# RUN: x >>= (16 & 17); \ +# RUN: x &= 0x7F; \ +# RUN: x /= (0x1278 - 4696); \ +# RUN: c = 1 << 1; \ +# RUN: ASSERT(x - c, "false"); \ +# RUN: " > %t.script +# RUN: not ld.lld -o %t.out --script %t.script %t > %t.log 2>&1 +# RUN: FileCheck -check-prefix=FALSE %s < %t.log + +.globl _start; +_start: + nop Index: test/ELF/linkerscript.s =================================================================== --- test/ELF/linkerscript.s +++ test/ELF/linkerscript.s @@ -104,7 +104,7 @@ # RUN: not ld.lld -o foo %t.script > %t.log 2>&1 # RUN: FileCheck -check-prefix=ERR1 %s < %t.log -# ERR1: unknown directive: FOO +# ERR1: unexpected EOF .globl _start, _label; _start: