[lld] Teach LLD how to parse complete linker scripts

[rafaelauler]

Summary

This patch does *not* implement any semantic actions, but it is a first step to
teach LLD how to read complete linker scripts. The additional linker scripts
statements whose parsing is now supported are:

• SEARCH_DIR directive
• SECTIONS directive
• Symbol definitions inside SECTIONS including PROVIDE and PROVIDE_HIDDEN
• C-like expressions used in many places in linker scripts
• Input to output sections mapping

The goal of this patch was guided towards completely parsing a default GNU ld
linker script and the linker script used to link the FreeBSD kernel. Thus, it
also adds a test case based on the default linker script used in GNU ld for
x86_64 ELF targets.

Note: Sorry for the size of this patch. I started with the goal of incrementally
developing this parser but ultimately failed. On the other side, the logic of the
parser is kind of repetitive, as one would expect, so this patch does not feature
lots of new things.

[rafaelauler]

Forgot to add llvm-commits to subscribers. Opened a new revision and added it.

[ruiu]

Because this is a large patch, it'll take some time to review.
Let me send out my first comment in the meantime.

include/lld/ReaderWriter/LinkerScript.h

402

Is there any reason to have these member functions to mutate object's fields? It seems to me that we can make the constructor to take all these values. If we do so, we can handle all BinOps as const, which helps readers to understand the code.

The same comments are applied to all other classes representing ast nodes.

[rafaelauler]

Hi Ruiu, sorry, I messed up this revision because I forgot to add llvm-commits to subscribers. I opened a new one in D5852, I will answer will question there. Thanks for sharing your opinion.

include/lld/ReaderWriter/LinkerScript.h

 namespace lld {
 namespace script {
 class Token {
 public:
   enum Kind {
     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) {}
   Token(StringRef range, Kind kind) : _range(range), _kind(kind) {}
 
   void dump(raw_ostream &os) const;
 
   StringRef _range;
   Kind _kind;
 };
 
 class Lexer {
 public:
-  explicit Lexer(std::unique_ptr<MemoryBuffer> mb)
-      : _buffer(mb->getBuffer()) {
+  explicit Lexer(std::unique_ptr<MemoryBuffer> mb) : _buffer(mb->getBuffer()) {
     _sourceManager.AddNewSourceBuffer(std::move(mb), llvm::SMLoc());
   }
 
   void lex(Token &tok);
 
   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();
 
   Token _current;
   /// \brief The current buffer state.
   StringRef _buffer;
   // Lexer owns the input files.
   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; }
 
   virtual void dump(raw_ostream &os) const = 0;
 
   virtual ~Command() {}
 
 protected:
struct Path {
 
   Path() : _asNeeded(false), _isDashlPrefix(false) {}
   explicit Path(StringRef path, bool asNeeded = false, bool isLib = false)
       : _path(path), _asNeeded(asNeeded), _isDashlPrefix(isLib) {}
 };
 
 class Group : public Command {
 public:
-  template <class RangeT>
-  explicit Group(RangeT range) : Command(Kind::Group) {
+  template <class RangeT> explicit Group(RangeT range) : Command(Kind::Group) {
     std::copy(std::begin(range), std::end(range), std::back_inserter(_paths));
   }
 
   static bool classof(const Command *c) { return c->getKind() == Kind::Group; }
 
   void dump(raw_ostream &os) const override {
     os << "GROUP(";
     bool first = true;
public:
   const std::vector<Path> &getPaths() const { return _paths; }
 
 private:
   std::vector<Path> _paths;
 };
 
 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() : Expression(Kind::Constant), _num(0) {}
+  void setNumber(uint64_t num) { _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() : Expression(Kind::Symbol) {}
+  void setName(StringRef name) { _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:
+  FunctionCall() : Expression(Kind::FunctionCall) {}
+  void setName(StringRef name) { _name = name; }
+  void addParam(const Expression *expr) { _arg.push_back(expr); }
+
+  bool isLastParamValid() const { return _arg.back() != nullptr; }
+
+  void dump(raw_ostream &os) const override;
+
+  static bool classof(const Expression *c) {
+    return c->getKind() == Kind::FunctionCall;
+  }
+
+private:
+  StringRef _name;
+  std::vector<const Expression *> _arg;
+};
+
+class BinOp : public Expression {
+public:
+  enum Operation {
+    Sum,
+    Sub,
+    Mul,
+    Div,
+    Shl,
+    Shr,
+    And,
+    Or,
+    CompareLess,
+    CompareGreater,
+    CompareLessEqual,
+    CompareGreaterEqual,
+    CompareEqual,
+    CompareDifferent
+  };
+
+  BinOp() : Expression(Kind::BinOp), _op(Sum), _LHS(nullptr), _RHS(nullptr) {}
+  void setOperation(Operation op) { _op = op; }
+  void setLHS(const Expression *LHS) { _LHS = LHS; }
+  void setRHS(const Expression *RHS) { _RHS = RHS; }
+  bool isLHSValid() const { return _LHS != nullptr; }
+  bool isRHSValid() const { return _RHS != nullptr; }
+  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()
+      : Expression(Kind::TernaryConditional), _conditional(nullptr),
+        _trueExpr(nullptr), _falseExpr(nullptr) {}
+
+  void setConditional(const Expression *conditional) {
+    _conditional = conditional;
+  }
+  void setTrueExpr(const Expression *trueExpr) { _trueExpr = trueExpr; }
+  void setFalseExpr(const Expression *falseExpr) { _falseExpr = falseExpr; }
+
+  bool isConditionalValid() const { return _conditional != nullptr; }
+  bool isTrueExprValid() const { return _trueExpr != nullptr; }
+  bool isFalseExprValid() const { return _falseExpr != nullptr; }
+
+  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 = <expression>" 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()
+      : Command(Kind::SymbolAssignment), _expression(nullptr),
+        _assignmentKind(Simple), _assignmentVisibility(Normal) {}
+
+  static bool classof(const Command *c) {
+    return c->getKind() == Kind::SymbolAssignment;
+  }
+
+  void dump(raw_ostream &os) const override;
+
+  void setSymbol(StringRef name) { _symbol = name; }
+  void setAssignmentKind(AssignmentKind kind) { _assignmentKind = kind; }
+  void setAssignmentVisibility(AssignmentVisibility visibility) {
+    _assignmentVisibility = visibility;
+  }
+  void setExpression(const Expression *expr) { _expression = expr; }
+  bool isExpressionValid() const { return _expression != nullptr; }
+
+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()
+      : InputSection(Kind::InputSectionName), _excludeFile(false) {}
+
+  void dump(raw_ostream &os) const override;
+  void setName(StringRef name) { _name = name; }
+  void setExcludeFile(bool val) { _excludeFile = val; }
+
+  static bool classof(const InputSection *c) {
+    return c->getKind() == Kind::InputSectionName;
+  }
+
+private:
+  StringRef _name;
+  bool _excludeFile;
+};
+
+class InputSectionSortedGroup : public InputSection {
+public:
+  InputSectionSortedGroup()
+      : InputSection(Kind::SortedGroup), _sortMode(WSM_NA) {}
+
+  void dump(raw_ostream &os) const override;
+  void setSortMode(WildcardSortMode sort) { _sortMode = sort; }
+  WildcardSortMode getSortMode() const { return _sortMode; }
+
+  void addInputSection(const InputSection *inputSection) {
+    _sections.push_back(inputSection);
+  }
+
+  static bool classof(const InputSection *c) {
+    return c->getKind() == Kind::SortedGroup;
+  }
+
+private:
+  WildcardSortMode _sortMode;
+  std::vector<const InputSection *> _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<const InputSection *> VectorTy;
+
+  InputSectionFile()
+      : Command(Kind::InputSectionFile), _keep(false), _fileSortMode(WSM_NA),
+        _archiveSortMode(WSM_NA) {}
+
+  void dump(raw_ostream &os) const override;
+
+  void setFileName(StringRef name) { _fileName = name; }
+  void setArchiveName(StringRef name) { _archiveName = name; }
+  void setFileNameSortMode(WildcardSortMode sortMode) {
+    _fileSortMode = sortMode;
+  }
+  void setArchiveNameSortMode(WildcardSortMode sortMode) {
+    _archiveSortMode = sortMode;
+  }
+  void setKeep(bool val) { _keep = val; }
+
+  void addInputSection(const InputSection *inputSection) {
+    _sections.push_back(inputSection);
+  }
+
+  void addRange(VectorTy &range) {
+    _sections.insert(_sections.end(), range.begin(), range.end());
+  }
+
+  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 };
+
+  OutputSectionDescription()
+      : Command(Kind::OutputSectionDescription), _address(nullptr),
+        _align(nullptr), _subAlign(nullptr), _at(nullptr), _fillExpr(nullptr),
+        _alignWithInput(false), _discard(false), _constraint(C_None) {}
+
+  static bool classof(const Command *c) {
+    return c->getKind() == Kind::OutputSectionDescription;
+  }
+
+  void dump(raw_ostream &os) const override;
+
+  void setDiscarded() { _discard = true; }
+  void setSectionName(StringRef name) { _sectionName = name; }
+  void setAlignWithInput() { _alignWithInput = true; }
+  void setConstraint(Constraint c) { _constraint = c; }
+
+  void setAddress(const Expression *expr) { _address = expr; }
+  void setAlign(const Expression *expr) { _align = expr; }
+  void setSubAlign(const Expression *expr) { _subAlign = expr; }
+  void setAt(const Expression *expr) { _at = expr; }
+  void setFillExpr(const Expression *expr) { _fillExpr = expr; }
+
+  void addCommand(const Command *cmd) { _outputSectionCommands.push_back(cmd); }
+
+  bool isLastCommandValid() const {
+    if (!_outputSectionCommands.size())
+      return false;
+    return _outputSectionCommands.back() != nullptr;
+  }
+
+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<const Command *> _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:
+  Sections() : Command(Kind::Sections) {}
+
+  static bool classof(const Command *c) {
+    return c->getKind() == Kind::Sections;
+  }
+
+  void dump(raw_ostream &os) const override;
+
+  void addCommand(const Command *cmd) { _sectionsCommands.push_back(cmd); }
+
+  bool isLastCommandValid() const {
+    if (!_sectionsCommands.size())
+      return false;
+    return _sectionsCommands.back() != nullptr;
+  }
+
+private:
+  std::vector<const Command *> _sectionsCommands;
+};
+
+/// Stores the parse tree of a linker script.
 class LinkerScript {
 public:
   void dump(raw_ostream &os) const {
     for (const Command *c : _commands)
       c->dump(os);
   }
 
   std::vector<Command *> _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<Token, 4> 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()),
   }
 
   bool expectAndConsume(Token::Kind kind, Twine msg) {
     if (_tok._kind != kind) {
       error(_tok, msg);
       return false;
     }
     consumeToken();
     return true;
   }
 
   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();
+
+  /// 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
+  //
+  // All of the member functions below parse either an expression operand or
+  // an operator of the given precedence or below.
+  const Expression *parseTerminalOrOpPrec3();
+  const Expression *parseTerminalOrOpPrec4();
+  const Expression *parseTerminalOrOpPrec5();
+  const Expression *parseTerminalOrOpPrec6();
+  const Expression *parseTerminalOrOpPrec7();
+  const Expression *parseTerminalOrOpPrec8();
+  const Expression *parseTerminalOrOpPrec10();
+  const Expression *parseTerminalOrOpPrec13();
+
+  // All of the member functions below parse an operator of a specific
+  // precedence.
+
+  /// Parse mul/div
+  const Expression *parseOpPrecedence3(const Expression *LHS);
+
+  /// Parse add/sub
+  const Expression *parseOpPrecedence4(const Expression *LHS);
+
+  /// Parse bitwise left shift and right shift
+  const Expression *parseOpPrecedence5(const Expression *LHS);
+
+  /// Parse relational operators <, <=, > and >=
+  const Expression *parseOpPrecedence6(const Expression *LHS);
+
+  /// Parse relational operators == and !=
+  const Expression *parseOpPrecedence7(const Expression *LHS);
+
+  /// Parse bitwise AND
+  const Expression *parseOpPrecedence8(const Expression *LHS);
+
+  /// Parse bitwise OR
+  const Expression *parseOpPrecedence10(const Expression *LHS);
+
+  /// Parse ternary conditionals such as "(condition)? true: false;"
+  const Expression *parseOpPrecedence13(const Expression *LHS);
+
+  /// Entry point for expression parsing, calls all functions above accordingly
+  const Expression *parseExpression();
+
+  // ==== 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<Path> &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<InputSectionFile::VectorTy> 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<Token, 1> _lookAheadBuf;
 };
 } // end namespace script
 } // end namespace lld
 
 #endif

lib/ReaderWriter/LinkerScript.cpp

 //===----------------------------------------------------------------------===//
 
 #include "lld/ReaderWriter/LinkerScript.h"
 
 namespace lld {
 namespace script {
 void Token::dump(raw_ostream &os) const {
   switch (_kind) {
-#define CASE(name)                              \
-  case Token::name:                             \
-    os << #name ": ";                           \
+#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<uint64_t> parseDecimal(StringRef str) {
+  uint64_t res = 0;
+  for (auto &c : str) {
+    res *= 10;
+    if (c < '0' || c > '9')
+      return llvm::ErrorOr<uint64_t>(std::make_error_code(std::errc::io_error));
+    res += c - '0';
+  }
+  return llvm::ErrorOr<uint64_t>(res);
+}
+
+static llvm::ErrorOr<uint64_t> parseOctal(StringRef str) {
+  uint64_t res = 0;
+  for (auto &c : str) {
+    res <<= 3;
+    if (c < '0' || c > '7')
+      return llvm::ErrorOr<uint64_t>(std::make_error_code(std::errc::io_error));
+    res += c - '0';
+  }
+  return llvm::ErrorOr<uint64_t>(res);
+}
+
+static llvm::ErrorOr<uint64_t> parseBinary(StringRef str) {
+  uint64_t res = 0;
+  for (auto &c : str) {
+    res <<= 1;
+    if (c != '0' && c != '1')
+      return llvm::ErrorOr<uint64_t>(std::make_error_code(std::errc::io_error));
+    res += c - '0';
+  }
+  return llvm::ErrorOr<uint64_t>(res);
+}
+
+static llvm::ErrorOr<uint64_t> 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<uint64_t>(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<uint64_t>(res);
+}
+
+static llvm::ErrorOr<uint64_t> parseNum(StringRef str) {
+  bool suffixK = false;
+  bool suffixM = false;
+  enum NumKind { decimal, hex, octal, binary };
+  NumKind kind = llvm::StringSwitch<NumKind>(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<uint64_t> 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':
   case 'H': case 'I': case 'J': case 'K': case 'L': case 'M': case 'N':
   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 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'g':
   case 'h': case 'i': case 'j': case 'k': case 'l': case 'm': case 'n':
   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;
   }
 }
 
 bool Lexer::canContinueName(char c) const {
   switch (c) {
void Lexer::lex(Token &tok) {
   case '(':
     tok = Token(_buffer.substr(0, 1), Token::l_paren);
     _buffer = _buffer.drop_front();
     return;
   case ')':
     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;
-  default:
-    // Handle quoted strings. They are treated as identifiers for
-    // simplicity.
-    if ((_buffer[0] == '\"') || (_buffer[0] == '\'')) {
-      char c = _buffer[0];
+  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();
-      auto quotedStringEnd = _buffer.find(c);
-      if (quotedStringEnd == StringRef::npos || quotedStringEnd == 0)
-        break;
-      StringRef word = _buffer.substr(0, quotedStringEnd);
-      tok = Token(word, Token::identifier);
-      _buffer = _buffer.drop_front(quotedStringEnd + 1);
       return;
     }
     // -l<lib name>
-    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.
-        break;
-      auto libNameEnd =
-          std::find_if(_buffer.begin() + start + 1, _buffer.end(),
+    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;
-    }
-    /// keyword or identifer.
-    if (!canStartName(_buffer[0]))
+  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.
+    if ((_buffer[0] == '\"') || (_buffer[0] == '\'')) {
+      char c = _buffer[0];
+      _buffer = _buffer.drop_front();
+      auto quotedStringEnd = _buffer.find(c);
+      if (quotedStringEnd == StringRef::npos || quotedStringEnd == 0)
         break;
-    auto endIter =
-        std::find_if(_buffer.begin() + 1, _buffer.end(), [=](char c) {
-      return !canContinueName(c);
+      StringRef word = _buffer.substr(0, quotedStringEnd);
+      tok = Token(word, Token::identifier);
+      _buffer = _buffer.drop_front(quotedStringEnd + 1);
+      return;
+    }
+    // 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
+      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);
+      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;
+    }
+    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);
     if (end == StringRef::npos || end == 0)
       break;
     StringRef word = _buffer.substr(0, end);
-    Token::Kind kind = llvm::StringSwitch<Token::Kind>(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<Token::Kind>(word)
+            .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)
     tok = Token(word, kind);
     _buffer = _buffer.drop_front(end);
     return;
   }
   tok = Token(_buffer.substr(0, 1), Token::unknown);
   _buffer = _buffer.drop_front();
 }
 
case '/':
         return;
       break;
     default:
       return;
     }
   }
 }
 
+// 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 = _arg.size()) {
+    _arg[0]->dump(os);
+    for (unsigned i = 1; i != e; ++i) {
+      os << ", ";
+      _arg[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 {
+  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 << "  }";
+}
+
+// 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);
   // Parse top level commands.
   while (true) {
     switch (_tok._kind) {
     case Token::eof:
       return &_script;
+    case Token::semicolon:
+      consumeToken();
+      break;
     case Token::kw_output_format: {
       auto outputFormat = parseOutputFormat();
       if (!outputFormat)
         return nullptr;
       _script._commands.push_back(outputFormat);
       break;
     }
     case Token::kw_output_arch: {
       auto outputArch = parseOutputArch();
       if (!outputArch)
         return nullptr;
       _script._commands.push_back(outputArch);
       break;
     }
     case Token::kw_group: {
       auto group = parseGroup();
       if (!group)
         return nullptr;
       _script._commands.push_back(group);
       break;
     }
     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();
       if (!entry)
         return nullptr;
       _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.
-      return nullptr;
-    }
-  }
+      error(_tok, "Unrecognized token.");
+      return nullptr;
+    }
+  }
+
+  return nullptr;
+}
+
+const Expression *Parser::parseFunctionCall() {
+  assert((_tok._kind == Token::identifier || _tok._kind == Token::kw_align) &&
+         "expected function call first tokens");
+  FunctionCall *fun = new (_alloc) FunctionCall();
+
+  fun->setName(_tok._range);
+  consumeToken();
+  if (!expectAndConsume(Token::l_paren, "expected ("))
+    return nullptr;
+
+  if (_tok._kind == Token::r_paren) {
+    consumeToken();
+    return fun;
+  }
+
+  fun->addParam(parseExpression());
+
+  if (!fun->isLastParamValid())
+    return nullptr;
+
+  while (_tok._kind == Token::comma) {
+    consumeToken();
+    fun->addParam(parseExpression());
+    if (!fun->isLastParamValid())
+      return nullptr;
+  }
+
+  if (!expectAndConsume(Token::r_paren, "expected )"))
+    return nullptr;
+  return fun;
+}
+
+const Expression *Parser::parseExprTerminal() {
+  assert((_tok._kind == Token::identifier || _tok._kind == Token::number ||
+          _tok._kind == Token::kw_align || _tok._kind == Token::l_paren) &&
+         "Expected symbol or number!");
+
+  switch (_tok._kind) {
+  case Token::identifier:
+    switch (peek(1)._kind) {
+    case Token::l_paren:
+      return parseFunctionCall();
+    default: {
+      Symbol *sym = new (_alloc) Symbol();
+      sym->setName(_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();
+    c->setNumber(*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");
+  }
+}
+
+const Expression *Parser::parseTerminalOrOpPrec3() {
+  assert((_tok._kind == Token::identifier || _tok._kind == Token::number ||
+          _tok._kind == Token::kw_align || _tok._kind == Token::l_paren) &&
+         "Expected symbol or number!");
+  const Expression *expr = parseExprTerminal();
+  if (!expr)
+    return nullptr;
+
+  switch (_tok._kind) {
+  case Token::star:
+  case Token::slash:
+    return parseOpPrecedence3(expr);
+  default:
+    return expr;
+  }
+}
+
+const Expression *Parser::parseTerminalOrOpPrec4() {
+  assert((_tok._kind == Token::identifier || _tok._kind == Token::number ||
+          _tok._kind == Token::kw_align || _tok._kind == Token::l_paren) &&
+         "Expected symbol or number!");
+  const Expression *expr = parseExprTerminal();
+  if (!expr)
+    return nullptr;
+
+  switch (_tok._kind) {
+  case Token::star:
+  case Token::slash:
+    return parseOpPrecedence3(expr);
+  case Token::plus:
+  case Token::minus:
+    return parseOpPrecedence4(expr);
+  default:
+    return expr;
+  }
+}
+
+const Expression *Parser::parseTerminalOrOpPrec5() {
+  assert((_tok._kind == Token::identifier || _tok._kind == Token::number ||
+          _tok._kind == Token::kw_align || _tok._kind == Token::l_paren) &&
+         "Expected symbol or number!");
+  const Expression *expr = parseExprTerminal();
+  if (!expr)
+    return nullptr;
+
+  switch (_tok._kind) {
+  case Token::star:
+  case Token::slash:
+    return parseOpPrecedence3(expr);
+  case Token::plus:
+  case Token::minus:
+    return parseOpPrecedence4(expr);
+  case Token::lessless:
+  case Token::greatergreater:
+    return parseOpPrecedence5(expr);
+  default:
+    return expr;
+  }
+}
+
+const Expression *Parser::parseTerminalOrOpPrec6() {
+  assert((_tok._kind == Token::identifier || _tok._kind == Token::number ||
+          _tok._kind == Token::kw_align || _tok._kind == Token::l_paren) &&
+         "Expected symbol or number!");
+  const Expression *expr = parseExprTerminal();
+  if (!expr)
+    return nullptr;
+
+  switch (_tok._kind) {
+  case Token::star:
+  case Token::slash:
+    return parseOpPrecedence3(expr);
+  case Token::plus:
+  case Token::minus:
+    return parseOpPrecedence4(expr);
+  case Token::lessless:
+  case Token::greatergreater:
+    return parseOpPrecedence5(expr);
+  case Token::lessequal:
+  case Token::greaterequal:
+  case Token::less:
+  case Token::greater:
+    return parseOpPrecedence6(expr);
+  default:
+    return expr;
+  }
+}
+
+const Expression *Parser::parseTerminalOrOpPrec7() {
+  assert((_tok._kind == Token::identifier || _tok._kind == Token::number ||
+          _tok._kind == Token::kw_align || _tok._kind == Token::l_paren) &&
+         "Expected symbol or number!");
+  const Expression *expr = parseExprTerminal();
+  if (!expr)
+    return nullptr;
+
+  switch (_tok._kind) {
+  case Token::star:
+  case Token::slash:
+    return parseOpPrecedence3(expr);
+  case Token::plus:
+  case Token::minus:
+    return parseOpPrecedence4(expr);
+  case Token::lessless:
+  case Token::greatergreater:
+    return parseOpPrecedence5(expr);
+  case Token::lessequal:
+  case Token::greaterequal:
+  case Token::less:
+  case Token::greater:
+    return parseOpPrecedence6(expr);
+  case Token::equalequal:
+  case Token::exclaimequal:
+    return parseOpPrecedence7(expr);
+  default:
+    return expr;
+  }
+}
+
+const Expression *Parser::parseTerminalOrOpPrec8() {
+  assert((_tok._kind == Token::identifier || _tok._kind == Token::number ||
+          _tok._kind == Token::kw_align || _tok._kind == Token::l_paren) &&
+         "Expected symbol or number!");
+  const Expression *expr = parseExprTerminal();
+  if (!expr)
+    return nullptr;
+
+  switch (_tok._kind) {
+  case Token::star:
+  case Token::slash:
+    return parseOpPrecedence3(expr);
+  case Token::plus:
+  case Token::minus:
+    return parseOpPrecedence4(expr);
+  case Token::lessless:
+  case Token::greatergreater:
+    return parseOpPrecedence5(expr);
+  case Token::lessequal:
+  case Token::greaterequal:
+  case Token::less:
+  case Token::greater:
+    return parseOpPrecedence6(expr);
+  case Token::equalequal:
+  case Token::exclaimequal:
+    return parseOpPrecedence7(expr);
+  case Token::amp:
+    return parseOpPrecedence8(expr);
+  default:
+    return expr;
+  }
+}
+
+const Expression *Parser::parseTerminalOrOpPrec10() {
+  assert((_tok._kind == Token::identifier || _tok._kind == Token::number ||
+          _tok._kind == Token::kw_align || _tok._kind == Token::l_paren) &&
+         "Expected symbol or number!");
+  const Expression *expr = parseExprTerminal();
+  if (!expr)
+    return nullptr;
+
+  switch (_tok._kind) {
+  case Token::star:
+  case Token::slash:
+    return parseOpPrecedence3(expr);
+  case Token::plus:
+  case Token::minus:
+    return parseOpPrecedence4(expr);
+  case Token::lessless:
+  case Token::greatergreater:
+    return parseOpPrecedence5(expr);
+  case Token::lessequal:
+  case Token::greaterequal:
+  case Token::less:
+  case Token::greater:
+    return parseOpPrecedence6(expr);
+  case Token::equalequal:
+  case Token::exclaimequal:
+    return parseOpPrecedence7(expr);
+  case Token::amp:
+    return parseOpPrecedence8(expr);
+  case Token::pipe:
+    return parseOpPrecedence10(expr);
+  default:
+    return expr;
+  }
+}
+
+const Expression *Parser::parseTerminalOrOpPrec13() {
+  assert((_tok._kind == Token::identifier || _tok._kind == Token::number ||
+          _tok._kind == Token::kw_align || _tok._kind == Token::l_paren) &&
+         "Expected symbol or number!");
+  const Expression *expr = parseExprTerminal();
+  if (!expr)
+    return nullptr;
+
+  switch (_tok._kind) {
+  case Token::star:
+  case Token::slash:
+    return parseOpPrecedence3(expr);
+  case Token::plus:
+  case Token::minus:
+    return parseOpPrecedence4(expr);
+  case Token::lessless:
+  case Token::greatergreater:
+    return parseOpPrecedence5(expr);
+  case Token::lessequal:
+  case Token::greaterequal:
+  case Token::less:
+  case Token::greater:
+    return parseOpPrecedence6(expr);
+  case Token::equalequal:
+  case Token::exclaimequal:
+    return parseOpPrecedence7(expr);
+  case Token::amp:
+    return parseOpPrecedence8(expr);
+  case Token::pipe:
+    return parseOpPrecedence10(expr);
+  case Token::question:
+    return parseOpPrecedence13(expr);
+  default:
+    return expr;
+  }
+}
+
+const Expression *Parser::parseOpPrecedence3(const Expression *LHS) {
+  assert((_tok._kind == Token::star || _tok._kind == Token::slash) &&
+         "Expected star or slash");
+  BinOp *binOp = new (_alloc) BinOp();
+  binOp->setLHS(LHS);
+  switch (_tok._kind) {
+  case Token::star:
+    binOp->setOperation(BinOp::Mul);
+    break;
+  case Token::slash:
+    binOp->setOperation(BinOp::Div);
+    break;
+  default:
+    llvm_unreachable("Unknown token");
+  }
+  consumeToken();
+
+  const Expression *RHS = parseExprTerminal();
+  if (!RHS)
+    return nullptr;
+  binOp->setRHS(RHS);
+
+  switch (_tok._kind) {
+  case Token::star:
+  case Token::slash:
+    return parseOpPrecedence3(binOp);
+  default:
+    return binOp;
+  }
+}
+
+const Expression *Parser::parseOpPrecedence4(const Expression *LHS) {
+  assert((_tok._kind == Token::plus || _tok._kind == Token::minus) &&
+         "Expected plus or minus");
+  BinOp *binOp = new (_alloc) BinOp();
+  binOp->setLHS(LHS);
+  switch (_tok._kind) {
+  case Token::plus:
+    binOp->setOperation(BinOp::Sum);
+    break;
+  case Token::minus:
+    binOp->setOperation(BinOp::Sub);
+    break;
+  default:
+    llvm_unreachable("Unknown token");
+  }
+  consumeToken();
+
+  const Expression *RHS = parseTerminalOrOpPrec3();
+  if (!RHS)
+    return nullptr;
+  binOp->setRHS(RHS);
+
+  switch (_tok._kind) {
+  case Token::plus:
+  case Token::minus:
+    return parseOpPrecedence4(binOp);
+  default:
+    return binOp;
+  }
+}
+
+const Expression *Parser::parseOpPrecedence5(const Expression *LHS) {
+  assert(
+      (_tok._kind == Token::lessless || _tok._kind == Token::greatergreater) &&
+      "Expected << or >>");
+  BinOp *binOp = new (_alloc) BinOp();
+  binOp->setLHS(LHS);
+  switch (_tok._kind) {
+  case Token::lessless:
+    binOp->setOperation(BinOp::Shl);
+    break;
+  case Token::greatergreater:
+    binOp->setOperation(BinOp::Shr);
+    break;
+  default:
+    llvm_unreachable("Unknown token");
+  }
+  consumeToken();
+
+  const Expression *RHS = parseTerminalOrOpPrec4();
+  if (!RHS)
+    return nullptr;
+  binOp->setRHS(RHS);
+
+  switch (_tok._kind) {
+  case Token::lessless:
+  case Token::greatergreater:
+    return parseOpPrecedence5(binOp);
+  default:
+    return binOp;
+  }
+}
+
+const Expression *Parser::parseOpPrecedence6(const Expression *LHS) {
+  assert((_tok._kind == Token::less || _tok._kind == Token::greater ||
+          _tok._kind == Token::lessequal ||
+          _tok._kind == Token::greaterequal) &&
+         "Expected <, <=, > or >=");
+  BinOp *binOp = new (_alloc) BinOp();
+  binOp->setLHS(LHS);
+  switch (_tok._kind) {
+  case Token::less:
+    binOp->setOperation(BinOp::CompareLess);
+    break;
+  case Token::greater:
+    binOp->setOperation(BinOp::CompareGreater);
+    break;
+  case Token::lessequal:
+    binOp->setOperation(BinOp::CompareLessEqual);
+    break;
+  case Token::greaterequal:
+    binOp->setOperation(BinOp::CompareGreaterEqual);
+    break;
+  default:
+    llvm_unreachable("Unknown token");
+  }
+  consumeToken();
+
+  const Expression *RHS = parseTerminalOrOpPrec5();
+  if (!RHS)
+  binOp->setRHS(RHS);
+
+  switch (_tok._kind) {
+  case Token::less:
+  case Token::greater:
+  case Token::lessequal:
+  case Token::greaterequal:
+    return parseOpPrecedence6(binOp);
+  default:
+    return binOp;
 
+const Expression *Parser::parseOpPrecedence7(const Expression *LHS) {
+  assert(
+      (_tok._kind == Token::equalequal || _tok._kind == Token::exclaimequal) &&
+      "Expected == or !=");
+  BinOp *binOp = new (_alloc) BinOp();
+  binOp->setLHS(LHS);
+  switch (_tok._kind) {
+  case Token::equalequal:
+    binOp->setOperation(BinOp::CompareEqual);
+    break;
+  case Token::exclaimequal:
+    binOp->setOperation(BinOp::CompareDifferent);
+    break;
+  default:
+    llvm_unreachable("Unknown token");
+  }
+  consumeToken();
+
+  const Expression *RHS = parseTerminalOrOpPrec6();
+  if (!RHS)
     return nullptr;
+  binOp->setRHS(RHS);
+
+  switch (_tok._kind) {
+  case Token::equalequal:
+  case Token::exclaimequal:
+    return parseOpPrecedence7(binOp);
+  default:
+    return binOp;
+  }
+}
+
+const Expression *Parser::parseOpPrecedence8(const Expression *LHS) {
+  assert(_tok._kind == Token::amp && "Expected amp");
+  BinOp *binOp = new (_alloc) BinOp();
+  binOp->setLHS(LHS);
+  binOp->setOperation(BinOp::And);
+  consumeToken();
+
+  const Expression *RHS = parseTerminalOrOpPrec7();
+  if (!RHS)
+    return nullptr;
+  binOp->setRHS(RHS);
+
+  if (_tok._kind == Token::amp)
+    return parseOpPrecedence8(binOp);
+  return binOp;
+}
+
+const Expression *Parser::parseOpPrecedence10(const Expression *LHS) {
+  assert(_tok._kind == Token::pipe && "Expected pipe");
+  BinOp *binOp = new (_alloc) BinOp();
+  binOp->setLHS(LHS);
+  binOp->setOperation(BinOp::Or);
+  consumeToken();
+
+  const Expression *RHS = parseTerminalOrOpPrec8();
+  if (!RHS)
+    return nullptr;
+  binOp->setRHS(RHS);
+
+  if (_tok._kind == Token::pipe)
+    return parseOpPrecedence10(binOp);
+  return binOp;
+}
+
+const Expression *Parser::parseOpPrecedence13(const Expression *LHS) {
+  assert(_tok._kind == Token::question && "Expected question mark");
+  TernaryConditional *ternaryConditional = new (_alloc) TernaryConditional();
+  ternaryConditional->setConditional(LHS);
+  consumeToken();
+
+  const Expression *trueExpr = parseTerminalOrOpPrec13();
+  if (!trueExpr)
+    return nullptr;
+  ternaryConditional->setTrueExpr(trueExpr);
+
+  if (!expectAndConsume(Token::colon, "expected :"))
+    return nullptr;
+
+  const Expression *falseExpr = parseTerminalOrOpPrec13();
+  if (!falseExpr)
+    return nullptr;
+  ternaryConditional->setFalseExpr(falseExpr);
+
+  return ternaryConditional;
+}
+
+const Expression *Parser::parseExpression() {
+  assert((_tok._kind == Token::identifier || _tok._kind == Token::number ||
+          _tok._kind == Token::kw_align || _tok._kind == Token::l_paren) &&
+         "Expected symbol, number or lparen!");
+  const Expression *expr = parseExprTerminal();
+  if (!expr)
+    return nullptr;
+
+  while (1) {
+    switch (_tok._kind) {
+    case Token::star:
+    case Token::slash:
+      expr = parseOpPrecedence3(expr);
+      break;
+    case Token::plus:
+    case Token::minus:
+      expr = parseOpPrecedence4(expr);
+      break;
+    case Token::lessless:
+    case Token::greatergreater:
+      expr = parseOpPrecedence5(expr);
+      break;
+    case Token::lessequal:
+    case Token::greaterequal:
+    case Token::less:
+    case Token::greater:
+      expr = parseOpPrecedence6(expr);
+      break;
+    case Token::equalequal:
+    case Token::exclaimequal:
+      expr = parseOpPrecedence7(expr);
+      break;
+    case Token::amp:
+      expr = parseOpPrecedence8(expr);
+      break;
+    case Token::pipe:
+      expr = parseOpPrecedence10(expr);
+      break;
+    case Token::question:
+      expr = parseOpPrecedence13(expr);
+      break;
+    default:
+      return expr;
+    }
+  }
 }
 
 // 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;
Entry *Parser::parseEntry() {
   }
   StringRef entryName(_tok._range);
   consumeToken();
   if (!expectAndConsume(Token::r_paren, "expected )"))
     return nullptr;
   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 *assignment = new (_alloc) SymbolAssignment();
+  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:
+      assignment->setAssignmentVisibility(SymbolAssignment::Hidden);
+      break;
+    case Token::kw_provide:
+      assignment->setAssignmentVisibility(SymbolAssignment::Provide);
+      break;
+    case Token::kw_provide_hidden:
+      assignment->setAssignmentVisibility(SymbolAssignment::ProvideHidden);
+      break;
+    default:
+      llvm_unreachable("Unknown token");
+    }
+    ++numParen;
+    consumeToken();
+    if (!expectAndConsume(Token::l_paren, "expected ("))
+      return nullptr;
+  }
+
+  assignment->setSymbol(_tok._range);
+  consumeToken();
+
+  // Parse assignment operator (=, +=, -= etc.)
+  switch (_tok._kind) {
+  case Token::equal:
+    assignment->setAssignmentKind(SymbolAssignment::Simple);
+    consumeToken();
+    break;
+  case Token::plusequal:
+    assignment->setAssignmentKind(SymbolAssignment::Sum);
+    consumeToken();
+    break;
+  case Token::minusequal:
+    assignment->setAssignmentKind(SymbolAssignment::Sub);
+    consumeToken();
+    break;
+  case Token::starequal:
+    assignment->setAssignmentKind(SymbolAssignment::Mul);
+    consumeToken();
+    break;
+  case Token::slashequal:
+    assignment->setAssignmentKind(SymbolAssignment::Div);
+    consumeToken();
+    break;
+  case Token::ampequal:
+    assignment->setAssignmentKind(SymbolAssignment::And);
+    consumeToken();
+    break;
+  case Token::pipeequal:
+    assignment->setAssignmentKind(SymbolAssignment::Or);
+    consumeToken();
+    break;
+  case Token::lesslessequal:
+    assignment->setAssignmentKind(SymbolAssignment::Shl);
+    consumeToken();
+    break;
+  case Token::greatergreaterequal:
+    assignment->setAssignmentKind(SymbolAssignment::Shr);
+    consumeToken();
+    break;
+  default:
+    error(_tok, "unexpected token");
+    return nullptr;
+  }
+
+  switch (_tok._kind) {
+  case Token::number:
+  case Token::kw_align:
+  case Token::identifier:
+  case Token::l_paren:
+    assignment->setExpression(parseExpression());
+    if (!assignment->isExpressionValid()) {
+      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 assignment;
+}
+
+llvm::ErrorOr<InputSectionFile::VectorTy> 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<InputSectionFile::VectorTy>(
+        std::make_error_code(std::errc::io_error));
+
+  while (_tok._kind == Token::identifier) {
+    InputSectionName *input = new (_alloc) InputSectionName();
+    input->setName(_tok._range);
+    input->setExcludeFile(true);
+    res.push_back(input);
+    consumeToken();
+  }
+
+  if (!expectAndConsume(Token::r_paren, "expected )"))
+    return llvm::ErrorOr<InputSectionFile::VectorTy>(
+        std::make_error_code(std::errc::io_error));
+  return llvm::ErrorOr<InputSectionFile::VectorTy>(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!");
+  InputSectionSortedGroup *sortedGroup = new (_alloc) InputSectionSortedGroup();
+
+  WildcardSortMode sortMode = WSM_NA;
+  int numParen = parseSortDirectives(sortMode);
+  if (numParen == -1)
+    return nullptr;
+  sortedGroup->setSortMode(sortMode);
+
+  while (_tok._kind == Token::identifier) {
+    InputSectionName *input = new (_alloc) InputSectionName();
+    input->setExcludeFile(false);
+    input->setName(_tok._range);
+    sortedGroup->addInputSection(input);
+    consumeToken();
+  }
+
+  // Eat "numParen" rparens
+  for (int i = 0, e = numParen; i != e; ++i)
+    if (!expectAndConsume(Token::r_paren, "expected )"))
+      return nullptr;
+
+  return sortedGroup;
+}
+
+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!");
+  InputSectionFile *descr = new (_alloc) InputSectionFile();
+  int numParen = 1;
+
+  if (_tok._kind == Token::kw_keep) {
+    consumeToken();
+    if (!expectAndConsume(Token::l_paren, "expected ("))
+      return nullptr;
+    ++numParen;
+    descr->setKeep(true);
+  }
+
+  // Input name
+  if (_tok._kind != Token::colon) {
+    WildcardSortMode sortMode;
+    int numParen = parseSortDirectives(sortMode);
+    if (numParen == -1)
+      return nullptr;
+    descr->setFileName(_tok._range);
+    consumeToken();
+    if (numParen) {
+      while (numParen--)
+        if (!expectAndConsume(Token::r_paren, "expected )"))
+          return nullptr;
+      descr->setFileNameSortMode(sortMode);
+    }
+  }
+  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) {
+      WildcardSortMode sortMode;
+      int numParen = parseSortDirectives(sortMode);
+      if (numParen == -1)
+        return nullptr;
+      descr->setArchiveName(_tok._range);
+      consumeToken();
+      if (numParen) {
+        while (numParen--)
+          if (!expectAndConsume(Token::r_paren, "expected )"))
+            return nullptr;
+        descr->setArchiveNameSortMode(sortMode);
+      }
+    }
+  }
+
+  if (_tok._kind != Token::l_paren)
+    return descr;
+  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;
+      descr->addRange(*vec);
+      break;
+    }
+    case Token::star:
+    case Token::identifier: {
+      InputSectionName *input = new (_alloc) InputSectionName();
+      input->setName(_tok._range);
+      input->setExcludeFile(false);
+      descr->addInputSection(input);
+      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;
+      descr->addInputSection(group);
+      break;
+    }
+    default:
+      llvm_unreachable("Unknown token");
+    }
+  }
+
+  for (int i = 0; i < numParen; ++i)
+    if (!expectAndConsume(Token::r_paren, "expected )"))
+      return nullptr;
+  return descr;
+}
+
+const OutputSectionDescription *Parser::parseOutputSectionDescription() {
+  assert((_tok._kind == Token::kw_discard || _tok._kind == Token::identifier) &&
+         "Expected /DISCARDED/ or identifier!");
+  OutputSectionDescription *descr = new (_alloc) OutputSectionDescription();
+
+  if (_tok._kind == Token::kw_discard)
+    descr->setDiscarded();
+  else
+    descr->setSectionName(_tok._range);
+  consumeToken();
+
+  if (_tok._kind == Token::number || _tok._kind == Token::identifier ||
+      _tok._kind == Token::kw_align || _tok._kind == Token::l_paren) {
+    const Expression *addr = parseExpression();
+    if (!addr)
+      return nullptr;
+    descr->setAddress(addr);
+  }
+
+  if (!expectAndConsume(Token::colon, "expected :"))
+    return nullptr;
+
+  if (_tok._kind == Token::kw_at) {
+    consumeToken();
+    const Expression *at = parseExpression();
+    if (!at)
+      return nullptr;
+    descr->setAt(at);
+  }
+
+  if (_tok._kind == Token::kw_align) {
+    consumeToken();
+    const Expression *align = parseExpression();
+    if (!align)
+      return nullptr;
+    descr->setAlign(align);
+  }
+
+  if (_tok._kind == Token::kw_align_with_input) {
+    consumeToken();
+    descr->setAlignWithInput();
+  }
+
+  if (_tok._kind == Token::kw_subalign) {
+    consumeToken();
+    const Expression *subalign = parseExpression();
+    if (!subalign)
+      return nullptr;
+    descr->setSubAlign(subalign);
+  }
+
+  if (_tok._kind == Token::kw_only_if_ro) {
+    consumeToken();
+    descr->setConstraint(OutputSectionDescription::C_OnlyIfRO);
+  } else if (_tok._kind == Token::kw_only_if_rw) {
+    consumeToken();
+    descr->setConstraint(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:
+        descr->addCommand(parseSymbolAssignment());
+        if (!descr->isLastCommandValid())
+          return nullptr;
+        break;
+      default:
+        descr->addCommand(parseInputSectionFile());
+        if (!descr->isLastCommandValid())
+          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:
+      descr->addCommand(parseInputSectionFile());
+      if (!descr->isLastCommandValid())
+        return nullptr;
+      break;
+    case Token::kw_hidden:
+    case Token::kw_provide:
+    case Token::kw_provide_hidden:
+      descr->addCommand(parseSymbolAssignment());
+      if (!descr->isLastCommandValid())
+        return nullptr;
+      break;
+    default:
+      error(_tok, "unexpected token while parsing output section description.");
+      return nullptr;
+    }
+  }
+
+  if (!expectAndConsume(Token::r_brace, "expected }"))
+    return nullptr;
+
+  if (_tok._kind == Token::equal) {
+    consumeToken();
+    const Expression *fillExpr = parseExpression();
+    if (!fillExpr)
+      return nullptr;
+    descr->setFillExpr(fillExpr);
+  }
+
+  return descr;
+}
+
+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;
+  Sections *sections = new (_alloc) Sections();
+
+  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:
+        sections->addCommand(parseSymbolAssignment());
+        if (!sections->isLastCommandValid())
+          return nullptr;
+        break;
+      default:
+        sections->addCommand(parseOutputSectionDescription());
+        if (!sections->isLastCommandValid())
+          return nullptr;
+        break;
+      }
+      break;
+
+    case Token::kw_discard:
+    case Token::star:
+      sections->addCommand(parseOutputSectionDescription());
+      if (!sections->isLastCommandValid())
+        return nullptr;
+      break;
+
+    case Token::kw_entry:
+      sections->addCommand(parseEntry());
+      if (!sections->isLastCommandValid())
+        return nullptr;
+      break;
+
+    case Token::kw_hidden:
+    case Token::kw_provide:
+    case Token::kw_provide_hidden:
+      sections->addCommand(parseSymbolAssignment());
+      if (!sections->isLastCommandValid())
+        return nullptr;
+      break;
+
+    case Token::kw_overlay:
+      sections->addCommand(parseOverlay());
+      if (!sections->isLastCommandValid())
+        return nullptr;
+      break;
+
+    default:
+      unrecognizedToken = true;
+      break;
+    }
+  }
+
+  if (!expectAndConsume(Token::r_brace, "expected }"))
+    return nullptr;
+
+  return sections;
+}
+
 } // end namespace script
 } // end namespace lld

test/LinkerScript/sections.test

+/*
+  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: }
+*/