Index: include/lld/ReaderWriter/LinkerScript.h =================================================================== --- include/lld/ReaderWriter/LinkerScript.h +++ include/lld/ReaderWriter/LinkerScript.h @@ -34,15 +34,64 @@ unknown, eof, identifier, + number, libname, comma, + colon, + semicolon, l_paren, r_paren, + l_brace, + r_brace, + question, + exclaim, + exclaimequal, + equal, + equalequal, + plus, + plusequal, + minus, + minusequal, + star, + starequal, + slash, + slashequal, + amp, + ampequal, + pipe, + pipeequal, + less, + lessless, + lesslessequal, + greater, + greatergreater, + greatergreaterequal, + lessequal, + greaterequal, kw_entry, kw_group, kw_output_format, kw_output_arch, - kw_as_needed + kw_as_needed, + kw_search_dir, + kw_sections, + kw_hidden, + kw_provide, + kw_provide_hidden, + kw_overlay, + kw_discard, + kw_at, + kw_align, + kw_align_with_input, + kw_subalign, + kw_exclude_file, + kw_sort_by_name, + kw_sort_by_alignment, + kw_sort_by_init_priority, + kw_sort_none, + kw_keep, + kw_only_if_ro, + kw_only_if_rw }; Token() : _kind(unknown) {} @@ -56,8 +105,7 @@ class Lexer { public: - explicit Lexer(std::unique_ptr mb) - : _buffer(mb->getBuffer()) { + explicit Lexer(std::unique_ptr mb) : _buffer(mb->getBuffer()) { _sourceManager.AddNewSourceBuffer(std::move(mb), llvm::SMLoc()); } @@ -66,6 +114,8 @@ const llvm::SourceMgr &getSourceMgr() const { return _sourceManager; } private: + bool canStartNumber(char c) const; + bool canContinueNumber(char c) const; bool canStartName(char c) const; bool canContinueName(char c) const; void skipWhitespace(); @@ -77,9 +127,35 @@ llvm::SourceMgr _sourceManager; }; +/// All linker scripts commands derive from this class. High-level, sections and +/// output section commands are all subclasses of this class. +/// Examples: +/// +/// OUTPUT_FORMAT("elf64-x86-64") /* A linker script command */ +/// OUTPUT_ARCH(i386:x86-64) /* Another command */ +/// ENTRY(_start) /* Another command */ +/// +/// SECTIONS /* Another command */ +/// { +/// .interp : { /* A sections-command */ +/// *(.interp) /* An output-section-command */ +/// } +/// } +/// class Command { public: - enum class Kind { Entry, OutputFormat, OutputArch, Group, }; + enum class Kind { + Entry, + OutputFormat, + OutputArch, + Group, + SearchDir, + Sections, + SymbolAssignment, + OutputSectionDescription, + InputSectionFile, + Overlay, + }; Kind getKind() const { return _kind; } @@ -155,8 +231,7 @@ class Group : public Command { public: - template - explicit Group(RangeT range) : Command(Kind::Group) { + template explicit Group(RangeT range) : Command(Kind::Group) { std::copy(std::begin(range), std::end(range), std::back_inserter(_paths)); } @@ -188,25 +263,377 @@ class Entry : public Command { public: - explicit Entry(StringRef entryName) : - Command(Kind::Entry), _entryName(entryName) { } + explicit Entry(StringRef entryName) + : Command(Kind::Entry), _entryName(entryName) {} + + static bool classof(const Command *c) { return c->getKind() == Kind::Entry; } + + void dump(raw_ostream &os) const override { + os << "ENTRY(" << _entryName << ")\n"; + } + + const StringRef getEntryName() const { return _entryName; } + +private: + StringRef _entryName; +}; + +class SearchDir : public Command { +public: + explicit SearchDir(StringRef searchPath) + : Command(Kind::SearchDir), _searchPath(searchPath) {} static bool classof(const Command *c) { - return c->getKind() == Kind::Entry; + return c->getKind() == Kind::SearchDir; } void dump(raw_ostream &os) const override { - os << "ENTRY(" << _entryName << ")\n"; + os << "SEARCH_DIR(" << _searchPath << ")\n"; } - const StringRef getEntryName() const { - return _entryName; + const StringRef getSearchPath() const { return _searchPath; } + +private: + StringRef _searchPath; +}; + +/// Superclass for expression nodes. Linker scripts accept C-like expressions in +/// many places, such as when defining the value of a symbol or the address of +/// an output section. +/// Example: +/// +/// SECTIONS { +/// my_symbol = 1 + 1 * 2; +/// | | ^~~~> Constant : Expression +/// | | ^~~~> Constant : Expression +/// | | ^~~~> BinOp : Expression +/// ^~~~> Constant : Expression +/// ^~~~> BinOp : Expression (the top-level Expression node) +/// } +/// +class Expression { +public: + enum class Kind { Constant, Symbol, FunctionCall, BinOp, TernaryConditional }; + + Kind getKind() const { return _kind; } + + virtual void dump(raw_ostream &os) const = 0; + + virtual ~Expression() {} + +protected: + explicit Expression(Kind k) : _kind(k) {} + +private: + Kind _kind; +}; + +class Constant : public Expression { +public: + Constant(uint64_t num) : Expression(Kind::Constant), _num(num) {} + void dump(raw_ostream &os) const override; + + static bool classof(const Expression *c) { + return c->getKind() == Kind::Constant; } private: - StringRef _entryName; + uint64_t _num; }; +class Symbol : public Expression { +public: + Symbol(StringRef name) : Expression(Kind::Symbol), _name(name) {} + void dump(raw_ostream &os) const override; + + static bool classof(const Expression *c) { + return c->getKind() == Kind::Symbol; + } + +private: + StringRef _name; +}; + +class FunctionCall : public Expression { +public: + template + FunctionCall(StringRef name, RangeT range) + : Expression(Kind::FunctionCall), _name(name) { + std::copy(std::begin(range), std::end(range), std::back_inserter(_args)); + } + + void dump(raw_ostream &os) const override; + + static bool classof(const Expression *c) { + return c->getKind() == Kind::FunctionCall; + } + +private: + StringRef _name; + std::vector _args; +}; + +class BinOp : public Expression { +public: + enum Operation { + Sum, + Sub, + Mul, + Div, + Shl, + Shr, + And, + Or, + CompareLess, + CompareGreater, + CompareLessEqual, + CompareGreaterEqual, + CompareEqual, + CompareDifferent + }; + + BinOp(const Expression *LHS, Operation op, const Expression *RHS) + : Expression(Kind::BinOp), _op(op), _LHS(LHS), _RHS(RHS) {} + + void dump(raw_ostream &os) const override; + + static bool classof(const Expression *c) { + return c->getKind() == Kind::BinOp; + } + +private: + Operation _op; + const Expression *_LHS; + const Expression *_RHS; +}; + +class TernaryConditional : public Expression { +public: + TernaryConditional(const Expression *conditional, const Expression *trueExpr, + const Expression *falseExpr) + : Expression(Kind::TernaryConditional), _conditional(conditional), + _trueExpr(trueExpr), _falseExpr(falseExpr) {} + + void dump(raw_ostream &os) const override; + + static bool classof(const Expression *c) { + return c->getKind() == Kind::TernaryConditional; + } + +private: + const Expression *_conditional; + const Expression *_trueExpr; + const Expression *_falseExpr; +}; + +/// Symbol assignments of the form "symbolname = " may occur either +/// as sections-commands or as output-section-commands. +/// Example: +/// +/// SECTIONS { +/// mysymbol = . /* SymbolAssignment as a sections-command */ +/// .data : { +/// othersymbol = . /* SymbolAssignment as an output-section-command */ +/// } +///} +/// +class SymbolAssignment : public Command { +public: + enum AssignmentKind { Simple, Sum, Sub, Mul, Div, Shl, Shr, And, Or }; + enum AssignmentVisibility { Normal, Hidden, Provide, ProvideHidden }; + + SymbolAssignment(StringRef name, const Expression *expr, AssignmentKind kind, + AssignmentVisibility visibility) + : Command(Kind::SymbolAssignment), _expression(expr), _symbol(name), + _assignmentKind(Simple), _assignmentVisibility(visibility) {} + + static bool classof(const Command *c) { + return c->getKind() == Kind::SymbolAssignment; + } + + void dump(raw_ostream &os) const override; + +private: + const Expression *_expression; + StringRef _symbol; + AssignmentKind _assignmentKind; + AssignmentVisibility _assignmentVisibility; +}; + +/// Encodes how to sort file names or section names that are expanded from +/// wildcard operators. This typically occurs in constructs such as +/// SECTIONS { .data : SORT_BY_NAME(*)(*) }}, where the order of the expanded +/// names is important to determine which sections go first. +enum WildcardSortMode { + WSM_NA, + WSM_ByName, + WSM_ByAlignment, + WSM_ByNameAndAlignment, + WSM_ByAlignmentAndName, + WSM_ByInitPriority, + WSM_None +}; + +/// Represents either a single input section name or a group of sorted input +/// section names. They specify which sections to map to a given output section. +class InputSection { +public: + enum class Kind { InputSectionName, SortedGroup }; + + Kind getKind() const { return _kind; } + + virtual void dump(raw_ostream &os) const = 0; + + virtual ~InputSection() {} + +protected: + explicit InputSection(Kind k) : _kind(k) {} + +private: + Kind _kind; +}; + +class InputSectionName : public InputSection { +public: + InputSectionName(StringRef name, bool excludeFile) + : InputSection(Kind::InputSectionName), _name(name), + _excludeFile(excludeFile) {} + + void dump(raw_ostream &os) const override; + + static bool classof(const InputSection *c) { + return c->getKind() == Kind::InputSectionName; + } + +private: + StringRef _name; + bool _excludeFile; +}; + +class InputSectionSortedGroup : public InputSection { +public: + template + InputSectionSortedGroup(WildcardSortMode sort, RangeT range) + : InputSection(Kind::SortedGroup), _sortMode(sort) { + std::copy(std::begin(range), std::end(range), + std::back_inserter(_sections)); + } + + void dump(raw_ostream &os) const override; + WildcardSortMode getSortMode() const { return _sortMode; } + + static bool classof(const InputSection *c) { + return c->getKind() == Kind::SortedGroup; + } + +private: + WildcardSortMode _sortMode; + std::vector _sections; +}; + +/// An output-section-command that maps a series of sections inside a given +/// file to an output section. +class InputSectionFile : public Command { +public: + typedef std::vector VectorTy; + + template + InputSectionFile(StringRef fileName, StringRef archiveName, bool keep, + WildcardSortMode fileSortMode, + WildcardSortMode archiveSortMode, RangeT range) + : Command(Kind::InputSectionFile), _fileName(fileName), + _archiveName(archiveName), _keep(keep), _fileSortMode(fileSortMode), + _archiveSortMode(archiveSortMode) { + std::copy(std::begin(range), std::end(range), + std::back_inserter(_sections)); + } + + void dump(raw_ostream &os) const override; + + static bool classof(const Command *c) { + return c->getKind() == Kind::InputSectionFile; + } + +private: + StringRef _fileName; + StringRef _archiveName; + bool _keep; + WildcardSortMode _fileSortMode; + WildcardSortMode _archiveSortMode; + VectorTy _sections; +}; + +/// A sections-command to specify which input sections compose a given output +/// section. +class OutputSectionDescription : public Command { +public: + enum Constraint { C_None, C_OnlyIfRO, C_OnlyIfRW }; + + template + OutputSectionDescription(StringRef sectionName, const Expression *address, + const Expression *align, const Expression *subAlign, + const Expression *at, const Expression *fillExpr, + bool alignWithInput, bool discard, + Constraint constraint, RangeT range) + : Command(Kind::OutputSectionDescription), _sectionName(sectionName), + _address(address), _align(align), _subAlign(subAlign), _at(at), + _fillExpr(fillExpr), _alignWithInput(alignWithInput), _discard(discard), + _constraint(constraint) { + std::copy(std::begin(range), std::end(range), + std::back_inserter(_outputSectionCommands)); + } + + static bool classof(const Command *c) { + return c->getKind() == Kind::OutputSectionDescription; + } + + void dump(raw_ostream &os) const override; + +private: + StringRef _sectionName; + const Expression *_address; + const Expression *_align; + const Expression *_subAlign; + const Expression *_at; + const Expression *_fillExpr; + bool _alignWithInput; + bool _discard; + Constraint _constraint; + std::vector _outputSectionCommands; +}; + +class Overlay : public Command { +public: + Overlay() : Command(Kind::Overlay) {} + + static bool classof(const Command *c) { + return c->getKind() == Kind::Overlay; + } + + void dump(raw_ostream &os) const override { os << "Overlay description\n"; } + +private: +}; + +/// Represents all the contents of the SECTIONS {} construct. +class Sections : public Command { +public: + template Sections(RangeT range) : Command(Kind::Sections) { + std::copy(std::begin(range), std::end(range), + std::back_inserter(_sectionsCommands)); + } + + static bool classof(const Command *c) { + return c->getKind() == Kind::Sections; + } + + void dump(raw_ostream &os) const override; + +private: + std::vector _sectionsCommands; +}; + +/// Stores the parse tree of a linker script. class LinkerScript { public: void dump(raw_ostream &os) const { @@ -217,19 +644,82 @@ std::vector _commands; }; +/// Recognizes syntactic constructs of a linker script using a predictive +/// parser/recursive descent implementation. +/// +/// Based on the linker script documentation available at +/// https://sourceware.org/binutils/docs/ld/Scripts.html class Parser { public: - explicit Parser(Lexer &lex) : _lex(lex) {} + explicit Parser(Lexer &lex) : _lex(lex), _tokIndex(0), _lookAheadIndex(0) {} LinkerScript *parse(); private: - void consumeToken() { _lex.lex(_tok); } + /// Advances to the next token, either asking the Lexer to lex the next token + /// or obtaining it from the look ahead buffer. + void consumeToken() { + // First check if the look ahead buffer cached the next token + if (_tokIndex + 1 >= _lookAheadIndex && + _lookAheadBuf.size() >= (_tokIndex - _lookAheadIndex + 2)) { + _tok = _lookAheadBuf[_tokIndex + 1 - _lookAheadIndex]; + ++_tokIndex; + return; + } + _lex.lex(_tok); + ++_tokIndex; + } + + /// Returns the nth token that succeeds the current one. If this operation + /// requires lexing additional tokens, store them in a private buffer. + const Token &peek(unsigned n) { + // Covers the case where the look ahead buffer contains the requested token + if (_tokIndex + n >= _lookAheadIndex && + _lookAheadBuf.size() >= (_tokIndex + n - _lookAheadIndex + 1)) + return _lookAheadBuf[_tokIndex + n - _lookAheadIndex]; + + // In this case, the look ahead buffer is filled with old tokens that we are + // not going to access anymore. Flush it and fill it with new tokens, + // starting with the current token until the requested token. + if (_tokIndex - _lookAheadIndex >= _lookAheadBuf.size()) { + _lookAheadBuf.clear(); + _lookAheadBuf.push_back(_tok); + for (unsigned i = 1; i <= n; ++i) { + _lookAheadBuf.push_back(Token()); + _lex.lex(_lookAheadBuf.back()); + } + _lookAheadIndex = _tokIndex; + return _lookAheadBuf[n]; + } + + // In this case, the look ahead buffer starts with the current token, but is + // not large enough to hold the requested future token. We simply expand it. + if (_tokIndex == _lookAheadIndex) { + for (unsigned i = 0, e = n - _lookAheadBuf.size() + 1; i != e; ++i) { + _lookAheadBuf.push_back(Token()); + _lex.lex(_lookAheadBuf.back()); + } + return _lookAheadBuf[n]; + } + + // This last case covers the corner case where some of the tokens in the + // buffer are new, but others are old. We discard the old ones, keep the + // new ones while expanding it to hold the requested token. + SmallVector temp(&_lookAheadBuf[_tokIndex - _lookAheadIndex], + _lookAheadBuf.end()); + _lookAheadBuf.clear(); + _lookAheadBuf.insert(_lookAheadBuf.begin(), temp.begin(), temp.end()); + for (unsigned i = 0, e = n - temp.size() + 1; i != e; ++i) { + _lookAheadBuf.push_back(Token()); + _lex.lex(_lookAheadBuf.back()); + } + return _lookAheadBuf[n]; + } void error(const Token &tok, Twine msg) { - _lex.getSourceMgr() - .PrintMessage(llvm::SMLoc::getFromPointer(tok._range.data()), - llvm::SourceMgr::DK_Error, msg); + _lex.getSourceMgr().PrintMessage( + llvm::SMLoc::getFromPointer(tok._range.data()), + llvm::SourceMgr::DK_Error, msg); } bool expectAndConsume(Token::Kind kind, Twine msg) { @@ -243,17 +733,206 @@ bool isNextToken(Token::Kind kind) { return (_tok._kind == kind); } + // Recursive descent parsing member functions + // All of these functions consumes tokens and return an AST object, + // represented by the Command superclass. However, note that not all AST + // objects derive from Command. For nodes of C-like expressions, used in + // linker scripts, the superclass is Expression. For nodes that represent + // input sections that map to an output section, the superclass is + // InputSection. + // + // Example mapping common constructs to AST nodes: + // + // SECTIONS { /* Parsed to Sections class */ + // my_symbol = 1 + 1; /* Parsed to SymbolAssignment class */ + // /* ^~~> Parsed to Expression class */ + // .data : { *(.data) } /* Parsed to OutputSectionDescription class */ + // /* ^~~> Parsed to InputSectionName class */ + // /* ^~~~~> Parsed to InputSectionFile class */ + // } + + // ==== Expression parsing member functions ==== + + /// Parse "identifier(param [, param]...)" + /// + /// Example: + /// + /// SECTIONS { + /// my_symbol = 0x1000 | ALIGN(other_symbol); + /// /* ^~~~> parseFunctionCall() + /// } + const Expression *parseFunctionCall(); + + /// Ensures that the current token is an expression terminal. If it is not, + /// issues an error to the user and returns false. + bool expectExprTerminal(); + + /// Parse operands of an expression, such as function calls, identifiers or + /// literal numbers. + /// + /// Example: + /// + /// SECTIONS { + /// my_symbol = 0x1000 | ALIGN(other_symbol); + /// ^~~~> parseExprTerminal() + /// } + const Expression *parseExprTerminal(); + + // As a reference to the precedence of C operators, consult + // http://en.cppreference.com/w/c/language/operator_precedence + + /// Parse either a single expression operand and returns or parse an entire + /// expression if its top-level node has a lower or equal precedence than the + /// indicated. + const Expression *parseExpression(unsigned precedence = 13); + + /// Parse an operator and its RHS operand, assuming that the LHS was already + /// consumed. Keep parsing subsequent operator-operand pairs that do not + /// exceed \p highestPrecedence. + /// \p LHS points to the left-hand-side operand of this operator + /// \p maxPrecedence has the maximum operator precedence level that this parse + /// function is allowed to consume. + const Expression *parseOperatorOperandLoop(const Expression *LHS, + unsigned maxPrecedence); + + /// Parse ternary conditionals such as "(condition)? true: false;". This + /// operator has precedence level 13 and associates right-to-left. + const Expression *parseTernaryCondOp(const Expression *LHS); + + // ==== High-level commands parsing ==== + + /// Parse the OUTPUT_FORMAT linker script command. + /// Example: + /// + /// OUTPUT_FORMAT(elf64-x86-64,elf64-x86-64,elf64-x86-64) + /// ^~~~> parseOutputFormat() + /// OutputFormat *parseOutputFormat(); + + /// Parse the OUTPUT_ARCH linker script command. + /// Example: + /// + /// OUTPUT_ARCH(i386:x86-64) + /// ^~~~> parseOutputArch() + /// OutputArch *parseOutputArch(); + + /// Parse the GROUP linker script command. + /// Example: + /// + /// GROUP ( /lib/x86_64-linux-gnu/libc.so.6 + /// /usr/lib/x86_64-linux-gnu/libc_nonshared.a + /// AS_NEEDED ( /lib/x86_64-linux-gnu/ld-linux-x86-64.so.2 ) + /// -lm -l:libgcc.a ) + /// Group *parseGroup(); bool parseAsNeeded(std::vector &paths); + + /// Parse the ENTRY linker script command. + /// Example: + /// + /// ENTRY(init) + /// ^~~~> parseEntry() + /// Entry *parseEntry(); + /// Parse the SEARCH_DIR linker script command. + /// Example: + /// + /// SEARCH_DIR("/usr/x86_64-linux-gnu/lib64"); + /// ^~~~> parseSearchDir() + /// + SearchDir *parseSearchDir(); + + /// Parse "symbol = expression" commands that live inside the + /// SECTIONS directive. + /// Example: + /// + /// SECTIONS { + /// my_symbol = 1 + 1; + /// ^~~~> parseExpression() + /// ^~~~ parseSymbolAssignment() + /// } + /// + const SymbolAssignment *parseSymbolAssignment(); + + /// Parse "EXCLUDE_FILE" used inside the listing of input section names. + /// Example: + /// + /// SECTIONS { + /// .data : { *(EXCLUDE_FILE (*crtend.o *otherfile.o) .ctors) } + /// ^~~~> parseExcludeFile() + /// } + /// + ErrorOr parseExcludeFile(); + + /// Helper to parse SORT_BY_NAME(, SORT_BY_ALIGNMENT( and SORT_NONE(, + /// possibly nested. Returns the number of Token::r_paren tokens that need + /// to be consumed, while \p sortMode is updated with the parsed sort + /// criteria. + /// Example: + /// + /// SORT_BY_NAME(SORT_BY_ALIGNMENT(*)) + /// ^~~~ parseSortDirectives() ~~^ + /// Returns 2, finishes with sortMode = WSM_ByNameAndAlignment + /// + int parseSortDirectives(WildcardSortMode &sortMode); + + /// Parse a group of input section names that are sorted via SORT* directives. + /// Example: + /// SORT_BY_NAME(SORT_BY_ALIGNMENT(*data *bss)) + const InputSection *parseSortedInputSections(); + + /// Parse input section description statements. + /// Example: + /// + /// SECTIONS { + /// .mysection : crt.o(.data* .bss SORT_BY_NAME(name*)) + /// ^~~~ parseInputSectionFile() + /// } + const InputSectionFile *parseInputSectionFile(); + + /// Parse output section description statements. + /// Example: + /// + /// SECTIONS { + /// .data : { crt.o(.data* .bss SORT_BY_NAME(name*)) } + /// ^~~~ parseOutputSectionDescription() + /// } + const OutputSectionDescription *parseOutputSectionDescription(); + + /// Stub for parsing overlay commands. Currently unimplemented. + const Overlay *parseOverlay(); + + /// Parse the SECTIONS linker script command. + /// Example: + /// + /// SECTIONS { + /// ^~~~ parseSections() + /// . = 0x100000; + /// .data : { *(.data) } + /// } + /// + Sections *parseSections(); + private: + // Owns the entire linker script AST nodes llvm::BumpPtrAllocator _alloc; + + // The top-level/entry-point linker script AST node LinkerScript _script; + Lexer &_lex; + + // Current token being analyzed Token _tok; + + // Keep track of the current token index and the index of the first cached + // token, allowing us to manage a buffer of future tokens and implement + // lookahead. + unsigned _tokIndex; + unsigned _lookAheadIndex; + llvm::SmallVector _lookAheadBuf; }; } // end namespace script } // end namespace lld Index: lib/ReaderWriter/LinkerScript.cpp =================================================================== --- lib/ReaderWriter/LinkerScript.cpp +++ lib/ReaderWriter/LinkerScript.cpp @@ -18,27 +18,245 @@ namespace script { void Token::dump(raw_ostream &os) const { switch (_kind) { -#define CASE(name) \ - case Token::name: \ - os << #name ": "; \ - break; - CASE(eof) - CASE(identifier) - CASE(libname) - CASE(kw_as_needed) - CASE(kw_entry) - CASE(kw_group) - CASE(kw_output_format) - CASE(kw_output_arch) - CASE(comma) - CASE(l_paren) - CASE(r_paren) - CASE(unknown) +#define CASE(name) \ + case Token::name: \ + os << #name ": "; \ + break; + CASE(eof) + CASE(identifier) + CASE(libname) + CASE(kw_as_needed) + CASE(kw_search_dir) + CASE(kw_sections) + CASE(kw_hidden) + CASE(kw_provide) + CASE(kw_provide_hidden) + CASE(kw_overlay) + CASE(kw_discard) + CASE(kw_at) + CASE(kw_align) + CASE(kw_align_with_input) + CASE(kw_subalign) + CASE(kw_exclude_file) + CASE(kw_sort_by_name) + CASE(kw_sort_by_alignment) + CASE(kw_sort_by_init_priority) + CASE(kw_sort_none) + CASE(kw_keep) + CASE(kw_only_if_ro) + CASE(kw_only_if_rw) + CASE(kw_entry) + CASE(kw_group) + CASE(kw_output_format) + CASE(kw_output_arch) + CASE(comma) + CASE(colon) + CASE(semicolon) + CASE(number) + CASE(l_paren) + CASE(r_paren) + CASE(l_brace) + CASE(r_brace) + CASE(question) + CASE(exclaim) + CASE(exclaimequal) + CASE(equal) + CASE(plus) + CASE(plusequal) + CASE(minus) + CASE(minusequal) + CASE(star) + CASE(starequal) + CASE(slash) + CASE(slashequal) + CASE(amp) + CASE(ampequal) + CASE(pipe) + CASE(pipeequal) + CASE(less) + CASE(lessless) + CASE(lesslessequal) + CASE(greater) + CASE(greatergreater) + CASE(greatergreaterequal) + CASE(equalequal) + CASE(lessequal) + CASE(greaterequal) + CASE(unknown) #undef CASE } os << _range << "\n"; } +static llvm::ErrorOr parseDecimal(StringRef str) { + uint64_t res = 0; + for (auto &c : str) { + res *= 10; + if (c < '0' || c > '9') + return llvm::ErrorOr(std::make_error_code(std::errc::io_error)); + res += c - '0'; + } + return llvm::ErrorOr(res); +} + +static llvm::ErrorOr parseOctal(StringRef str) { + uint64_t res = 0; + for (auto &c : str) { + res <<= 3; + if (c < '0' || c > '7') + return llvm::ErrorOr(std::make_error_code(std::errc::io_error)); + res += c - '0'; + } + return llvm::ErrorOr(res); +} + +static llvm::ErrorOr parseBinary(StringRef str) { + uint64_t res = 0; + for (auto &c : str) { + res <<= 1; + if (c != '0' && c != '1') + return llvm::ErrorOr(std::make_error_code(std::errc::io_error)); + res += c - '0'; + } + return llvm::ErrorOr(res); +} + +static llvm::ErrorOr parseHex(StringRef str) { + uint64_t res = 0; + for (auto &c : str) { + res <<= 4; + if (((c < '0' || c > '9') && (c < 'a' || c > 'f') && (c < 'A' || c > 'F'))) + return llvm::ErrorOr(std::make_error_code(std::errc::io_error)); + if (c >= '0' && c <= '9') + res += c - '0'; + else if (c >= 'a' && c <= 'f') + res += c - 'a' + 10; + else + res += c - 'A' + 10; + } + return llvm::ErrorOr(res); +} + +static llvm::ErrorOr parseNum(StringRef str) { + bool suffixK = false; + bool suffixM = false; + enum NumKind { decimal, hex, octal, binary }; + NumKind kind = llvm::StringSwitch(str) + .StartsWith("0x", hex) + .StartsWith("0", octal) + .Default(decimal); + + // Parse scale + if (str.endswith("K")) { + suffixK = true; + str = str.drop_back(); + } else if (str.endswith("M")) { + suffixM = true; + str = str.drop_back(); + } + + // Parse type + if (str.endswith_lower("o")) { + kind = octal; + str = str.drop_back(); + } else if (str.endswith_lower("h")) { + kind = hex; + str = str.drop_back(); + } else if (str.endswith_lower("d")) { + kind = decimal; + str = str.drop_back(); + } else if (str.endswith_lower("b")) { + kind = binary; + str = str.drop_back(); + } + + llvm::ErrorOr res(0); + switch (kind) { + case hex: + if (str.startswith("0x")) + str = str.drop_front(2); + res = parseHex(str); + break; + case octal: + res = parseOctal(str); + break; + case decimal: + res = parseDecimal(str); + break; + case binary: + res = parseBinary(str); + break; + } + if (!res.getError()) { + if (suffixK) + *res = *res << 10; + else if (suffixM) + *res = *res << 20; + } + return res; +} + +bool Lexer::canStartNumber(char c) const { + switch (c) { + // Digits + case '0': + case '1': + case '2': + case '3': + case '4': + case '5': + case '6': + case '7': + case '8': + case '9': + return true; + default: + return false; + } +} + +bool Lexer::canContinueNumber(char c) const { + switch (c) { + // Digits + case '0': + case '1': + case '2': + case '3': + case '4': + case '5': + case '6': + case '7': + case '8': + case '9': + case 'A': + case 'B': + case 'C': + case 'D': + case 'E': + case 'F': + case 'a': + case 'b': + case 'c': + case 'd': + case 'e': + case 'f': + // Hex marker + case 'x': + case 'X': + // Type suffix + case 'h': + case 'H': + case 'o': + case 'O': + // Scale suffix + case 'M': + case 'K': + return true; + default: + return false; + } +} + bool Lexer::canStartName(char c) const { switch (c) { case 'A': case 'B': case 'C': case 'D': case 'E': case 'F': case 'G': @@ -50,6 +268,7 @@ case 'o': case 'p': case 'q': case 'r': case 's': case 't': case 'u': case 'v': case 'w': case 'x': case 'y': case 'z': case '_': case '.': case '$': case '/': case '\\': + case '*': return true; default: return false; @@ -101,10 +320,136 @@ tok = Token(_buffer.substr(0, 1), Token::r_paren); _buffer = _buffer.drop_front(); return; + case '{': + tok = Token(_buffer.substr(0, 1), Token::l_brace); + _buffer = _buffer.drop_front(); + return; + case '}': + tok = Token(_buffer.substr(0, 1), Token::r_brace); + _buffer = _buffer.drop_front(); + return; + case '=': + if (_buffer.startswith("==")) { + tok = Token(_buffer.substr(0, 2), Token::equalequal); + _buffer = _buffer.drop_front(2); + return; + } + tok = Token(_buffer.substr(0, 1), Token::equal); + _buffer = _buffer.drop_front(); + return; + case '!': + if (_buffer.startswith("!=")) { + tok = Token(_buffer.substr(0, 2), Token::exclaimequal); + _buffer = _buffer.drop_front(2); + return; + } + tok = Token(_buffer.substr(0, 1), Token::exclaim); + _buffer = _buffer.drop_front(); + return; case ',': tok = Token(_buffer.substr(0, 1), Token::comma); _buffer = _buffer.drop_front(); return; + case ';': + tok = Token(_buffer.substr(0, 1), Token::semicolon); + _buffer = _buffer.drop_front(); + return; + case ':': + tok = Token(_buffer.substr(0, 1), Token::colon); + _buffer = _buffer.drop_front(); + return; + case '&': + if (_buffer.startswith("&=")) { + tok = Token(_buffer.substr(0, 2), Token::ampequal); + _buffer = _buffer.drop_front(2); + return; + } + tok = Token(_buffer.substr(0, 1), Token::amp); + _buffer = _buffer.drop_front(); + return; + case '|': + if (_buffer.startswith("|=")) { + tok = Token(_buffer.substr(0, 2), Token::pipeequal); + _buffer = _buffer.drop_front(2); + return; + } + tok = Token(_buffer.substr(0, 1), Token::pipe); + _buffer = _buffer.drop_front(); + return; + case '+': + if (_buffer.startswith("+=")) { + tok = Token(_buffer.substr(0, 2), Token::plusequal); + _buffer = _buffer.drop_front(2); + return; + } + tok = Token(_buffer.substr(0, 1), Token::plus); + _buffer = _buffer.drop_front(); + return; + case '-': { + if (_buffer.startswith("-=")) { + tok = Token(_buffer.substr(0, 2), Token::minusequal); + _buffer = _buffer.drop_front(2); + return; + } + if (!_buffer.startswith("-l")) { + tok = Token(_buffer.substr(0, 1), Token::minus); + _buffer = _buffer.drop_front(); + return; + } + // -l + _buffer = _buffer.drop_front(2); + StringRef::size_type start = 0; + if (_buffer[start] == ':') + ++start; + if (!canStartName(_buffer[start])) + // Create 'unknown' token. + break; + auto libNameEnd = std::find_if(_buffer.begin() + start + 1, _buffer.end(), + [=](char c) { return !canContinueName(c); }); + StringRef::size_type libNameLen = + std::distance(_buffer.begin(), libNameEnd); + tok = Token(_buffer.substr(0, libNameLen), Token::libname); + _buffer = _buffer.drop_front(libNameLen); + return; + } + case '<': + if (_buffer.startswith("<<=")) { + tok = Token(_buffer.substr(0, 3), Token::lesslessequal); + _buffer = _buffer.drop_front(3); + return; + } + if (_buffer.startswith("<<")) { + tok = Token(_buffer.substr(0, 2), Token::lessless); + _buffer = _buffer.drop_front(2); + return; + } + if (_buffer.startswith("<=")) { + tok = Token(_buffer.substr(0, 2), Token::lessequal); + _buffer = _buffer.drop_front(2); + return; + } + tok = Token(_buffer.substr(0, 1), Token::less); + _buffer = _buffer.drop_front(); + return; + case '>': + if (_buffer.startswith(">>=")) { + tok = Token(_buffer.substr(0, 3), Token::greatergreaterequal); + _buffer = _buffer.drop_front(3); + return; + } + if (_buffer.startswith(">>")) { + tok = Token(_buffer.substr(0, 2), Token::greatergreater); + _buffer = _buffer.drop_front(2); + return; + } + if (_buffer.startswith(">=")) { + tok = Token(_buffer.substr(0, 2), Token::greaterequal); + _buffer = _buffer.drop_front(2); + return; + } + tok = Token(_buffer.substr(0, 1), Token::greater); + _buffer = _buffer.drop_front(); + return; default: // Handle quoted strings. They are treated as identifiers for // simplicity. @@ -119,44 +464,94 @@ _buffer = _buffer.drop_front(quotedStringEnd + 1); return; } - // -l - if (_buffer.startswith("-l")) { - _buffer = _buffer.drop_front(2); - StringRef::size_type start = 0; - if (_buffer[start] == ':') - ++start; - if (!canStartName(_buffer[start])) - // Create 'unknown' token. + // Handle literal numbers + if ((_buffer.startswith("0x") && _buffer.size() > 2 && + canContinueNumber(_buffer[2])) || + canStartNumber(_buffer[0])) { + auto endIter = std::find_if(_buffer.begin(), _buffer.end(), [=](char c) { + return !canContinueNumber(c); + }); + StringRef::size_type end = endIter == _buffer.end() + ? StringRef::npos + : std::distance(_buffer.begin(), endIter); + if (end == StringRef::npos || end == 0) break; - auto libNameEnd = - std::find_if(_buffer.begin() + start + 1, _buffer.end(), - [=](char c) { return !canContinueName(c); }); - StringRef::size_type libNameLen = - std::distance(_buffer.begin(), libNameEnd); - tok = Token(_buffer.substr(0, libNameLen), Token::libname); - _buffer = _buffer.drop_front(libNameLen); + StringRef word = _buffer.substr(0, end); + tok = Token(word, Token::number); + _buffer = _buffer.drop_front(end); + return; + } + /// Handle slashes '/', which can be either an operator inside an expression + /// or the beginning of an identifier + if (_buffer.startswith("/=")) { + tok = Token(_buffer.substr(0, 2), Token::slashequal); + _buffer = _buffer.drop_front(2); return; } - /// keyword or identifer. + if (_buffer[0] == '/' && _buffer.size() > 1 && + !canContinueName(_buffer[1])) { + tok = Token(_buffer.substr(0, 1), Token::slash); + _buffer = _buffer.drop_front(); + return; + } + /// Handle stars '*' + if (_buffer.startswith("*=")) { + tok = Token(_buffer.substr(0, 2), Token::starequal); + _buffer = _buffer.drop_front(2); + return; + } + if (_buffer[0] == '*' && _buffer.size() > 1 && + !canContinueName(_buffer[1])) { + tok = Token(_buffer.substr(0, 1), Token::star); + _buffer = _buffer.drop_front(); + return; + } + /// Handle questions '?' + if (_buffer[0] == '?' && _buffer.size() > 1 && + !canContinueName(_buffer[1])) { + tok = Token(_buffer.substr(0, 1), Token::question); + _buffer = _buffer.drop_front(); + return; + } + /// keyword or identifier. if (!canStartName(_buffer[0])) break; - auto endIter = - std::find_if(_buffer.begin() + 1, _buffer.end(), [=](char c) { - return !canContinueName(c); - }); - StringRef::size_type end = - endIter == _buffer.end() ? StringRef::npos - : std::distance(_buffer.begin(), endIter); + auto endIter = std::find_if(_buffer.begin() + 1, _buffer.end(), + [=](char c) { return !canContinueName(c); }); + StringRef::size_type end = endIter == _buffer.end() + ? StringRef::npos + : std::distance(_buffer.begin(), endIter); if (end == StringRef::npos || end == 0) break; StringRef word = _buffer.substr(0, end); - Token::Kind kind = llvm::StringSwitch(word) - .Case("OUTPUT_FORMAT", Token::kw_output_format) - .Case("OUTPUT_ARCH", Token::kw_output_arch) - .Case("GROUP", Token::kw_group) - .Case("AS_NEEDED", Token::kw_as_needed) - .Case("ENTRY", Token::kw_entry) - .Default(Token::identifier); + Token::Kind kind = + llvm::StringSwitch(word) + .Case("OUTPUT_FORMAT", Token::kw_output_format) + .Case("OUTPUT_ARCH", Token::kw_output_arch) + .Case("GROUP", Token::kw_group) + .Case("AS_NEEDED", Token::kw_as_needed) + .Case("SEARCH_DIR", Token::kw_search_dir) + .Case("SECTIONS", Token::kw_sections) + .Case("HIDDEN", Token::kw_hidden) + .Case("PROVIDE", Token::kw_provide) + .Case("PROVIDE_HIDDEN", Token::kw_provide_hidden) + .Case("OVERLAY", Token::kw_overlay) + .Case("AT", Token::kw_at) + .Case("ALIGN", Token::kw_align) + .Case("ALIGN_WITH_INPUT", Token::kw_align_with_input) + .Case("SUBALIGN", Token::kw_subalign) + .Case("EXCLUDE_FILE", Token::kw_exclude_file) + .Case("SORT_BY_NAME", Token::kw_sort_by_name) + .Case("SORT_BY_ALIGNMENT", Token::kw_sort_by_alignment) + .Case("SORT_BY_INIT_PRIORITY", Token::kw_sort_by_init_priority) + .Case("SORT_NONE", Token::kw_sort_none) + .Case("SORT", Token::kw_sort_by_name) + .Case("KEEP", Token::kw_keep) + .Case("ONLY_IF_RO", Token::kw_only_if_ro) + .Case("ONLY_IF_RW", Token::kw_only_if_rw) + .Case("/DISCARD/", Token::kw_discard) + .Case("ENTRY", Token::kw_entry) + .Default(Token::identifier); tok = Token(word, kind); _buffer = _buffer.drop_front(end); return; @@ -202,6 +597,292 @@ } } +// Constant functions +void Constant::dump(raw_ostream &os) const { os << _num; } + +// Symbol functions +void Symbol::dump(raw_ostream &os) const { os << _name; } + +// FunctionCall functions +void FunctionCall::dump(raw_ostream &os) const { + os << _name << "("; + if (unsigned e = _args.size()) { + _args[0]->dump(os); + for (unsigned i = 1; i != e; ++i) { + os << ", "; + _args[i]->dump(os); + } + } + os << ")"; +} + +// BinOp functions +void BinOp::dump(raw_ostream &os) const { + os << "("; + _LHS->dump(os); + os << " "; + switch (_op) { + case Sum: + os << "+"; + break; + case Sub: + os << "-"; + break; + case Mul: + os << "*"; + break; + case Div: + os << "/"; + break; + case Shl: + os << "<<"; + break; + case Shr: + os << ">>"; + break; + case And: + os << "&"; + break; + case Or: + os << "|"; + break; + case CompareEqual: + os << "=="; + break; + case CompareDifferent: + os << "!="; + break; + case CompareLess: + os << "<"; + break; + case CompareGreater: + os << ">"; + break; + case CompareLessEqual: + os << "<="; + break; + case CompareGreaterEqual: + os << ">="; + break; + } + os << " "; + _RHS->dump(os); + os << ")"; +} + +// TernaryConditional functions +void TernaryConditional::dump(raw_ostream &os) const { + _conditional->dump(os); + os << " ? "; + _trueExpr->dump(os); + os << " : "; + _falseExpr->dump(os); +} + +// SymbolAssignment functions +void SymbolAssignment::dump(raw_ostream &os) const { + int numParen = 0; + + if (_assignmentVisibility != Normal) { + switch (_assignmentVisibility) { + case Hidden: + os << "HIDDEN("; + break; + case Provide: + os << "PROVIDE("; + break; + case ProvideHidden: + os << "PROVIDE_HIDDEN("; + break; + default: + llvm_unreachable("Unknown visibility"); + } + ++numParen; + } + + os << _symbol << " "; + switch (_assignmentKind) { + case Simple: + os << "="; + break; + case Sum: + os << "+="; + break; + case Sub: + os << "-="; + break; + case Mul: + os << "*="; + break; + case Div: + os << "/="; + break; + case Shl: + os << "<<="; + break; + case Shr: + os << ">>="; + break; + case And: + os << "&="; + break; + case Or: + os << "|="; + break; + } + + os << " "; + _expression->dump(os); + if (numParen) + os << ")"; +} + +static int dumpSortDirectives(raw_ostream &os, WildcardSortMode sortMode) { + int numParen = 0; + switch (sortMode) { + case WSM_NA: + break; + case WSM_ByName: + os << "SORT_BY_NAME("; + numParen = 1; + break; + case WSM_ByAlignment: + os << "SORT_BY_ALIGNMENT("; + numParen = 1; + break; + case WSM_ByInitPriority: + os << "SORT_BY_INIT_PRIORITY("; + numParen = 1; + break; + case WSM_ByNameAndAlignment: + os << "SORT_BY_NAME(SORT_BY_ALIGNMENT"; + numParen = 2; + break; + case WSM_ByAlignmentAndName: + os << "SORT_BY_ALIGNMENT(SORT_BY_NAME"; + numParen = 2; + break; + case WSM_None: + os << "SORT_NONE("; + numParen = 1; + break; + } + return numParen; +} + +// InputSectionName functions +void InputSectionName::dump(raw_ostream &os) const { + if (_excludeFile) + os << "EXCLUDE_FILE("; + os << _name; + if (_excludeFile) + os << ")"; +} + +// InputSectionSortedGroup functions +void InputSectionSortedGroup::dump(raw_ostream &os) const { + int numParen = dumpSortDirectives(os, _sortMode); + for (auto &secName : _sections) { + secName->dump(os); + os << " "; + } + for (int i = 0; i < numParen; ++i) + os << ")"; +} + +// InputSectionFile functions +void InputSectionFile::dump(raw_ostream &os) const { + if (_keep) + os << "KEEP("; + int numParen = dumpSortDirectives(os, _fileSortMode); + os << _fileName; + for (int i = 0; i < numParen; ++i) + os << ")"; + os << ":"; + numParen = dumpSortDirectives(os, _archiveSortMode); + os << _archiveName; + for (int i = 0; i < numParen; ++i) + os << ")"; + os << "("; + for (auto &command : _sections) { + command->dump(os); + os << " "; + } + os << ")"; + if (_keep) + os << ")"; +} + +// OutputSectionDescription functions +void OutputSectionDescription::dump(raw_ostream &os) const { + if (_discard) + os << "/DISCARD/"; + else + os << _sectionName; + + if (_address) { + os << " "; + _address->dump(os); + } + os << " :\n"; + + if (_at) { + os << " AT("; + _at->dump(os); + os << ")\n"; + } + + if (_align) { + os << " ALIGN("; + _align->dump(os); + os << ")\n"; + } else if (_alignWithInput) { + os << " ALIGN_WITH_INPUT\n"; + } + + if (_subAlign) { + os << " SUBALIGN("; + _subAlign->dump(os); + os << ")\n"; + } + + switch (_constraint) { + case C_None: + break; + case C_OnlyIfRO: + os << "ONLY_IF_RO"; + break; + case C_OnlyIfRW: + os << "ONLY_IF_RW"; + break; + } + + os << " { \n"; + for (auto &command : _outputSectionCommands) { + os << " "; + command->dump(os); + os << "\n"; + } + os << " }"; + + if (_fillExpr) { + os << " ="; + _fillExpr->dump(os); + os << ";"; + } +} + +// Sections functions +void Sections::dump(raw_ostream &os) const { + os << "SECTIONS\n{\n"; + for (auto &command : _sectionsCommands) { + command->dump(os); + os << "\n"; + } + os << "}\n"; +} + +// Parser functions LinkerScript *Parser::parse() { // Get the first token. _lex.lex(_tok); @@ -210,6 +891,9 @@ switch (_tok._kind) { case Token::eof: return &_script; + case Token::semicolon: + consumeToken(); + break; case Token::kw_output_format: { auto outputFormat = parseOutputFormat(); if (!outputFormat) @@ -233,6 +917,7 @@ } case Token::kw_as_needed: // Not allowed at top level. + error(_tok, "AS_NEEDED not allowed at top level."); return nullptr; case Token::kw_entry: { Entry *entry = parseEntry(); @@ -241,8 +926,23 @@ _script._commands.push_back(entry); break; } + case Token::kw_search_dir: { + SearchDir *searchDir = parseSearchDir(); + if (!searchDir) + return nullptr; + _script._commands.push_back(searchDir); + break; + } + case Token::kw_sections: { + Sections *sections = parseSections(); + if (!sections) + return nullptr; + _script._commands.push_back(sections); + break; + } default: // Unexpected. + error(_tok, "Unrecognized token."); return nullptr; } } @@ -250,51 +950,269 @@ return nullptr; } -// Parse OUTPUT_FORMAT(ident) -OutputFormat *Parser::parseOutputFormat() { - assert(_tok._kind == Token::kw_output_format && "Expected OUTPUT_FORMAT!"); +const Expression *Parser::parseFunctionCall() { + assert((_tok._kind == Token::identifier || _tok._kind == Token::kw_align) && + "expected function call first tokens"); + std::vector params; + StringRef name = _tok._range; + consumeToken(); if (!expectAndConsume(Token::l_paren, "expected (")) return nullptr; - if (_tok._kind != Token::identifier) { - error(_tok, "Expected identifier in OUTPUT_FORMAT."); - return nullptr; + if (_tok._kind == Token::r_paren) { + consumeToken(); + return new (_alloc) FunctionCall(_tok._range, params); } - auto ret = new (_alloc) OutputFormat(_tok._range); - consumeToken(); + if (const Expression *firstParam = parseExpression()) + params.push_back(firstParam); + else + return nullptr; - do { - if (isNextToken(Token::comma)) - consumeToken(); + while (_tok._kind == Token::comma) { + consumeToken(); + if (const Expression *param = parseExpression()) + params.push_back(param); else - break; - if (_tok._kind != Token::identifier) { - error(_tok, "Expected identifier in OUTPUT_FORMAT."); return nullptr; - } - ret->addOutputFormat(_tok._range); - consumeToken(); - } while (isNextToken(Token::comma)); + } if (!expectAndConsume(Token::r_paren, "expected )")) return nullptr; - - return ret; + return new (_alloc) FunctionCall(name, params); } -// Parse OUTPUT_ARCH(ident) -OutputArch *Parser::parseOutputArch() { - assert(_tok._kind == Token::kw_output_arch && "Expected OUTPUT_ARCH!"); - consumeToken(); - if (!expectAndConsume(Token::l_paren, "expected (")) - return nullptr; +bool Parser::expectExprTerminal() { + if (!(_tok._kind == Token::identifier || _tok._kind == Token::number || + _tok._kind == Token::kw_align || _tok._kind == Token::l_paren)) { + error(_tok, "expected symbol, number or left parenthesis."); + return false; + } + return true; +} - if (_tok._kind != Token::identifier) { - error(_tok, "Expected identifier in OUTPUT_ARCH."); +const Expression *Parser::parseExprTerminal() { + if (!expectExprTerminal()) return nullptr; - } + + switch (_tok._kind) { + case Token::identifier: + switch (peek(1)._kind) { + case Token::l_paren: + return parseFunctionCall(); + default: { + Symbol *sym = new (_alloc) Symbol(_tok._range); + consumeToken(); + return sym; + } + } + break; + case Token::kw_align: + return parseFunctionCall(); + case Token::number: { + auto val = parseNum(_tok._range); + if (val.getError()) { + error(_tok, "Unrecognized number constant"); + return nullptr; + } + Constant *c = new (_alloc) Constant(*val); + consumeToken(); + return c; + } + case Token::l_paren: { + consumeToken(); + const Expression *expr = parseExpression(); + if (!expectAndConsume(Token::r_paren, "expected )")) + return nullptr; + return expr; + } + default: + llvm_unreachable("Unknown token"); + } +} + +static bool TokenToBinOp(const Token &tok, BinOp::Operation &op, + unsigned &precedence) { + switch (tok._kind) { + case Token::star: + op = BinOp::Mul; + precedence = 3; + return true; + case Token::slash: + op = BinOp::Div; + precedence = 3; + return true; + case Token::plus: + op = BinOp::Sum; + precedence = 4; + return true; + case Token::minus: + op = BinOp::Sub; + precedence = 4; + return true; + case Token::lessless: + op = BinOp::Shl; + precedence = 5; + return true; + case Token::greatergreater: + op = BinOp::Shr; + precedence = 5; + return true; + case Token::less: + op = BinOp::CompareLess; + precedence = 6; + return true; + case Token::greater: + op = BinOp::CompareGreater; + precedence = 6; + return true; + case Token::lessequal: + op = BinOp::CompareLessEqual; + precedence = 6; + return true; + case Token::greaterequal: + op = BinOp::CompareGreaterEqual; + precedence = 6; + return true; + case Token::equalequal: + op = BinOp::CompareEqual; + precedence = 7; + return true; + case Token::exclaimequal: + op = BinOp::CompareDifferent; + precedence = 7; + return true; + case Token::amp: + op = BinOp::And; + precedence = 8; + return true; + case Token::pipe: + op = BinOp::Or; + precedence = 10; + return true; + default: + break; + } + return false; +} + +const Expression *Parser::parseExpression(unsigned precedence) { + assert(precedence <= 13 && "Invalid precedence value"); + if (!expectExprTerminal()) + return nullptr; + + const Expression *expr = parseExprTerminal(); + if (!expr) + return nullptr; + + BinOp::Operation op; + unsigned binOpPrecedence = 0; + if (TokenToBinOp(_tok, op, binOpPrecedence)) { + if (precedence >= binOpPrecedence) + return parseOperatorOperandLoop(expr, precedence); + return expr; + } + + // Non-binary operators + if (_tok._kind == Token::question && precedence >= 13) + return parseOperatorOperandLoop(expr, precedence); + return expr; +} + +const Expression *Parser::parseOperatorOperandLoop(const Expression *LHS, + unsigned highestPrecedence) { + assert(highestPrecedence <= 13 && "Invalid precedence value"); + unsigned precedence = 0; + const Expression *binOp = nullptr; + + while (1) { + BinOp::Operation op; + if (!TokenToBinOp(_tok, op, precedence)) { + if (_tok._kind == Token::question && highestPrecedence >= 13) + return parseTernaryCondOp(LHS); + return binOp; + } + + if (precedence > highestPrecedence) + return binOp; + + consumeToken(); + const Expression *RHS = parseExpression(precedence - 1); + if (!RHS) + return nullptr; + binOp = new (_alloc) BinOp(LHS, op, RHS); + LHS = binOp; + } +} + +const Expression *Parser::parseTernaryCondOp(const Expression *LHS) { + assert(_tok._kind == Token::question && "Expected question mark"); + + consumeToken(); + + // The ternary conditional operator has right-to-left associativity. + // To implement this, we allow our children to contain ternary conditional + // operators themselves (precedence 13). + const Expression *trueExpr = parseExpression(13); + if (!trueExpr) + return nullptr; + + if (!expectAndConsume(Token::colon, "expected :")) + return nullptr; + + const Expression *falseExpr = parseExpression(13); + if (!falseExpr) + return nullptr; + + return new (_alloc) TernaryConditional(LHS, trueExpr, falseExpr); +} + +// Parse OUTPUT_FORMAT(ident) +OutputFormat *Parser::parseOutputFormat() { + assert(_tok._kind == Token::kw_output_format && "Expected OUTPUT_FORMAT!"); + consumeToken(); + if (!expectAndConsume(Token::l_paren, "expected (")) + return nullptr; + + if (_tok._kind != Token::identifier) { + error(_tok, "Expected identifier in OUTPUT_FORMAT."); + return nullptr; + } + + auto ret = new (_alloc) OutputFormat(_tok._range); + consumeToken(); + + do { + if (isNextToken(Token::comma)) + consumeToken(); + else + break; + if (_tok._kind != Token::identifier) { + error(_tok, "Expected identifier in OUTPUT_FORMAT."); + return nullptr; + } + ret->addOutputFormat(_tok._range); + consumeToken(); + } while (isNextToken(Token::comma)); + + if (!expectAndConsume(Token::r_paren, "expected )")) + return nullptr; + + return ret; +} + +// Parse OUTPUT_ARCH(ident) +OutputArch *Parser::parseOutputArch() { + assert(_tok._kind == Token::kw_output_arch && "Expected OUTPUT_ARCH!"); + consumeToken(); + if (!expectAndConsume(Token::l_paren, "expected (")) + return nullptr; + + if (_tok._kind != Token::identifier) { + error(_tok, "Expected identifier in OUTPUT_ARCH."); + return nullptr; + } auto ret = new (_alloc) OutputArch(_tok._range); consumeToken(); @@ -386,5 +1304,564 @@ return new (_alloc) Entry(entryName); } +// Parse SEARCH_DIR(ident) +SearchDir *Parser::parseSearchDir() { + assert(_tok._kind == Token::kw_search_dir && "Expected SEARCH_DIR!"); + consumeToken(); + if (!expectAndConsume(Token::l_paren, "expected (")) + return nullptr; + if (_tok._kind != Token::identifier) { + error(_tok, "expected identifier in SEARCH_DIR"); + return nullptr; + } + StringRef searchPath(_tok._range); + consumeToken(); + if (!expectAndConsume(Token::r_paren, "expected )")) + return nullptr; + return new (_alloc) SearchDir(searchPath); +} + +const SymbolAssignment *Parser::parseSymbolAssignment() { + assert((_tok._kind == Token::identifier || _tok._kind == Token::kw_hidden || + _tok._kind == Token::kw_provide || + _tok._kind == Token::kw_provide_hidden) && + "Expected identifier!"); + SymbolAssignment::AssignmentVisibility visibility = SymbolAssignment::Normal; + SymbolAssignment::AssignmentKind kind; + int numParen = 0; + + if (_tok._kind == Token::kw_hidden || _tok._kind == Token::kw_provide || + _tok._kind == Token::kw_provide_hidden) { + switch (_tok._kind) { + case Token::kw_hidden: + visibility = SymbolAssignment::Hidden; + break; + case Token::kw_provide: + visibility = SymbolAssignment::Provide; + break; + case Token::kw_provide_hidden: + visibility = SymbolAssignment::ProvideHidden; + break; + default: + llvm_unreachable("Unknown token"); + } + ++numParen; + consumeToken(); + if (!expectAndConsume(Token::l_paren, "expected (")) + return nullptr; + } + + StringRef name = _tok._range; + consumeToken(); + + // Parse assignment operator (=, +=, -= etc.) + switch (_tok._kind) { + case Token::equal: + kind = SymbolAssignment::Simple; + consumeToken(); + break; + case Token::plusequal: + kind = SymbolAssignment::Sum; + consumeToken(); + break; + case Token::minusequal: + kind = SymbolAssignment::Sub; + consumeToken(); + break; + case Token::starequal: + kind = SymbolAssignment::Mul; + consumeToken(); + break; + case Token::slashequal: + kind = SymbolAssignment::Div; + consumeToken(); + break; + case Token::ampequal: + kind = SymbolAssignment::And; + consumeToken(); + break; + case Token::pipeequal: + kind = SymbolAssignment::Or; + consumeToken(); + break; + case Token::lesslessequal: + kind = SymbolAssignment::Shl; + consumeToken(); + break; + case Token::greatergreaterequal: + kind = SymbolAssignment::Shr; + consumeToken(); + break; + default: + error(_tok, "unexpected token"); + return nullptr; + } + + const Expression *expr = nullptr; + switch (_tok._kind) { + case Token::number: + case Token::kw_align: + case Token::identifier: + case Token::l_paren: + expr = parseExpression(); + if (!expr) + return nullptr; + break; + default: + error(_tok, "unexpected token while parsing assignment value."); + return nullptr; + } + + for (int i = 0; i < numParen; ++i) + if (!expectAndConsume(Token::r_paren, "expected )")) + return nullptr; + + return new (_alloc) SymbolAssignment(name, expr, kind, visibility); +} + +llvm::ErrorOr Parser::parseExcludeFile() { + assert(_tok._kind == Token::kw_exclude_file && "Expected EXCLUDE_FILE!"); + InputSectionFile::VectorTy res; + consumeToken(); + + if (!expectAndConsume(Token::l_paren, "expected (")) + return llvm::ErrorOr( + std::make_error_code(std::errc::io_error)); + + while (_tok._kind == Token::identifier) { + res.push_back(new (_alloc) InputSectionName(_tok._range, true)); + consumeToken(); + } + + if (!expectAndConsume(Token::r_paren, "expected )")) + return llvm::ErrorOr( + std::make_error_code(std::errc::io_error)); + return llvm::ErrorOr(std::move(res)); +} + +int Parser::parseSortDirectives(WildcardSortMode &sortMode) { + int numParsedDirectives = 0; + sortMode = WSM_NA; + + if (_tok._kind == Token::kw_sort_by_name) { + consumeToken(); + if (!expectAndConsume(Token::l_paren, "expected (")) + return -1; + ++numParsedDirectives; + sortMode = WSM_ByName; + } + + if (_tok._kind == Token::kw_sort_by_init_priority) { + consumeToken(); + if (!expectAndConsume(Token::l_paren, "expected (")) + return -1; + ++numParsedDirectives; + sortMode = WSM_ByInitPriority; + } + + if (_tok._kind == Token::kw_sort_by_alignment) { + consumeToken(); + if (!expectAndConsume(Token::l_paren, "expected (")) + return -1; + ++numParsedDirectives; + if (sortMode != WSM_ByName) + sortMode = WSM_ByAlignment; + else + sortMode = WSM_ByNameAndAlignment; + } + + if (numParsedDirectives < 2 && _tok._kind == Token::kw_sort_by_name) { + consumeToken(); + if (!expectAndConsume(Token::l_paren, "expected (")) + return -1; + ++numParsedDirectives; + if (sortMode == WSM_ByAlignment) + sortMode = WSM_ByAlignmentAndName; + } + + if (numParsedDirectives < 2 && _tok._kind == Token::kw_sort_by_alignment) { + consumeToken(); + if (!expectAndConsume(Token::l_paren, "expected (")) + return -1; + ++numParsedDirectives; + } + + if (numParsedDirectives == 0 && _tok._kind == Token::kw_sort_none) { + consumeToken(); + if (!expectAndConsume(Token::l_paren, "expected (")) + return -1; + ++numParsedDirectives; + sortMode = WSM_None; + } + + return numParsedDirectives; +} + +const InputSection *Parser::parseSortedInputSections() { + assert((_tok._kind == Token::kw_sort_by_name || + _tok._kind == Token::kw_sort_by_alignment || + _tok._kind == Token::kw_sort_by_init_priority || + _tok._kind == Token::kw_sort_none) && + "Expected SORT directives!"); + + WildcardSortMode sortMode = WSM_NA; + int numParen = parseSortDirectives(sortMode); + if (numParen == -1) + return nullptr; + + std::vector inputSections; + + while (_tok._kind == Token::identifier) { + inputSections.push_back(new (_alloc) InputSectionName(_tok._range, false)); + consumeToken(); + } + + // Eat "numParen" rparens + for (int i = 0, e = numParen; i != e; ++i) + if (!expectAndConsume(Token::r_paren, "expected )")) + return nullptr; + + return new (_alloc) InputSectionSortedGroup(sortMode, inputSections); +} + +const InputSectionFile *Parser::parseInputSectionFile() { + assert((_tok._kind == Token::identifier || _tok._kind == Token::colon || + _tok._kind == Token::star || _tok._kind == Token::kw_keep || + _tok._kind == Token::kw_sort_by_name || + _tok._kind == Token::kw_sort_by_alignment || + _tok._kind == Token::kw_sort_by_init_priority || + _tok._kind == Token::kw_sort_none) && + "Expected input section first tokens!"); + int numParen = 1; + bool keep = false; + WildcardSortMode fileSortMode = WSM_NA; + WildcardSortMode archiveSortMode = WSM_NA; + StringRef fileName; + StringRef archiveName; + + if (_tok._kind == Token::kw_keep) { + consumeToken(); + if (!expectAndConsume(Token::l_paren, "expected (")) + return nullptr; + ++numParen; + keep = true; + } + + // Input name + if (_tok._kind != Token::colon) { + int numParen = parseSortDirectives(fileSortMode); + if (numParen == -1) + return nullptr; + fileName = _tok._range; + consumeToken(); + if (numParen) { + while (numParen--) + if (!expectAndConsume(Token::r_paren, "expected )")) + return nullptr; + } + } + if (_tok._kind == Token::colon) { + consumeToken(); + if (_tok._kind == Token::identifier || + _tok._kind == Token::kw_sort_by_name || + _tok._kind == Token::kw_sort_by_alignment || + _tok._kind == Token::kw_sort_by_init_priority || + _tok._kind == Token::kw_sort_none) { + int numParen = parseSortDirectives(archiveSortMode); + if (numParen == -1) + return nullptr; + archiveName = _tok._range; + consumeToken(); + if (numParen) { + while (numParen--) + if (!expectAndConsume(Token::r_paren, "expected )")) + return nullptr; + } + } + } + + std::vector inputSections; + + if (_tok._kind != Token::l_paren) + return new (_alloc) + InputSectionFile(fileName, archiveName, keep, fileSortMode, + archiveSortMode, inputSections); + ; + consumeToken(); + + while (_tok._kind == Token::identifier || + _tok._kind == Token::kw_exclude_file || + _tok._kind == Token::kw_sort_by_name || + _tok._kind == Token::kw_sort_by_alignment || + _tok._kind == Token::kw_sort_by_init_priority || + _tok._kind == Token::kw_sort_none) { + switch (_tok._kind) { + case Token::kw_exclude_file: { + auto vec = parseExcludeFile(); + if (vec.getError()) + return nullptr; + inputSections.insert(inputSections.end(), vec->begin(), vec->end()); + break; + } + case Token::star: + case Token::identifier: { + inputSections.push_back(new (_alloc) + InputSectionName(_tok._range, false)); + consumeToken(); + break; + } + case Token::kw_sort_by_name: + case Token::kw_sort_by_alignment: + case Token::kw_sort_by_init_priority: + case Token::kw_sort_none: { + const InputSection *group = parseSortedInputSections(); + if (!group) + return nullptr; + inputSections.push_back(group); + break; + } + default: + llvm_unreachable("Unknown token"); + } + } + + for (int i = 0; i < numParen; ++i) + if (!expectAndConsume(Token::r_paren, "expected )")) + return nullptr; + return new (_alloc) + InputSectionFile(fileName, archiveName, keep, fileSortMode, + archiveSortMode, inputSections); +} + +const OutputSectionDescription *Parser::parseOutputSectionDescription() { + assert((_tok._kind == Token::kw_discard || _tok._kind == Token::identifier) && + "Expected /DISCARD/ or identifier!"); + StringRef sectionName; + const Expression *address = nullptr; + const Expression *align = nullptr; + const Expression *subAlign = nullptr; + const Expression *at = nullptr; + const Expression *fillExpr = nullptr; + bool alignWithInput = false; + bool discard = false; + OutputSectionDescription::Constraint constraint = + OutputSectionDescription::C_None; + std::vector outputSectionCommands; + + if (_tok._kind == Token::kw_discard) + discard = true; + else + sectionName = _tok._range; + consumeToken(); + + if (_tok._kind == Token::number || _tok._kind == Token::identifier || + _tok._kind == Token::kw_align || _tok._kind == Token::l_paren) { + address = parseExpression(); + if (!address) + return nullptr; + } + + if (!expectAndConsume(Token::colon, "expected :")) + return nullptr; + + if (_tok._kind == Token::kw_at) { + consumeToken(); + at = parseExpression(); + if (!at) + return nullptr; + } + + if (_tok._kind == Token::kw_align) { + consumeToken(); + align = parseExpression(); + if (!align) + return nullptr; + } + + if (_tok._kind == Token::kw_align_with_input) { + consumeToken(); + alignWithInput = true; + } + + if (_tok._kind == Token::kw_subalign) { + consumeToken(); + subAlign = parseExpression(); + if (!subAlign) + return nullptr; + } + + if (_tok._kind == Token::kw_only_if_ro) { + consumeToken(); + constraint = OutputSectionDescription::C_OnlyIfRO; + } else if (_tok._kind == Token::kw_only_if_rw) { + consumeToken(); + constraint = OutputSectionDescription::C_OnlyIfRW; + } + + if (!expectAndConsume(Token::l_brace, "expected {")) + return nullptr; + + // Parse zero or more output-section-commands + while (_tok._kind != Token::r_brace) { + switch (_tok._kind) { + case Token::semicolon: + consumeToken(); + break; + case Token::identifier: + switch (peek(1)._kind) { + case Token::equal: + case Token::plusequal: + case Token::minusequal: + case Token::starequal: + case Token::slashequal: + case Token::ampequal: + case Token::pipeequal: + case Token::lesslessequal: + case Token::greatergreaterequal: + if (const Command *cmd = parseSymbolAssignment()) + outputSectionCommands.push_back(cmd); + else + return nullptr; + break; + default: + if (const Command *cmd = parseInputSectionFile()) + outputSectionCommands.push_back(cmd); + else + return nullptr; + break; + } + break; + case Token::kw_keep: + case Token::star: + case Token::colon: + case Token::kw_sort_by_name: + case Token::kw_sort_by_alignment: + case Token::kw_sort_by_init_priority: + case Token::kw_sort_none: + if (const Command *cmd = parseInputSectionFile()) + outputSectionCommands.push_back(cmd); + else + return nullptr; + break; + case Token::kw_hidden: + case Token::kw_provide: + case Token::kw_provide_hidden: + if (const Command *cmd = parseSymbolAssignment()) + outputSectionCommands.push_back(cmd); + else + return nullptr; + break; + default: + error(_tok, "expected symbol assignment or input file name."); + return nullptr; + } + } + + if (!expectAndConsume(Token::r_brace, "expected }")) + return nullptr; + + if (_tok._kind == Token::equal) { + consumeToken(); + fillExpr = parseExpression(); + if (!fillExpr) + return nullptr; + } + + return new (_alloc) OutputSectionDescription( + sectionName, address, align, subAlign, at, fillExpr, alignWithInput, + discard, constraint, outputSectionCommands); +} + +const Overlay *Parser::parseOverlay() { + assert(_tok._kind == Token::kw_overlay && "Expected OVERLAY!"); + error(_tok, "Overlay description is not yet supported."); + return nullptr; +} + +Sections *Parser::parseSections() { + assert(_tok._kind == Token::kw_sections && "Expected SECTIONS!"); + consumeToken(); + if (!expectAndConsume(Token::l_brace, "expected {")) + return nullptr; + std::vector sectionsCommands; + + bool unrecognizedToken = false; + // Parse zero or more sections-commands + while (!unrecognizedToken) { + switch (_tok._kind) { + case Token::semicolon: + consumeToken(); + break; + + case Token::identifier: + switch (peek(1)._kind) { + case Token::equal: + case Token::plusequal: + case Token::minusequal: + case Token::starequal: + case Token::slashequal: + case Token::ampequal: + case Token::pipeequal: + case Token::lesslessequal: + case Token::greatergreaterequal: + if (const Command *cmd = parseSymbolAssignment()) + sectionsCommands.push_back(cmd); + else + return nullptr; + break; + default: + if (const Command *cmd = parseOutputSectionDescription()) + sectionsCommands.push_back(cmd); + else + return nullptr; + break; + } + break; + + case Token::kw_discard: + case Token::star: + if (const Command *cmd = parseOutputSectionDescription()) + sectionsCommands.push_back(cmd); + else + return nullptr; + break; + + case Token::kw_entry: + if (const Command *cmd = parseEntry()) + sectionsCommands.push_back(cmd); + else + return nullptr; + break; + + case Token::kw_hidden: + case Token::kw_provide: + case Token::kw_provide_hidden: + if (const Command *cmd = parseSymbolAssignment()) + sectionsCommands.push_back(cmd); + else + return nullptr; + break; + + case Token::kw_overlay: + if (const Command *cmd = parseOverlay()) + sectionsCommands.push_back(cmd); + else + return nullptr; + break; + + default: + unrecognizedToken = true; + break; + } + } + + if (!expectAndConsume( + Token::r_brace, + "expected symbol assignment, entry, overlay or output section name.")) + return nullptr; + + return new (_alloc) Sections(sectionsCommands); +} + } // end namespace script } // end namespace lld Index: test/LinkerScript/expr-precedence.test =================================================================== --- /dev/null +++ test/LinkerScript/expr-precedence.test @@ -0,0 +1,29 @@ +/* + RUN: linker-script-test %s | FileCheck %s +*/ +SECTIONS { + . = foo >= bar + 1 ? bar : 1; +} + +/* +CHECK: kw_sections: SECTIONS +CHECK: l_brace: { +CHECK: identifier: . +CHECK: equal: = +CHECK: identifier: foo +CHECK: greaterequal: >= +CHECK: identifier: bar +CHECK: plus: + +CHECK: number: 1 +CHECK: question: ? +CHECK: identifier: bar +CHECK: colon: : +CHECK: number: 1 +CHECK: semicolon: ; +CHECK: r_brace: } +CHECK: eof: +CHECK: SECTIONS +CHECK: { +CHECK: . = (foo >= (bar + 1)) ? bar : 1 +CHECK: } +*/ Index: test/LinkerScript/incomplete-ternary.test =================================================================== --- /dev/null +++ test/LinkerScript/incomplete-ternary.test @@ -0,0 +1,21 @@ +/* + RUN: linker-script-test %s 2> %t | FileCheck %s + RUN: FileCheck -input-file %t -check-prefix=CHECK-ERR %s +*/ +SECTIONS { + . = foo ? bar; +} + +/* +CHECK: kw_sections: SECTIONS +CHECK: l_brace: { +CHECK: identifier: . +CHECK: equal: = +CHECK: identifier: foo +CHECK: question: ? +CHECK: identifier: bar +CHECK: semicolon: ; +CHECK: r_brace: } +CHECK: eof: +CHECK-ERR: 6:18: error: expected : +*/ Index: test/LinkerScript/missing-entry-symbol.test =================================================================== --- /dev/null +++ test/LinkerScript/missing-entry-symbol.test @@ -0,0 +1,17 @@ +/* + RUN: linker-script-test %s 2> %t | FileCheck %s + RUN: FileCheck -input-file %t -check-prefix=CHECK-ERR %s +*/ +SECTIONS { + ENTRY() +} + +/* +CHECK: l_brace: { +CHECK: kw_entry: ENTRY +CHECK: l_paren: ( +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: eof: +CHECK-ERR: 6:11: error: expected identifier in ENTRY +*/ Index: test/LinkerScript/missing-input-file-name.test =================================================================== --- /dev/null +++ test/LinkerScript/missing-input-file-name.test @@ -0,0 +1,21 @@ +/* + RUN: linker-script-test %s 2> %t | FileCheck %s + RUN: FileCheck -input-file %t -check-prefix=CHECK-ERR %s +*/ +SECTIONS { + .text : { ()} +} + +/* +CHECK: kw_sections: SECTIONS +CHECK: l_brace: { +CHECK: identifier: .text +CHECK: colon: : +CHECK: l_brace: { +CHECK: l_paren: ( +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: r_brace: } +CHECK: eof: +CHECK-ERR: 6:15: error: expected symbol assignment or input file name. +*/ Index: test/LinkerScript/missing-input-sections.test =================================================================== --- /dev/null +++ test/LinkerScript/missing-input-sections.test @@ -0,0 +1,23 @@ +/* + RUN: linker-script-test %s 2> %t | FileCheck %s + RUN: FileCheck -input-file %t -check-prefix=CHECK-ERR %s +*/ +SECTIONS { + .text : { *(+)} +} + +/* +CHECK: kw_sections: SECTIONS +CHECK: l_brace: { +CHECK: identifier: .text +CHECK: colon: : +CHECK: l_brace: { +CHECK: star: * +CHECK: l_paren: ( +CHECK: plus: + +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: r_brace: } +CHECK: eof: +CHECK-ERR: 6:16: error: expected ) +*/ Index: test/LinkerScript/missing-operand.test =================================================================== --- /dev/null +++ test/LinkerScript/missing-operand.test @@ -0,0 +1,20 @@ +/* + RUN: linker-script-test %s 2> %t | FileCheck %s + RUN: FileCheck -check-prefix=CHECK-ERR -input-file %t %s +*/ +SECTIONS { + . = foo / ; +} + +/* +CHECK: kw_sections: SECTIONS +CHECK: l_brace: { +CHECK: identifier: . +CHECK: equal: = +CHECK: identifier: foo +CHECK: slash: / +CHECK: semicolon: ; +CHECK: r_brace: } +CHECK: eof: +CHECK-ERR: 6:15: error: expected symbol, number or left parenthesis. + */ Index: test/LinkerScript/missing-output-section-name.test =================================================================== --- /dev/null +++ test/LinkerScript/missing-output-section-name.test @@ -0,0 +1,21 @@ +/* + RUN: linker-script-test %s 2> %t | FileCheck %s + RUN: FileCheck -input-file %t -check-prefix=CHECK-ERR %s +*/ +SECTIONS { + : { *()} +} + +/* +CHECK: kw_sections: SECTIONS +CHECK: l_brace: { +CHECK: colon: : +CHECK: l_brace: { +CHECK: star: * +CHECK: l_paren: ( +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: r_brace: } +CHECK: eof: +CHECK-ERR: 6:5: error: expected symbol assignment, entry, overlay or output section name +*/ Index: test/LinkerScript/missing-symbol.test =================================================================== --- /dev/null +++ test/LinkerScript/missing-symbol.test @@ -0,0 +1,20 @@ +/* + RUN: linker-script-test %s 2> %t | FileCheck %s + RUN: FileCheck -input-file %t -check-prefix=CHECK-ERR %s +*/ +SECTIONS { + = foo + bar; +} + +/* +CHECK: kw_sections: SECTIONS +CHECK: l_brace: { +CHECK: equal: = +CHECK: identifier: foo +CHECK: plus: + +CHECK: identifier: bar +CHECK: semicolon: ; +CHECK: r_brace: } +CHECK: eof: +CHECK-ERR: 6:5: error: expected symbol assignment, entry, overlay or output section name +*/ Index: test/LinkerScript/sections.test =================================================================== --- /dev/null +++ test/LinkerScript/sections.test @@ -0,0 +1,618 @@ +/* + This test exercises parsing typical commands found in GNU ld linker scripts. + RUN: linker-script-test %s | FileCheck %s +*/ + +SEARCH_DIR("/usr/x86_64-linux-gnu/lib64"); SEARCH_DIR("=/usr/local/lib/x86_64-linux-gnu"); +SECTIONS +{ + PROVIDE (__executable_start = SEGMENT_START("text-segment", 0x400000)); . = SEGMENT_START("text-segment", 0x400000) + SIZEOF_HEADERS; + .interp : { *(.interp) } + .note.gnu.build-id : { *(.note.gnu.build-id) } + .hash : { *(.hash) } + .rela.dyn : + { + *(.rela.init) + *(.rela.text .rela.text.* .rela.gnu.linkonce.t.*) + *(.rela.fini) + *(.rela.rodata .rela.rodata.* .rela.gnu.linkonce.r.*) + } + .rela.plt : + { + *(.rela.plt) + PROVIDE_HIDDEN (__rela_iplt_start = .); + *(.rela.iplt) + PROVIDE_HIDDEN (__rela_iplt_end = .); + } + .init : + { + KEEP (*(SORT_NONE(.init))) + } + PROVIDE (__etext = .); + .eh_frame : ONLY_IF_RO { KEEP (*(.eh_frame)) } + .exception_ranges : ONLY_IF_RO { *(.exception_ranges + .exception_ranges*) } + . = ALIGN (CONSTANT (MAXPAGESIZE)) - ((CONSTANT (MAXPAGESIZE) - .) & (CONSTANT (MAXPAGESIZE) - 1)); . = DATA_SEGMENT_ALIGN (CONSTANT (MAXPAGESIZE), CONSTANT (COMMONPAGESIZE)); + /* Exception handling */ + .eh_frame : ONLY_IF_RW { KEEP (*(.eh_frame)) } + .ctors : + { + KEEP (*crtbegin.o(.ctors)) + KEEP (*crtbegin?.o(.ctors)) + KEEP (*(EXCLUDE_FILE (*crtend.o *crtend?.o ) .ctors)) + KEEP (*(SORT(.ctors.*))) + KEEP (*(.ctors)) + } + .dtors : + { + KEEP (*crtbegin.o(.dtors)) + KEEP (*crtbegin?.o(.dtors)) + KEEP (*(EXCLUDE_FILE (*crtend.o *crtend?.o ) .dtors)) + KEEP (*(SORT(.dtors.*))) + KEEP (*(.dtors)) + } + . = DATA_SEGMENT_RELRO_END (SIZEOF (.got.plt) >= 24 ? 24 : 0, .); + .got.plt : { *(.got.plt) *(.igot.plt) } + .lrodata ALIGN(CONSTANT (MAXPAGESIZE)) + (. & (CONSTANT (MAXPAGESIZE) - 1)) : + { + *(.lrodata .lrodata.* .gnu.linkonce.lr.*) + } + .ldata ALIGN(CONSTANT (MAXPAGESIZE)) + (. & (CONSTANT (MAXPAGESIZE) - 1)) : + { + *(.ldata .ldata.* .gnu.linkonce.l.*) + . = ALIGN(. != 0 ? 64 / 8 : 1); + } + . = ALIGN(64 / 8); + _end = .; PROVIDE (end = .); + . = DATA_SEGMENT_END (.); + /DISCARD/ : { *(.note.GNU-stack) *(.gnu_debuglink) *(.gnu.lto_*) } +} + +/* +CHECK: kw_search_dir: SEARCH_DIR +CHECK: l_paren: ( +CHECK: identifier: /usr/x86_64-linux-gnu/lib64 +CHECK: r_paren: ) +CHECK: semicolon: ; +CHECK: kw_search_dir: SEARCH_DIR +CHECK: l_paren: ( +CHECK: identifier: =/usr/local/lib/x86_64-linux-gnu +CHECK: r_paren: ) +CHECK: semicolon: ; +CHECK: kw_sections: SECTIONS +CHECK: l_brace: { +CHECK: kw_provide: PROVIDE +CHECK: l_paren: ( +CHECK: identifier: __executable_start +CHECK: equal: = +CHECK: identifier: SEGMENT_START +CHECK: l_paren: ( +CHECK: identifier: text-segment +CHECK: comma: , +CHECK: number: 0x400000 +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: semicolon: ; +CHECK: identifier: . +CHECK: equal: = +CHECK: identifier: SEGMENT_START +CHECK: l_paren: ( +CHECK: identifier: text-segment +CHECK: comma: , +CHECK: number: 0x400000 +CHECK: r_paren: ) +CHECK: plus: + +CHECK: identifier: SIZEOF_HEADERS +CHECK: semicolon: ; +CHECK: identifier: .interp +CHECK: colon: : +CHECK: l_brace: { +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .interp +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: identifier: .note.gnu.build-id +CHECK: colon: : +CHECK: l_brace: { +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .note.gnu.build-id +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: identifier: .hash +CHECK: colon: : +CHECK: l_brace: { +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .hash +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: identifier: .rela.dyn +CHECK: colon: : +CHECK: l_brace: { +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .rela.init +CHECK: r_paren: ) +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .rela.text +CHECK: identifier: .rela.text.* +CHECK: identifier: .rela.gnu.linkonce.t.* +CHECK: r_paren: ) +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .rela.fini +CHECK: r_paren: ) +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .rela.rodata +CHECK: identifier: .rela.rodata.* +CHECK: identifier: .rela.gnu.linkonce.r.* +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: identifier: .rela.plt +CHECK: colon: : +CHECK: l_brace: { +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .rela.plt +CHECK: r_paren: ) +CHECK: kw_provide_hidden: PROVIDE_HIDDEN +CHECK: l_paren: ( +CHECK: identifier: __rela_iplt_start +CHECK: equal: = +CHECK: identifier: . +CHECK: r_paren: ) +CHECK: semicolon: ; +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .rela.iplt +CHECK: r_paren: ) +CHECK: kw_provide_hidden: PROVIDE_HIDDEN +CHECK: l_paren: ( +CHECK: identifier: __rela_iplt_end +CHECK: equal: = +CHECK: identifier: . +CHECK: r_paren: ) +CHECK: semicolon: ; +CHECK: r_brace: } +CHECK: identifier: .init +CHECK: colon: : +CHECK: l_brace: { +CHECK: kw_keep: KEEP +CHECK: l_paren: ( +CHECK: star: * +CHECK: l_paren: ( +CHECK: kw_sort_none: SORT_NONE +CHECK: l_paren: ( +CHECK: identifier: .init +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: kw_provide: PROVIDE +CHECK: l_paren: ( +CHECK: identifier: __etext +CHECK: equal: = +CHECK: identifier: . +CHECK: r_paren: ) +CHECK: semicolon: ; +CHECK: identifier: .eh_frame +CHECK: colon: : +CHECK: kw_only_if_ro: ONLY_IF_RO +CHECK: l_brace: { +CHECK: kw_keep: KEEP +CHECK: l_paren: ( +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .eh_frame +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: identifier: .exception_ranges +CHECK: colon: : +CHECK: kw_only_if_ro: ONLY_IF_RO +CHECK: l_brace: { +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .exception_ranges +CHECK: identifier: .exception_ranges* +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: identifier: . +CHECK: equal: = +CHECK: kw_align: ALIGN +CHECK: l_paren: ( +CHECK: identifier: CONSTANT +CHECK: l_paren: ( +CHECK: identifier: MAXPAGESIZE +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: minus: - +CHECK: l_paren: ( +CHECK: l_paren: ( +CHECK: identifier: CONSTANT +CHECK: l_paren: ( +CHECK: identifier: MAXPAGESIZE +CHECK: r_paren: ) +CHECK: minus: - +CHECK: identifier: . +CHECK: r_paren: ) +CHECK: amp: & +CHECK: l_paren: ( +CHECK: identifier: CONSTANT +CHECK: l_paren: ( +CHECK: identifier: MAXPAGESIZE +CHECK: r_paren: ) +CHECK: minus: - +CHECK: number: 1 +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: semicolon: ; +CHECK: identifier: . +CHECK: equal: = +CHECK: identifier: DATA_SEGMENT_ALIGN +CHECK: l_paren: ( +CHECK: identifier: CONSTANT +CHECK: l_paren: ( +CHECK: identifier: MAXPAGESIZE +CHECK: r_paren: ) +CHECK: comma: , +CHECK: identifier: CONSTANT +CHECK: l_paren: ( +CHECK: identifier: COMMONPAGESIZE +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: semicolon: ; +CHECK: identifier: .eh_frame +CHECK: colon: : +CHECK: kw_only_if_rw: ONLY_IF_RW +CHECK: l_brace: { +CHECK: kw_keep: KEEP +CHECK: l_paren: ( +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .eh_frame +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: identifier: .ctors +CHECK: colon: : +CHECK: l_brace: { +CHECK: kw_keep: KEEP +CHECK: l_paren: ( +CHECK: identifier: *crtbegin.o +CHECK: l_paren: ( +CHECK: identifier: .ctors +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: kw_keep: KEEP +CHECK: l_paren: ( +CHECK: identifier: *crtbegin?.o +CHECK: l_paren: ( +CHECK: identifier: .ctors +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: kw_keep: KEEP +CHECK: l_paren: ( +CHECK: star: * +CHECK: l_paren: ( +CHECK: kw_exclude_file: EXCLUDE_FILE +CHECK: l_paren: ( +CHECK: identifier: *crtend.o +CHECK: identifier: *crtend?.o +CHECK: r_paren: ) +CHECK: identifier: .ctors +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: kw_keep: KEEP +CHECK: l_paren: ( +CHECK: star: * +CHECK: l_paren: ( +CHECK: kw_sort_by_name: SORT +CHECK: l_paren: ( +CHECK: identifier: .ctors.* +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: kw_keep: KEEP +CHECK: l_paren: ( +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .ctors +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: identifier: .dtors +CHECK: colon: : +CHECK: l_brace: { +CHECK: kw_keep: KEEP +CHECK: l_paren: ( +CHECK: identifier: *crtbegin.o +CHECK: l_paren: ( +CHECK: identifier: .dtors +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: kw_keep: KEEP +CHECK: l_paren: ( +CHECK: identifier: *crtbegin?.o +CHECK: l_paren: ( +CHECK: identifier: .dtors +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: kw_keep: KEEP +CHECK: l_paren: ( +CHECK: star: * +CHECK: l_paren: ( +CHECK: kw_exclude_file: EXCLUDE_FILE +CHECK: l_paren: ( +CHECK: identifier: *crtend.o +CHECK: identifier: *crtend?.o +CHECK: r_paren: ) +CHECK: identifier: .dtors +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: kw_keep: KEEP +CHECK: l_paren: ( +CHECK: star: * +CHECK: l_paren: ( +CHECK: kw_sort_by_name: SORT +CHECK: l_paren: ( +CHECK: identifier: .dtors.* +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: kw_keep: KEEP +CHECK: l_paren: ( +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .dtors +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: identifier: . +CHECK: equal: = +CHECK: identifier: DATA_SEGMENT_RELRO_END +CHECK: l_paren: ( +CHECK: identifier: SIZEOF +CHECK: l_paren: ( +CHECK: identifier: .got.plt +CHECK: r_paren: ) +CHECK: greaterequal: >= +CHECK: number: 24 +CHECK: question: ? +CHECK: number: 24 +CHECK: colon: : +CHECK: number: 0 +CHECK: comma: , +CHECK: identifier: . +CHECK: r_paren: ) +CHECK: semicolon: ; +CHECK: identifier: .got.plt +CHECK: colon: : +CHECK: l_brace: { +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .got.plt +CHECK: r_paren: ) +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .igot.plt +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: identifier: .lrodata +CHECK: kw_align: ALIGN +CHECK: l_paren: ( +CHECK: identifier: CONSTANT +CHECK: l_paren: ( +CHECK: identifier: MAXPAGESIZE +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: plus: + +CHECK: l_paren: ( +CHECK: identifier: . +CHECK: amp: & +CHECK: l_paren: ( +CHECK: identifier: CONSTANT +CHECK: l_paren: ( +CHECK: identifier: MAXPAGESIZE +CHECK: r_paren: ) +CHECK: minus: - +CHECK: number: 1 +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: colon: : +CHECK: l_brace: { +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .lrodata +CHECK: identifier: .lrodata.* +CHECK: identifier: .gnu.linkonce.lr.* +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: identifier: .ldata +CHECK: kw_align: ALIGN +CHECK: l_paren: ( +CHECK: identifier: CONSTANT +CHECK: l_paren: ( +CHECK: identifier: MAXPAGESIZE +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: plus: + +CHECK: l_paren: ( +CHECK: identifier: . +CHECK: amp: & +CHECK: l_paren: ( +CHECK: identifier: CONSTANT +CHECK: l_paren: ( +CHECK: identifier: MAXPAGESIZE +CHECK: r_paren: ) +CHECK: minus: - +CHECK: number: 1 +CHECK: r_paren: ) +CHECK: r_paren: ) +CHECK: colon: : +CHECK: l_brace: { +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .ldata +CHECK: identifier: .ldata.* +CHECK: identifier: .gnu.linkonce.l.* +CHECK: r_paren: ) +CHECK: identifier: . +CHECK: equal: = +CHECK: kw_align: ALIGN +CHECK: l_paren: ( +CHECK: identifier: . +CHECK: exclaimequal: != +CHECK: number: 0 +CHECK: question: ? +CHECK: number: 64 +CHECK: slash: / +CHECK: number: 8 +CHECK: colon: : +CHECK: number: 1 +CHECK: r_paren: ) +CHECK: semicolon: ; +CHECK: r_brace: } +CHECK: identifier: . +CHECK: equal: = +CHECK: kw_align: ALIGN +CHECK: l_paren: ( +CHECK: number: 64 +CHECK: slash: / +CHECK: number: 8 +CHECK: r_paren: ) +CHECK: semicolon: ; +CHECK: identifier: _end +CHECK: equal: = +CHECK: identifier: . +CHECK: semicolon: ; +CHECK: kw_provide: PROVIDE +CHECK: l_paren: ( +CHECK: identifier: end +CHECK: equal: = +CHECK: identifier: . +CHECK: r_paren: ) +CHECK: semicolon: ; +CHECK: identifier: . +CHECK: equal: = +CHECK: identifier: DATA_SEGMENT_END +CHECK: l_paren: ( +CHECK: identifier: . +CHECK: r_paren: ) +CHECK: semicolon: ; +CHECK: kw_discard: /DISCARD/ +CHECK: colon: : +CHECK: l_brace: { +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .note.GNU-stack +CHECK: r_paren: ) +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .gnu_debuglink +CHECK: r_paren: ) +CHECK: star: * +CHECK: l_paren: ( +CHECK: identifier: .gnu.lto_* +CHECK: r_paren: ) +CHECK: r_brace: } +CHECK: r_brace: } +CHECK: eof: +CHECK: SEARCH_DIR(/usr/x86_64-linux-gnu/lib64) +CHECK: SEARCH_DIR(=/usr/local/lib/x86_64-linux-gnu) +CHECK: SECTIONS +CHECK: { +CHECK: PROVIDE(__executable_start = SEGMENT_START(text-segment, 4194304)) +CHECK: . = (SEGMENT_START(text-segment, 4194304) + SIZEOF_HEADERS) +CHECK: .interp : +CHECK: { +CHECK: *:(.interp ) +CHECK: } +CHECK: .note.gnu.build-id : +CHECK: { +CHECK: *:(.note.gnu.build-id ) +CHECK: } +CHECK: .hash : +CHECK: { +CHECK: *:(.hash ) +CHECK: } +CHECK: .rela.dyn : +CHECK: { +CHECK: *:(.rela.init ) +CHECK: *:(.rela.text .rela.text.* .rela.gnu.linkonce.t.* ) +CHECK: *:(.rela.fini ) +CHECK: *:(.rela.rodata .rela.rodata.* .rela.gnu.linkonce.r.* ) +CHECK: } +CHECK: .rela.plt : +CHECK: { +CHECK: *:(.rela.plt ) +CHECK: PROVIDE_HIDDEN(__rela_iplt_start = .) +CHECK: *:(.rela.iplt ) +CHECK: PROVIDE_HIDDEN(__rela_iplt_end = .) +CHECK: } +CHECK: .init : +CHECK: { +CHECK: KEEP(*:(SORT_NONE(.init ) )) +CHECK: } +CHECK: PROVIDE(__etext = .) +CHECK: .eh_frame : +CHECK: ONLY_IF_RO { +CHECK: KEEP(*:(.eh_frame )) +CHECK: } +CHECK: .exception_ranges : +CHECK: ONLY_IF_RO { +CHECK: *:(.exception_ranges .exception_ranges* ) +CHECK: } +CHECK: . = (ALIGN(CONSTANT(MAXPAGESIZE)) - ((CONSTANT(MAXPAGESIZE) - .) & (CONSTANT(MAXPAGESIZE) - 1))) +CHECK: . = DATA_SEGMENT_ALIGN(CONSTANT(MAXPAGESIZE), CONSTANT(COMMONPAGESIZE)) +CHECK: .eh_frame : +CHECK: ONLY_IF_RW { +CHECK: KEEP(*:(.eh_frame )) +CHECK: } +CHECK: .ctors : +CHECK: { +CHECK: KEEP(*crtbegin.o:(.ctors )) +CHECK: KEEP(*crtbegin?.o:(.ctors )) +CHECK: KEEP(*:(EXCLUDE_FILE(*crtend.o) EXCLUDE_FILE(*crtend?.o) .ctors )) +CHECK: KEEP(*:(SORT_BY_NAME(.ctors.* ) )) +CHECK: KEEP(*:(.ctors )) +CHECK: } +CHECK: .dtors : +CHECK: { +CHECK: KEEP(*crtbegin.o:(.dtors )) +CHECK: KEEP(*crtbegin?.o:(.dtors )) +CHECK: KEEP(*:(EXCLUDE_FILE(*crtend.o) EXCLUDE_FILE(*crtend?.o) .dtors )) +CHECK: KEEP(*:(SORT_BY_NAME(.dtors.* ) )) +CHECK: KEEP(*:(.dtors )) +CHECK: } +CHECK: . = DATA_SEGMENT_RELRO_END((SIZEOF(.got.plt) >= 24) ? 24 : 0, .) +CHECK: .got.plt : +CHECK: { +CHECK: *:(.got.plt ) +CHECK: *:(.igot.plt ) +CHECK: } +CHECK: .lrodata (ALIGN(CONSTANT(MAXPAGESIZE)) + (. & (CONSTANT(MAXPAGESIZE) - 1))) : +CHECK: { +CHECK: *:(.lrodata .lrodata.* .gnu.linkonce.lr.* ) +CHECK: } +CHECK: .ldata (ALIGN(CONSTANT(MAXPAGESIZE)) + (. & (CONSTANT(MAXPAGESIZE) - 1))) : +CHECK: { +CHECK: *:(.ldata .ldata.* .gnu.linkonce.l.* ) +CHECK: . = ALIGN((. != 0) ? (64 / 8) : 1) +CHECK: } +CHECK: . = ALIGN((64 / 8)) +CHECK: _end = . +CHECK: PROVIDE(end = .) +CHECK: . = DATA_SEGMENT_END(.) +CHECK: : +CHECK: { +CHECK: *:(.note.GNU-stack ) +CHECK: *:(.gnu_debuglink ) +CHECK: *:(.gnu.lto_* ) +CHECK: } +CHECK: } +*/