[lld] [LinkerScript] Implement semantics for simple sections mappings

[rafaelauler]

Summary

This patch implements the behaviour of the SECTIONS linker script directive,
used to define a custom mapping between input and output sections. Not all
sections constructs are currently supported, but only the ones that do not
use wildcard matching to define section names and that does not sort or use
any other special feature. This patch also adds support for the evaluation of
linker scripts expressions when used to define a new address for an output
section. I added a LIT test as a practical example of which sections
directives are currently supported.

The strategy employed here to change the layout of the output file based on
the linker script file was based on a suggestion by Shankar and involves
using "rule ids".

We start by assigning each linker script "rule" (a mapping between input and
output section) a "rule id" in an incremental fashion: the first rules have
the lowest ids. Afterwards, in the ELF reader, when creating ELF defined atoms,
I check from which input file and input section this file came from, try to
match a linker script rule against it and assign it a "rule id". When done
reading, we should have a "rule id" for each atom, which is essentially a
different "ordinal" number, but crafted in terms of what the linker script
thinks the order should be.

In terms of high-level changes, I created a new class "script::Sema" that owns
all linker script ASTs and the logic for linker script semantics as well.
ELFLinkingContext owns a single copy of Sema, which will be used throughout
the object file reading process (to assign rule ids to atoms) and writing
process (to layout sections as proposed by the linker script).

Other high-level change is that the writer no longer uses a "const" copy of
the linking context. This happens because linker script expressions must be
calculated *while* calculating final virtual addresses, which is a very late
step in object file writing. While calculating these expressions, we need to
update the linker script symbol table (inside the semantics object), and, thus,
we are "modifying our context" as we prepare to write the file.

[shankarke]

Cool!

Few comments :-

a) We should assign rule id's to Sections, and not to DefinedAtoms.

• The ruleid could be assigned when parsing linker scripts, and you attach a rule id to it.
• DefinedAtoms should not have this extra member ruleid.
• So when the AtomSection is queried for the output section from the LinkerScript datastructure, it would return a tuple that contains the (order_of_outputsection, ruleid).

b) All the linker script matching would be not be done in the DefaultLayout class. ScriptLayout was essentially designed to take advantage of linker scripts.

[ruiu]

I don't understand why you needed to introduce the notion of "rule id" to sort sections in a specific order. What you are trying to do with this patch is to layout sections in an order specified using linker scripts, right? I understand that we need that much code for linker script evaluation because it's a small programming language, but I'm not convinced that attaching a "rule id" to each DefinedAtom helps implementing section ordering.

It seems that we can just have a simple renaming map, which is a map from-sections (e.g. foo.o:.foo) to to-sections (.text), and look up that map in the writer then the writer makes a final decision about which atoms need to be put in which section. At least it seems it should be enough to make the test that you wrote pass.

[shankarke]

Rui,

There are more complicated examples than that where ruleid's are required, It makes the design scale a lot, than keeping more data structures IMO.

For example :

.data : { *(.data1 *.data2 *.data3) } is very hard to implement with one single map.

Say you have say you have two objects 1.o 2.o, which contains data1, data2, data3 as sections.

1.o { data1->a, data2->b, data3->c } and 2.o { data1->d data2->e data2->f }

The (->) corresponds to the section containing the defined atom.

The Layout would need to be a,b,c,d,e,f instead of a,d,b,e,c,f.

Rule id is less costly than using a map IMO.

[ruiu]

This patch contains both a linker script expression evaluator and and a user of that feature. Both are rather large, so maybe I'd split it into two patches. Can you do that? The evaluator can be tested using GnuLdDriverTest.cpp.

[ruiu]

This patch contains both a linker script expression evaluator and and a user of that feature. Both are rather large, so maybe I'd split it into two patches. Can you do that? The evaluator can be tested using GnuLdDriverTest.cpp.

[rafaelauler]

Hi Rui and Shankar,

Thanks for your suggestions, I will work on them. I will also split this
patch, as suggested by Rui.

include/lld/Core/DefinedAtom.h

public:
   /// resulting image is stable and reproducible.
   ///
   /// Note that this should not be confused with ordinals of exported symbols in
   /// Windows DLLs. In Windows terminology, ordinals are symbols' export table
   /// indices (small integers) which can be used instead of symbol names to
   /// refer items in a DLL.
   virtual uint64_t ordinal() const = 0;
 
+  /// \brief returns the linker script rule id that is associeted with this atom
+  ///
+  /// This is used to enforce atom order as imposed by a linker script. Each
+  /// linker script mapping rule gets assigned a rule id. A lower id means
+  /// higher precedence when sorting atoms.
+  virtual uint32_t ruleId() const { return 0; }
+
   /// \brief the number of bytes of space this atom's content will occupy in the
   /// final linked image.
   ///
   /// For a function atom, it is the number of bytes of code in the function.
   virtual uint64_t size() const = 0;
 
   /// \brief The visibility of this atom to other atoms.
   ///

include/lld/Core/Error.h

 inline std::error_code make_error_code(YamlReaderError e) {
   return std::error_code(static_cast<int>(e), YamlReaderCategory());
 }
 
 const std::error_category &LinkerScriptReaderCategory();
 
 enum class LinkerScriptReaderError {
   success = 0,
-  parse_error
+  parse_error,
+  unknown_symbol_in_expr,
+  unrecognized_function_in_expr
 };
 
 inline std::error_code make_error_code(LinkerScriptReaderError e) {
   return std::error_code(static_cast<int>(e), LinkerScriptReaderCategory());
 }
 
 /// Creates an error_code object that has associated with it an arbitrary
 /// error messsage.  The value() of the error_code will always be non-zero

include/lld/ReaderWriter/ELFLinkingContext.h

public:
   /// \brief Strip symbols.
   bool stripSymbols() const { return _stripSymbols; }
   void setStripSymbols(bool strip) { _stripSymbols = strip; }
 
   /// \brief Collect statistics.
   bool collectStats() const { return _collectStats; }
   void setCollectStats(bool s) { _collectStats = s; }
 
-  // We can parse several linker scripts via command line whose ASTs are stored
-  // in the current linking context via addLinkerScript().
-  void addLinkerScript(std::unique_ptr<script::Parser> script) {
-    _scripts.push_back(std::move(script));
-  }
-
   // --wrap option.
   void addWrapForSymbol(StringRef sym) { _wrapCalls.insert(sym); }
 
   const llvm::StringSet<> &wrapCalls() const { return _wrapCalls; }
 
+  script::Sema &linkerScriptSema() { return _linkerScriptSema; }
+
 private:
   ELFLinkingContext() = delete;
 
 protected:
   ELFLinkingContext(llvm::Triple, std::unique_ptr<TargetHandlerBase>);
 
   Writer &writer() const override;
 
protected:
   StringRef _finiFunction;
   StringRef _sysrootPath;
   StringRef _soname;
   StringRefVector _rpathList;
   StringRefVector _rpathLinkList;
   llvm::StringSet<> _wrapCalls;
   std::map<std::string, uint64_t> _absoluteSymbols;
   llvm::StringSet<> _dynamicallyExportedSymbols;
-  std::vector<std::unique_ptr<script::Parser>> _scripts;
+
+  // The linker script semantic object, which owns all script ASTs, is stored
+  // in the current linking context via _linkerScriptSema.
+  script::Sema _linkerScriptSema;
 };
 } // end namespace lld
 
 #endif

include/lld/ReaderWriter/LinkerScript.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_READER_WRITER_LINKER_SCRIPT_H
 #define LLD_READER_WRITER_LINKER_SCRIPT_H
 
 #include "lld/Core/Error.h"
 #include "lld/Core/LLVM.h"
 #include "lld/Core/range.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Support/raw_ostream.h"
 #include <memory>
 #include <system_error>
+#include <unordered_map>
 #include <vector>
 
 namespace lld {
 namespace script {
 class Token {
 public:
   enum Kind {
     unknown,

 ///
 class Command {
 public:
   enum class Kind {
     Entry,
     Group,
     Input,
     InputSectionsCmd,
+    InputSectionName,
     Output,
     OutputArch,
     OutputFormat,
     OutputSectionDescription,
     Overlay,
     SearchDir,
     Sections,
+    SortedGroup,
     SymbolAssignment,
   };
 
   Kind getKind() const { return _kind; }
   inline llvm::BumpPtrAllocator &getAllocator() const;
 
   virtual void dump(raw_ostream &os) const = 0;
 

 ///               | | ^~~~> Constant : Expression
 ///               | |   ^~~~> BinOp : Expression
 ///               ^~~~> Constant : Expression
 ///                 ^~~~> BinOp : Expression  (the top-level Expression node)
 /// }
 ///
 class Expression {
 public:
+  // The symbol table does not need to own its string keys and the use of StringMap
+  // here is an overkill.
+  typedef llvm::StringMap<int64_t, llvm::BumpPtrAllocator> SymbolTableTy;
+
   enum class Kind { Constant, Symbol, FunctionCall, Unary, BinOp,
                     TernaryConditional };
   Kind getKind() const { return _kind; }
   inline llvm::BumpPtrAllocator &getAllocator() const;
   virtual void dump(raw_ostream &os) const = 0;
+  virtual ErrorOr<int64_t> evalExpr(SymbolTableTy &symbolTable) const = 0;
   virtual ~Expression() {}
 
 protected:
   Expression(class Parser &ctx, Kind k) : _ctx(ctx), _kind(k) {}
 
 private:
   Parser &_ctx;
   Kind _kind;
 };
 
 /// A constant value is stored as unsigned because it represents absolute
 /// values. We represent negative numbers by composing the unary '-' operator
 /// with a constant.
 class Constant : public Expression {
 public:
   Constant(Parser &ctx, uint64_t num)
       : Expression(ctx, Kind::Constant), _num(num) {}
   void dump(raw_ostream &os) const override;
 
   static bool classof(const Expression *c) {
     return c->getKind() == Kind::Constant;
   }
 
+  ErrorOr<int64_t> evalExpr(SymbolTableTy &symbolTable) const override {
+    return _num;
+  }
+
 private:
   uint64_t _num;
 };
 
 class Symbol : public Expression {
 public:
   Symbol(Parser &ctx, StringRef name)
       : Expression(ctx, Kind::Symbol), _name(name) {}
   void dump(raw_ostream &os) const override;
 
   static bool classof(const Expression *c) {
     return c->getKind() == Kind::Symbol;
   }
 
+  ErrorOr<int64_t> evalExpr(SymbolTableTy &symbolTable) const override {
+    if (symbolTable.count(_name) == 0)
+      return LinkerScriptReaderError::unknown_symbol_in_expr;
+    return symbolTable[_name];
+  }
+
 private:
   StringRef _name;
 };
 
 class FunctionCall : public Expression {
 public:
   FunctionCall(Parser &ctx, StringRef name,
                const SmallVectorImpl<const Expression *> &args)
       : Expression(ctx, Kind::FunctionCall), _name(name) {
     size_t numArgs = args.size();
     const Expression **argsStart =
         getAllocator().Allocate<const Expression *>(numArgs);
     std::copy(std::begin(args), std::end(args), argsStart);
     _args = llvm::makeArrayRef(argsStart, numArgs);
   }
 
   void dump(raw_ostream &os) const override;
 
   static bool classof(const Expression *c) {
     return c->getKind() == Kind::FunctionCall;
   }
 
+  ErrorOr<int64_t> evalExpr(SymbolTableTy &symbolTable) const override {
+    return LinkerScriptReaderError::unrecognized_function_in_expr;
+  }
+
 private:
   StringRef _name;
   llvm::ArrayRef<const Expression *> _args;
 };
 
 class Unary : public Expression {
 public:
   enum Operation {
     Minus,
     Not
   };
 
   Unary(Parser &ctx, Operation op, const Expression *child)
       : Expression(ctx, Kind::Unary), _op(op), _child(child) {}
   void dump(raw_ostream &os) const override;
 
   static bool classof(const Expression *c) {
     return c->getKind() == Kind::Unary;
   }
 
+  ErrorOr<int64_t> evalExpr(SymbolTableTy &symbolTable) const override {
+    auto child = _child->evalExpr(symbolTable);
+    if (child.getError())
+      return child.getError();
+
+    int64_t childRes = *child;
+    switch(_op) {
+    case Unary::Minus:
+      return 0 - childRes;
+    case Unary::Not:
+      return ~childRes;
+    }
+  }
+
 private:
   Operation _op;
   const Expression *_child;
 };
 
 class BinOp : public Expression {
 public:
   enum Operation {
BinOp(Parser &ctx, const Expression *lhs, Operation op, const Expression *rhs)
       : Expression(ctx, Kind::BinOp), _op(op), _lhs(lhs), _rhs(rhs) {}
 
   void dump(raw_ostream &os) const override;
 
   static bool classof(const Expression *c) {
     return c->getKind() == Kind::BinOp;
   }
 
+  ErrorOr<int64_t> evalExpr(SymbolTableTy &symbolTable) const override {
+    auto lhs = _lhs->evalExpr(symbolTable);
+    if (lhs.getError())
+      return lhs.getError();
+    auto rhs = _rhs->evalExpr(symbolTable);
+    if (rhs.getError())
+      return rhs.getError();
+
+    int64_t lhsRes = *lhs;
+    int64_t rhsRes = *rhs;
+
+    switch(_op) {
+    case And:                 return lhsRes & rhsRes;
+    case CompareDifferent:    return lhsRes != rhsRes;
+    case CompareEqual:        return lhsRes == rhsRes;
+    case CompareGreater:      return lhsRes > rhsRes;
+    case CompareGreaterEqual: return lhsRes >= rhsRes;
+    case CompareLess:         return lhsRes < rhsRes;
+    case CompareLessEqual:    return lhsRes <= rhsRes;
+    case Div:                 return lhsRes / rhsRes;
+    case Mul:                 return lhsRes * rhsRes;
+    case Or:                  return lhsRes | rhsRes;
+    case Shl:                 return lhsRes << rhsRes;
+    case Shr:                 return lhsRes >> rhsRes;
+    case Sub:                 return lhsRes - rhsRes;
+    case Sum:                 return lhsRes + rhsRes;
+    }
+  }
+
 private:
   Operation _op;
   const Expression *_lhs;
   const Expression *_rhs;
 };
 
 /// Operands of the ternary operator can be any expression, similar to the other
 /// operations, including another ternary operator. To disambiguate the parse
TernaryConditional(Parser &ctx, const Expression *conditional,
         _trueExpr(trueExpr), _falseExpr(falseExpr) {}
 
   void dump(raw_ostream &os) const override;
 
   static bool classof(const Expression *c) {
     return c->getKind() == Kind::TernaryConditional;
   }
 
+  ErrorOr<int64_t> evalExpr(SymbolTableTy &symbolTable) const override {
+    auto conditional = _conditional->evalExpr(symbolTable);
+    if (conditional.getError())
+      return conditional.getError();
+    auto trueExpr = _trueExpr->evalExpr(symbolTable);
+    if (trueExpr.getError())
+      return trueExpr.getError();
+    auto falseExpr = _falseExpr->evalExpr(symbolTable);
+    if (falseExpr.getError())
+      return falseExpr.getError();
+
+    int64_t conditionalRes = *conditional;
+    int64_t trueExprRes = *trueExpr;
+    int64_t falseExprRes = *falseExpr;
+    if (conditionalRes)
+      return trueExprRes;
+    else
+      return falseExprRes;
+  }
+
 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.
SymbolAssignment(Parser &ctx, StringRef name, const Expression *expr,
       : Command(ctx, Kind::SymbolAssignment), _expression(expr), _symbol(name),
         _assignmentKind(Simple), _assignmentVisibility(visibility) {}
 
   static bool classof(const Command *c) {
     return c->getKind() == Kind::SymbolAssignment;
   }
 
   void dump(raw_ostream &os) const override;
+  const Expression *expr() const { return _expression; }
+  StringRef symbol() const { return _symbol; }
 
 private:
   const Expression *_expression;
   StringRef _symbol;
   AssignmentKind _assignmentKind;
   AssignmentVisibility _assignmentVisibility;
 };
 

 /// Example:
 ///
 /// SECTIONS {
 ///   .x: { *(.text) }
 ///   /*      ^~~~^         InputSectionName : InputSection  */
 ///   .y: { *(SORT(.text*)) }
 ///   /*      ^~~~~~~~~~~^  InputSectionSortedGroup : InputSection  */
 /// }
-class InputSection {
+class InputSection : public Command {
 public:
-  enum class Kind { InputSectionName, SortedGroup };
-
-  Kind getKind() const { return _kind; }
-  inline llvm::BumpPtrAllocator &getAllocator() const;
-
-  virtual void dump(raw_ostream &os) const = 0;
-
-  virtual ~InputSection() {}
+  static bool classof(const Command *c) {
+    return c->getKind() == Kind::InputSectionName
+      || c->getKind() == Kind::SortedGroup;
+  }
 
 protected:
-  InputSection(Parser &ctx, Kind k) : _ctx(ctx), _kind(k) {}
-
-private:
-  Parser &_ctx;
-  Kind _kind;
+  InputSection(Parser &ctx, Kind k) : Command(ctx, k) {}
 };
 
 class InputSectionName : public InputSection {
 public:
   InputSectionName(Parser &ctx, StringRef name, bool excludeFile)
       : InputSection(ctx, Kind::InputSectionName), _name(name),
         _excludeFile(excludeFile) {}
 
   void dump(raw_ostream &os) const override;
 
-  static bool classof(const InputSection *c) {
+  static bool classof(const Command *c) {
     return c->getKind() == Kind::InputSectionName;
   }
   bool hasExcludeFile() const { return _excludeFile; }
+  StringRef name() const { return _name; }
 
 private:
   StringRef _name;
   bool _excludeFile;
 };
 
 class InputSectionSortedGroup : public InputSection {
 public:
+  typedef llvm::ArrayRef<const InputSection *>::const_iterator const_iterator;
+
   InputSectionSortedGroup(Parser &ctx, WildcardSortMode sort,
                           const SmallVectorImpl<const InputSection *> &sections)
       : InputSection(ctx, Kind::SortedGroup), _sortMode(sort) {
     size_t numSections = sections.size();
     const InputSection **sectionsStart =
         getAllocator().Allocate<const InputSection *>(numSections);
     std::copy(std::begin(sections), std::end(sections), sectionsStart);
     _sections = llvm::makeArrayRef(sectionsStart, numSections);
   }
 
   void dump(raw_ostream &os) const override;
   WildcardSortMode getSortMode() const { return _sortMode; }
 
-  static bool classof(const InputSection *c) {
+  static bool classof(const Command *c) {
     return c->getKind() == Kind::SortedGroup;
   }
 
+  const_iterator begin() const { return _sections.begin(); }
+  const_iterator end() const { return _sections.end(); }
+
 private:
   WildcardSortMode _sortMode;
   llvm::ArrayRef<const InputSection *> _sections;
 };
 
 /// An output-section-command that maps a series of sections inside a given
 /// file-archive pair to an output section.
 /// Example:
 ///
 /// SECTIONS {
 ///   .x: { *(.text) }
 ///   /*    ^~~~~~~^ InputSectionsCmd   */
 ///   .y: { w:z(SORT(.text*)) }
 ///   /*    ^~~~~~~~~~~~~~~~^  InputSectionsCmd  */
 /// }
 class InputSectionsCmd : public Command {
 public:
   typedef std::vector<const InputSection *> VectorTy;
+  typedef llvm::ArrayRef<const InputSection *>::const_iterator const_iterator;
 
   InputSectionsCmd(Parser &ctx, StringRef fileName, StringRef archiveName,
                    bool keep, WildcardSortMode fileSortMode,
                    WildcardSortMode archiveSortMode,
                    const SmallVectorImpl<const InputSection *> &sections)
       : Command(ctx, Kind::InputSectionsCmd), _fileName(fileName),
         _archiveName(archiveName), _keep(keep), _fileSortMode(fileSortMode),
         _archiveSortMode(archiveSortMode) {
     size_t numSections = sections.size();
     const InputSection **sectionsStart =
         getAllocator().Allocate<const InputSection *>(numSections);
     std::copy(std::begin(sections), std::end(sections), sectionsStart);
     _sections = llvm::makeArrayRef(sectionsStart, numSections);
   }
 
   void dump(raw_ostream &os) const override;
 
   static bool classof(const Command *c) {
     return c->getKind() == Kind::InputSectionsCmd;
   }
 
+  StringRef fileName() const { return _fileName; }
+  StringRef archiveName() const { return _archiveName; }
+  const_iterator begin() const { return _sections.begin(); }
+  const_iterator end() const { return _sections.end(); }
+
 private:
   StringRef _fileName;
   StringRef _archiveName;
   bool _keep;
   WildcardSortMode _fileSortMode;
   WildcardSortMode _archiveSortMode;
   llvm::ArrayRef<const InputSection *> _sections;
 };

 /// /*^~~~~~~~~~~~~~~~~~~~~~~~^  OutputSectionDescription  */
 ///   .a 0x10000 : ONLY_IF_RW { *(.data*) ; *:libc.a(SORT(*)); }
 /// /*^~~~~~~~~~~~~  OutputSectionDescription ~~~~~~~~~~~~~~~~~^ */
 /// }
 class OutputSectionDescription : public Command {
 public:
   enum Constraint { C_None, C_OnlyIfRO, C_OnlyIfRW };
 
+  typedef llvm::ArrayRef<const Command *>::const_iterator const_iterator;
+
   OutputSectionDescription(
       Parser &ctx, StringRef sectionName, const Expression *address,
       const Expression *align, const Expression *subAlign, const Expression *at,
       const Expression *fillExpr, StringRef fillStream, bool alignWithInput,
       bool discard, Constraint constraint,
       const SmallVectorImpl<const Command *> &outputSectionCommands)
       : Command(ctx, Kind::OutputSectionDescription), _sectionName(sectionName),
         _address(address), _align(align), _subAlign(subAlign), _at(at),
public:
   }
 
   static bool classof(const Command *c) {
     return c->getKind() == Kind::OutputSectionDescription;
   }
 
   void dump(raw_ostream &os) const override;
 
+  const_iterator begin() const { return _outputSectionCommands.begin(); }
+  const_iterator end() const { return _outputSectionCommands.end(); }
+  StringRef name() const { return _sectionName; }
+
 private:
   StringRef _sectionName;
   const Expression *_address;
   const Expression *_align;
   const Expression *_subAlign;
   const Expression *_at;
   const Expression *_fillExpr;
   StringRef _fillStream;
public:
   }
 
   void dump(raw_ostream &os) const override { os << "Overlay description\n"; }
 };
 
 /// Represents all the contents of the SECTIONS {} construct.
 class Sections : public Command {
 public:
+  typedef llvm::ArrayRef<const Command *>::const_iterator const_iterator;
+
   Sections(Parser &ctx,
            const SmallVectorImpl<const Command *> &sectionsCommands)
       : Command(ctx, Kind::Sections) {
     size_t numCommands = sectionsCommands.size();
     const Command **commandsStart =
         getAllocator().Allocate<const Command *>(numCommands);
     std::copy(std::begin(sectionsCommands), std::end(sectionsCommands),
               commandsStart);
     _sectionsCommands = llvm::makeArrayRef(commandsStart, numCommands);
   }
 
   static bool classof(const Command *c) {
     return c->getKind() == Kind::Sections;
   }
 
   void dump(raw_ostream &os) const override;
 
+  const_iterator begin() const { return _sectionsCommands.begin(); }
+  const_iterator end() const { return _sectionsCommands.end(); }
 private:
   llvm::ArrayRef<const Command *> _sectionsCommands;
 };
 
 /// Stores the parse tree of a linker script.
 class LinkerScript {
 public:
   void dump(raw_ostream &os) const {
private:
   // Current token being analyzed
   Token _tok;
 
   // Annotate whether we buffered the next token to allow peeking
   bool _peekAvailable;
   Token _bufferedToken;
 };
 
+/// script::Sema traverses all parsed linker script structures and assigns an
+/// increasing "rule id" to each input-to-output mapping construct.
+/// This includes:
+///
+///   * OutputSectionDescription, containing an output section name
+///   * InputSectionsCmd, containing an input file name
+///   * InputSectionName, containing a single input section name
+///   * InputSectionSortedName, a group of input section names
+///   * AssignmentExpression, containing an expression that may
+///     change the address where the linker is outputting data
+///
+/// In this way, the sections described first in the linker script will have
+/// lower (higher precedence) ids. Input sections that appear first also have
+/// higher precedence. This allows an order pass to later assign to each atom
+/// a corresponding rule id according to the input file and section where it
+/// came from and then stable-sort all atoms according to their ids. The result
+/// is an output file layout that follows what is described in the linker
+/// script.
+///
+/// In order to easily match atoms with rules ids, we also maintain two string
+/// maps. One matches archive file names to rule ids and the other, input object
+/// file names to rule ids. In this way, we can easily locate the group of input
+/// section names and their respective ids.
+///
+/// Example:
+///
+///  .data :  { input.o(.data .bss) }
+///
+/// The above would be organized in the _rules vector, indexed by rule ids, as
+/// follows:
+///
+///  _rules vector: id 0:  <OutputSectionDescription> (_sectionName = ".data")
+///                 id 1:  <InputSecionsCmd> (_fileName = "input.o")
+///                 id 2:  <InputSectionName> (_name = ".data")
+///                 id 3:  <InputSectionName> (_name = ".bss")
+///
+/// In this scenario, all atoms from input.o:.data gets assigned rule id 1.
+class Sema {
+public:
+  Sema();
+
+  // We can parse several linker scripts via command line whose ASTs are stored
+  // here via addLinkerScript().
+  void addLinkerScript(std::unique_ptr<Parser> script) {
+    _scripts.push_back(std::move(script));
+  }
+
+  std::vector<std::unique_ptr<Parser>> &getLinkerScripts() { return _scripts; }
+
+  void perform() {
+    for (auto &parser : _scripts)
+      assignRuleIds(parser->get());
+  }
+
+  bool hasRules() const { return _rules.size() > 0; }
+  uint32_t lastRuleId() const { return _rules.size(); }
+  bool isLegalRuleId(uint32_t ruleId) const { return ruleId < _rules.size(); }
+
+  uint32_t getRuleId(StringRef archiveName, StringRef fileName,
+                     StringRef sectionName) const {
+    if (archiveName.empty())
+      return getRuleId(fileName, sectionName);
+
+    auto range = _fileToRuleId.equal_range(fileName);
+    for (auto I = range.first, E = range.second; I != E; ++I) {
+      uint32_t id = I->second;
+      const InputSectionsCmd *cmd = dyn_cast<InputSectionsCmd>(_rules[id]);
+      if (!cmd || cmd->archiveName() != archiveName)
+        continue;
+
+      while (++id < _rules.size() && (isa<InputSection>(_rules[id]))) {
+        if (isa<InputSectionSortedGroup>(_rules[id]))
+          continue;
+
+        const InputSectionName *in = dyn_cast<InputSectionName>(_rules[id]);
+        if (in->name() == sectionName)
+          return id;
+      }
+    }
+    return _rules.size();
+  }
+
+  uint32_t getRuleId(StringRef fileName, StringRef sectionName) const {
+    auto range = _fileToRuleId.equal_range(fileName);
+    for (auto I = range.first, E = range.second; I != E; ++I) {
+      uint32_t id = I->second;
+      while (++id < _rules.size() && (isa<InputSection>(_rules[id]))) {
+        if (isa<InputSectionSortedGroup>(_rules[id]))
+          continue;
+
+        const InputSectionName *in = dyn_cast<InputSectionName>(_rules[id]);
+        if (in->name() == sectionName)
+          return id;
+      }
+    }
+    return _rules.size();
+  }
+
+  StringRef getOutputSection(uint32_t ruleId) const {
+    if (ruleId == _rules.size() || ruleId == 0)
+      return StringRef();
+
+    for (int i = ruleId - 1; i >= 0; --i) {
+      if (!isa<OutputSectionDescription>(_rules[i]))
+        continue;
+
+      const OutputSectionDescription *out =
+          dyn_cast<OutputSectionDescription>(_rules[i]);
+      return out->name();
+    }
+
+    return StringRef();
+  }
+
+  std::vector<const SymbolAssignment *> getExprs(uint32_t ruleId) const {
+    auto ans = std::vector<const SymbolAssignment *>();
+
+    if (!isLegalRuleId(ruleId) || ruleId == 0)
+      return ans;
+
+    for (int i = ruleId - 1; i >= 0; --i) {
+      if (isa<InputSection>(_rules[i]))
+        break;
+      if (auto assgn = dyn_cast<SymbolAssignment>(_rules[i]))
+        ans.push_back(assgn);
+    }
+
+    return ans;
+  }
+
+  std::error_code evalExpr(const SymbolAssignment *assgn, uint64_t &curPos) {
+    _symbolTable[StringRef(".")] = curPos;
+
+    auto ans = assgn->expr()->evalExpr(_symbolTable);
+    if (ans.getError())
+      return ans.getError();
+    uint64_t result = *ans;
+
+    if (assgn->symbol() == ".") {
+      curPos = result;
+      return std::error_code();
+    }
+
+    _symbolTable[assgn->symbol()] = result;
+    return std::error_code();
+  }
+
+  void dump() const {
+    raw_ostream &os = llvm::outs();
+    os << "Linker script semantics dump\n";
+    int num = 0;
+    for (auto &parser : _scripts) {
+      os << "Dumping script #" << ++num << ":\n";
+      parser->get()->dump(os);
+      os << "\n";
+    }
+    os << "Dumping rule ids:\n";
+    for (unsigned i = 0; i < _rules.size(); ++i) {
+      os << "RuleId " << i << ":\n";
+      _rules[i]->dump(os);
+      os << "\n\n";
+    }
+  }
+
+private:
+  void assignRuleIds(const InputSection *inputSection) {
+    if (isa<InputSectionName>(inputSection)) {
+      _idMap[inputSection] = _rules.size();
+      _rules.push_back(inputSection);
+      return;
+    }
+
+    auto *sortedGroup = dyn_cast<InputSectionSortedGroup>(inputSection);
+    assert(sortedGroup && "Expected InputSectionSortedGroup object");
+
+    for (const InputSection *child : *sortedGroup) {
+      // FIXME: Implement all SORT* variations
+      assignRuleIds(child);
+    }
+  }
+
+  void assignRuleIds(const InputSectionsCmd *inputSections) {
+    StringRef fileName = inputSections->fileName();
+    if (!fileName.empty())
+      _fileToRuleId.insert(
+          std::make_pair<std::string, uint32_t>(fileName.str(), _rules.size()));
+
+    StringRef archiveName = inputSections->archiveName();
+    if (!archiveName.empty())
+      _archiveToRuleId.insert(std::make_pair<std::string, uint32_t>(
+          archiveName.str(), _rules.size()));
+
+    _idMap[inputSections] = _rules.size();
+    _rules.push_back(inputSections);
+    for (const InputSection *inputSection : *inputSections)
+      assignRuleIds(inputSection);
+  }
+
+  void assignRuleIds(const Sections *sections) {
+    for (const Command *sectionCommand : *sections) {
+      if (isa<SymbolAssignment>(sectionCommand)) {
+        _idMap[sectionCommand] = _rules.size();
+        _rules.push_back(sectionCommand);
+        continue;
+      }
+
+      if (!isa<OutputSectionDescription>(sectionCommand))
+        continue;
+
+      _idMap[sectionCommand] = _rules.size();
+      _rules.push_back(sectionCommand);
+      auto *outSection = dyn_cast<OutputSectionDescription>(sectionCommand);
+
+      for (const Command *outSecCommand : *outSection) {
+        if (isa<SymbolAssignment>(outSecCommand)) {
+          _idMap[outSecCommand] = _rules.size();
+          _rules.push_back(outSecCommand);
+          continue;
+        }
+
+        if (!isa<InputSectionsCmd>(outSecCommand))
+          continue;
+
+        assignRuleIds(dyn_cast<InputSectionsCmd>(outSecCommand));
+      }
+    }
+  }
+
+  void assignRuleIds(const LinkerScript *ls) {
+    for (const Command *c : ls->_commands) {
+      if (!isa<Sections>(c))
+        continue;
+
+      assignRuleIds(dyn_cast<Sections>(c));
+    }
+  }
+
+  std::vector<std::unique_ptr<Parser>> _scripts;
+  std::vector<const Command *> _rules;
+  llvm::DenseMap<const Command *, uint32_t> _idMap;
+  std::unordered_multimap<std::string, uint32_t> _fileToRuleId;
+  std::unordered_multimap<std::string, uint32_t> _archiveToRuleId;
+  Expression::SymbolTableTy _symbolTable;
+};
+
 llvm::BumpPtrAllocator &Command::getAllocator() const {
   return _ctx.getAllocator();
 }
 llvm::BumpPtrAllocator &Expression::getAllocator() const {
   return _ctx.getAllocator();
 }
-llvm::BumpPtrAllocator &InputSection::getAllocator() const {
-  return _ctx.getAllocator();
-}
 } // end namespace script
 } // end namespace lld
 
 #endif

lib/Core/Error.cpp

public:
   }
 
   std::string message(int ev) const override {
     switch (static_cast<LinkerScriptReaderError>(ev)) {
     case LinkerScriptReaderError::success:
       return "Success";
     case LinkerScriptReaderError::parse_error:
       return "Error parsing linker script";
+    case LinkerScriptReaderError::unknown_symbol_in_expr:
+      return "Unknown symbol found when evaluating linker script expression";
+    case LinkerScriptReaderError::unrecognized_function_in_expr:
+      return "Unrecognized function call when evaluating linker script "
+             "expression";
     }
     llvm_unreachable("An enumerator of LinkerScriptReaderError does not have a "
                      "message defined.");
   }
 };
 
 const std::error_category &lld::LinkerScriptReaderCategory() {
   static _LinkerScriptReaderErrorCategory o;

lib/Driver/GnuLdDriver.cpp

if (auto *searchDir = dyn_cast<script::SearchDir>(c))
       if (!nostdlib)
         ctx.addSearchPath(searchDir->getSearchPath());
     if (auto *entry = dyn_cast<script::Entry>(c))
       ctx.setEntrySymbolName(entry->getEntryName());
     if (auto *output = dyn_cast<script::Output>(c))
       ctx.setOutputPath(output->getOutputFileName());
   }
   // Transfer ownership of the script to the linking context
-  ctx.addLinkerScript(std::move(parser));
+  ctx.linkerScriptSema().addLinkerScript(std::move(parser));
   return std::error_code();
 }
 
 bool GnuLdDriver::applyEmulation(llvm::Triple &triple,
                                  llvm::opt::InputArgList &args,
                                  raw_ostream &diag) {
   llvm::opt::Arg *arg = args.getLastArg(OPT_m);
   if (!arg)
default:
       break;
     }
   }
 
   // Validate the combination of options used.
   if (!ctx->validate(diag))
     return false;
 
+  // Perform linker script semantic actions
+  ctx->linkerScriptSema().perform();
+
   context.swap(ctx);
   return true;
 }
 
 /// Get the default target triple based on either the program name
 /// (e.g. "x86-ibm-linux-lld") or the primary target llvm was configured for.
 llvm::Triple GnuLdDriver::getDefaultTarget(const char *progName) {
   SmallVector<StringRef, 4> components;

lib/ReaderWriter/ELF/Atoms.h

 public:
   ELFDefinedAtom(const ELFFile<ELFT> &file, StringRef symbolName,
                  StringRef sectionName, const Elf_Sym *symbol,
                  const Elf_Shdr *section, ArrayRef<uint8_t> contentData,
                  unsigned int referenceStart, unsigned int referenceEnd,
                  std::vector<ELFReference<ELFT> *> &referenceList)
       : _owningFile(file), _symbolName(symbolName), _sectionName(sectionName),
         _symbol(symbol), _section(section), _contentData(contentData),
-        _referenceStartIndex(referenceStart), _referenceEndIndex(referenceEnd),
-        _referenceList(referenceList), _contentType(typeUnknown),
-        _permissions(permUnknown) {}
+        _ruleId(0), _referenceStartIndex(referenceStart),
+        _referenceEndIndex(referenceEnd), _referenceList(referenceList),
+        _contentType(typeUnknown), _permissions(permUnknown) {}
 
   ~ELFDefinedAtom() {}
 
   const ELFFile<ELFT> &file() const override { return _owningFile; }
 
   StringRef name() const override { return _symbolName; }
 
   uint64_t ordinal() const override { return _ordinal; }
 
+  uint32_t ruleId() const override { return _ruleId; }
+
   const Elf_Sym *symbol() const { return _symbol; }
 
   const Elf_Shdr *section() const { return _section; }
 
   uint64_t size() const override {
     // Common symbols are not allocated in object files,
     // so use st_size to tell how many bytes are required.
     if (_symbol && (_symbol->getType() == llvm::ELF::STT_COMMON ||
public:
 
   void addReference(ELFReference<ELFT> *reference) {
     _referenceList.push_back(reference);
     _referenceEndIndex = _referenceList.size();
   }
 
   virtual void setOrdinal(uint64_t ord) { _ordinal = ord; }
 
+  virtual void setRuleId(uint32_t id) { _ruleId = id; }
+
 protected:
   /// Returns correct st_value for the symbol depending on the architecture.
   /// For most architectures it's just a regular st_value with no changes.
   virtual uint64_t getSymbolValue(const Elf_Sym *symbol) const {
     return symbol->st_value;
   }
 
 protected:
   const ELFFile<ELFT> &_owningFile;
   StringRef _symbolName;
   StringRef _sectionName;
   const Elf_Sym *_symbol;
   const Elf_Shdr *_section;
   /// \brief Holds the bits that make up the atom.
   ArrayRef<uint8_t> _contentData;
 
   uint64_t _ordinal;
+  uint32_t _ruleId;
   unsigned int _referenceStartIndex;
   unsigned int _referenceEndIndex;
   std::vector<ELFReference<ELFT> *> &_referenceList;
   mutable ContentType _contentType;
   mutable ContentPermissions _permissions;
 };
 
 /// \brief This atom stores mergeable Strings
 template <class ELFT> class ELFMergeAtom : public DefinedAtom {
   typedef llvm::object::Elf_Shdr_Impl<ELFT> Elf_Shdr;
 
 public:
   ELFMergeAtom(const ELFFile<ELFT> &file, StringRef sectionName,
                const Elf_Shdr *section, ArrayRef<uint8_t> contentData,
                uint64_t offset)
       : _owningFile(file), _sectionName(sectionName), _section(section),
-        _contentData(contentData), _offset(offset) {
+        _contentData(contentData), _ruleId(0), _offset(offset) {
   }
 
   const ELFFile<ELFT> &file() const override { return _owningFile; }
 
   StringRef name() const override { return ""; }
 
   virtual uint64_t section() const { return _section->sh_name; }
 
   virtual uint64_t offset() const { return _offset; }
 
   virtual void setOrdinal(uint64_t ord) { _ordinal = ord; }
 
+  virtual void setRuleId(uint32_t id) { _ruleId = id; }
+
+  uint32_t ruleId() const override { return _ruleId; }
+
   uint64_t ordinal() const override { return _ordinal; }
 
   uint64_t size() const override { return _contentData.size(); }
 
   Scope scope() const override { return scopeTranslationUnit; }
 
   Interposable interposable() const override { return interposeNo; }
 

 private:
 
   const ELFFile<ELFT> &_owningFile;
   StringRef _sectionName;
   const Elf_Shdr *_section;
   /// \brief Holds the bits that make up the atom.
   ArrayRef<uint8_t> _contentData;
   uint64_t _ordinal;
+  uint32_t _ruleId;
   uint64_t _offset;
 };
 
 template <class ELFT> class ELFCommonAtom : public DefinedAtom {
   typedef llvm::object::Elf_Sym_Impl<ELFT> Elf_Sym;
 public:
-  ELFCommonAtom(const ELFFile<ELFT> &file,
-                StringRef symbolName,
+  ELFCommonAtom(const ELFFile<ELFT> &file, StringRef symbolName,
                 const Elf_Sym *symbol)
-      : _owningFile(file),
-        _symbolName(symbolName),
-        _symbol(symbol) {}
+      : _owningFile(file), _symbolName(symbolName), _symbol(symbol),
+        _ruleId(0) {}
 
   const ELFFile<ELFT> &file() const override { return _owningFile; }
 
   StringRef name() const override { return _symbolName; }
 
   uint64_t ordinal() const override { return _ordinal; }
 
+  virtual void setRuleId(uint32_t ruleId) { _ruleId = ruleId; }
+
+  uint32_t ruleId() const override { return _ruleId; }
+
   virtual void setOrdinal(uint64_t ord) { _ordinal = ord; }
 
   uint64_t size() const override { return _symbol->st_size; }
 
   Scope scope() const override {
     if (_symbol->getVisibility() == llvm::ELF::STV_HIDDEN)
       return scopeLinkageUnit;
     else if (_symbol->getBinding() != llvm::ELF::STB_LOCAL)
protected:
   }
 
   void incrementIterator(const void *&iter) const override {}
 
   const ELFFile<ELFT> &_owningFile;
   StringRef _symbolName;
   const Elf_Sym *_symbol;
   uint64_t _ordinal;
+  uint32_t _ruleId;
 };
 
 /// \brief An atom from a shared library.
 template <class ELFT> class ELFDynamicAtom : public SharedLibraryAtom {
   typedef llvm::object::Elf_Sym_Impl<ELFT> Elf_Sym;
 
 public:
   ELFDynamicAtom(const DynamicFile<ELFT> &file, StringRef symbolName,

lib/ReaderWriter/ELF/Chunk.h

 public:
 
   /// \brief Describes the type of Chunk
   enum Kind : uint8_t{ ELFHeader,     ///< ELF Header
                        ProgramHeader, ///< Program Header
                        SectionHeader, ///< Section header
                        ELFSegment,    ///< Segment
                        ELFSection,    ///< Section
-                       AtomSection    ///< A section containing atoms.
+                       AtomSection,   ///< A section containing atoms.
+                       Expression     ///< A linker script expression
   };
   /// \brief the ContentType of the chunk
   enum ContentType : uint8_t{ Unknown, Header, Code, Data, Note, TLS };
 
   Chunk(StringRef name, Kind kind, const ELFLinkingContext &context)
       : _name(name), _kind(kind), _fsize(0), _msize(0), _alignment(0), _order(0),
-        _ordinal(1), _start(0), _fileoffset(0), _context(context) {}
+        _ruleId(0), _ordinal(1), _start(0), _fileoffset(0), _context(context) {}
   virtual ~Chunk() {}
   // The name of the chunk
   StringRef name() const { return _name; }
   // Kind of chunk
   Kind kind() const { return _kind; }
   virtual uint64_t fileSize() const { return _fsize; }
   virtual void setFileSize(uint64_t sz) { _fsize = sz; }
   virtual void setAlign(uint64_t align) { _alignment = align; }
   virtual uint64_t alignment() const { return _alignment; }
 
   // The ordinal value of the chunk
   uint64_t            ordinal() const { return _ordinal;}
   void               setOrdinal(uint64_t newVal) { _ordinal = newVal;}
   // The order in which the chunk would appear in the output file
   uint64_t            order() const { return _order; }
   void               setOrder(uint32_t order) { _order = order; }
+  uint32_t           ruleId() const { return _ruleId; }
+  void               setRuleId(uint32_t ruleId) { _ruleId = ruleId; }
   // Output file offset of the chunk
   uint64_t            fileOffset() const { return _fileoffset; }
   void               setFileOffset(uint64_t offset) { _fileoffset = offset; }
   // Output start address of the chunk
   virtual void setVirtualAddr(uint64_t start) { _start = start; }
   virtual uint64_t virtualAddr() const { return _start; }
   // Memory size of the chunk
   uint64_t memSize() const { return _msize; }

 
 protected:
   StringRef _name;
   Kind _kind;
   uint64_t _fsize;
   uint64_t _msize;
   uint64_t _alignment;
   uint32_t _order;
+  uint32_t _ruleId;
   uint64_t _ordinal;
   uint64_t _start;
   uint64_t _fileoffset;
   const ELFLinkingContext &_context;
 };
 
 } // end namespace elf
 } // end namespace lld
 
 #endif

lib/ReaderWriter/ELF/DefaultLayout.h

struct FindByName {
     FindByName(StringRef name) : _name(name) {}
     bool operator()(const lld::AtomLayout *j) { return j->_atom->name() == _name; }
   };
 
   typedef typename std::vector<lld::AtomLayout *>::iterator AbsoluteAtomIterT;
 
   typedef llvm::DenseSet<const Atom *> AtomSetT;
 
-  DefaultLayout(const ELFLinkingContext &context) : _context(context) {}
+  DefaultLayout(ELFLinkingContext &context) : _context(context),
+    _linkerScriptSema(context.linkerScriptSema()) {}
 
   /// \brief Return the section order for a input section
   SectionOrder getSectionOrder(StringRef name, int32_t contentType,
                                int32_t contentPermissions) override;
 
   /// \brief Return the name of the input section by decoding the input
   /// sectionChoice.
   virtual StringRef getInputSectionName(const DefinedAtom *da) const;
 
   /// \brief Return the name of the output section from the input section.
   virtual StringRef getOutputSectionName(StringRef inputSectionName) const;
 
   /// \brief Gets or creates a section.
   AtomSection<ELFT> *
   getSection(StringRef name, int32_t contentType,
              DefinedAtom::ContentPermissions contentPermissions,
-             StringRef path);
+             const DefinedAtom *da);
 
   /// \brief Gets the segment for a output section
   virtual Layout::SegmentType getSegmentType(Section<ELFT> *section) const;
 
   /// \brief Returns true/false depending on whether the section has a Output
   //         segment or not
   static bool hasOutputSegment(Section<ELFT> *section);
 
public:
 
   void assignVirtualAddress() override;
 
   void assignFileOffsetsForMiscSections();
 
   /// Inline functions
   inline range<AbsoluteAtomIterT> absoluteAtoms() { return _absoluteAtoms; }
 
-  inline void addSection(Chunk<ELFT> *c) {
+  void addSection(Chunk<ELFT> *c) {
+    if (_linkerScriptSema.hasRules()) {
+      if (auto sec = dyn_cast<Section<ELFT>>(c))
+        c->setRuleId(_linkerScriptSema.getRuleId(StringRef("*"),
+                                                 sec->inputSectionName()));
+      else
+        c->setRuleId(_linkerScriptSema.lastRuleId());
+    }
     _sections.push_back(c);
   }
 
   inline void finalize() {
     ScopedTask task(getDefaultDomain(), "Finalize layout");
     for (auto &si : _sections)
       si->finalize();
   }
protected:
   ELFHeader<ELFT> *_elfHeader;
   ProgramHeader<ELFT> *_programHeader;
   LLD_UNIQUE_BUMP_PTR(RelocationTable<ELFT>) _dynamicRelocationTable;
   LLD_UNIQUE_BUMP_PTR(RelocationTable<ELFT>) _pltRelocationTable;
   std::vector<lld::AtomLayout *> _absoluteAtoms;
   AtomSetT _referencedDynAtoms;
   llvm::StringSet<> _copiedDynSymNames;
   const ELFLinkingContext &_context;
+  script::Sema &_linkerScriptSema;
 };
 
 template <class ELFT>
 Layout::SectionOrder DefaultLayout<ELFT>::getSectionOrder(
     StringRef name, int32_t contentType, int32_t contentPermissions) {
   switch (contentType) {
   case DefinedAtom::typeResolver:
   case DefinedAtom::typeCode:
AtomSection<ELFT> *DefaultLayout<ELFT>::createSection(
   return new (_allocator) AtomSection<ELFT>(_context, sectionName, contentType,
                                             permissions, sectionOrder);
 }
 
 template <class ELFT>
 AtomSection<ELFT> *
 DefaultLayout<ELFT>::getSection(StringRef sectionName, int32_t contentType,
                                 DefinedAtom::ContentPermissions permissions,
-                                StringRef path) {
-  const SectionKey sectionKey(sectionName, permissions, path);
-  SectionOrder sectionOrder =
-      getSectionOrder(sectionName, contentType, permissions);
+                                const DefinedAtom *da) {
+  const SectionKey sectionKey(sectionName, permissions, da->file().path());
+  SectionOrder sectionOrder = getSectionOrder(sectionName, contentType, permissions);
   auto sec = _sectionMap.find(sectionKey);
   if (sec != _sectionMap.end())
     return sec->second;
   AtomSection<ELFT> *newSec =
       createSection(sectionName, contentType, permissions, sectionOrder);
-  newSec->setOutputSectionName(getOutputSectionName(sectionName));
+
+  StringRef outputSectionName;
+  if (!_linkerScriptSema.hasRules() ||
+      (outputSectionName = _linkerScriptSema.getOutputSection(da->ruleId())).empty())
+    outputSectionName = getOutputSectionName(sectionName);
+
+  newSec->setOutputSectionName(outputSectionName);
   newSec->setOrder(sectionOrder);
+  if (_linkerScriptSema.hasRules()) {
+    // In atoms, 0 is an invalid rule id (uninitialized)
+    if (da->ruleId() != 0)
+      newSec->setRuleId(da->ruleId());
+    else
+      newSec->setRuleId(_linkerScriptSema.lastRuleId());
+  }
   _sections.push_back(newSec);
   _sectionMap.insert(std::make_pair(sectionKey, newSec));
   return newSec;
 }
 
 template <class ELFT>
 ErrorOr<const lld::AtomLayout *>
 DefaultLayout<ELFT>::addAtom(const Atom *atom) {
   if (const DefinedAtom *definedAtom = dyn_cast<DefinedAtom>(atom)) {
     // HACK: Ignore undefined atoms. We need to adjust the interface so that
     // undefined atoms can still be included in the output symbol table for
     // -noinhibit-exec.
     if (definedAtom->contentType() == DefinedAtom::typeUnknown)
       return make_error_code(llvm::errc::invalid_argument);
     const DefinedAtom::ContentPermissions permissions =
         definedAtom->permissions();
     const DefinedAtom::ContentType contentType = definedAtom->contentType();
 
     StringRef sectionName = getInputSectionName(definedAtom);
-    AtomSection<ELFT> *section = getSection(
-        sectionName, contentType, permissions, definedAtom->file().path());
+    AtomSection<ELFT> *section =
+        getSection(sectionName, contentType, permissions, definedAtom);
 
     // Add runtime relocations to the .rela section.
     for (const auto &reloc : *definedAtom) {
       bool isLocalReloc = true;
       if (_context.isDynamicRelocation(*reloc)) {
         getDynamicRelocationTable()->addRelocation(*definedAtom, *reloc);
         isLocalReloc = false;
       } else if (_context.isPLTRelocation(*reloc)) {

 template <class ELFT> void DefaultLayout<ELFT>::assignSectionsToSegments() {
   ScopedTask task(getDefaultDomain(), "assignSectionsToSegments");
   ELFLinkingContext::OutputMagic outputMagic = _context.getOutputMagic();
   // sort the sections by their order as defined by the layout
   std::stable_sort(_sections.begin(), _sections.end(),
                    [](Chunk<ELFT> *A, Chunk<ELFT> *B) {
     return A->order() < B->order();
   });
+  if (_linkerScriptSema.hasRules()) {
+    // sort the sections by their order as defined by the linker script
+    std::stable_sort(_sections.begin(), _sections.end(),
+                     [](Chunk<ELFT> *A, Chunk<ELFT> *B) {
+                       return A->ruleId() < B->ruleId();
+                     });
+    // now try to arrange sections with no mapping rules to sections with
+    // similar content
+    auto p = _sections.begin();
+    const uint32_t lastRuleId = _linkerScriptSema.lastRuleId();
+    // Find first section that has no assigned rule id
+    while (p != _sections.end() && (*p)->ruleId() != lastRuleId)
+      ++p;
+    // For all sections that have no assigned rule id, try to move them near a
+    // section with similar contents
+    if (p != _sections.begin()) {
+      for (; p != _sections.end(); ++p) {
+        auto q = p;
+        --q;
+        while (q != _sections.begin() &&
+               (*q)->getContentType() != (*p)->getContentType())
+          --q;
+        if ((*q)->getContentType() != (*p)->getContentType())
+          continue;
+        ++q;
+        for (auto i = p; i != q;) {
+          auto next = i--;
+          std::iter_swap(i, next);
+        }
+      }
+    }
+  }
   // Create output sections.
   createOutputSections();
   // Set the ordinal after sorting the sections
   int ordinal = 1;
   for (auto osi : _outputSections) {
     osi->setOrdinal(ordinal);
     for (auto ai : osi->sections()) {
       ai->setOrdinal(ordinal);
for (auto ai : osi->sections()) {
           const std::pair<AdditionalSegmentKey, Segment<ELFT> *>
           additionalSegment(key, nullptr);
           std::pair<typename AdditionalSegmentMapT::iterator, bool>
           additionalSegmentInsert(
               _additionalSegmentMap.insert(additionalSegment));
           if (!additionalSegmentInsert.second) {
             segment = additionalSegmentInsert.first->second;
           } else {
-            segment = new (_allocator) Segment<ELFT>(_context, segmentName,
-                                                     segmentType);
+            segment = new (_allocator) Segment<ELFT>(
+                _context, segmentName, segmentType, _linkerScriptSema);
             additionalSegmentInsert.first->second = segment;
             _segments.push_back(segment);
           }
           segment->append(section);
         }
         if (segmentType == llvm::ELF::PT_NULL)
           continue;
 
for (auto ai : osi->sections()) {
         const SegmentKey key("PT_LOAD", lookupSectionFlag);
         const std::pair<SegmentKey, Segment<ELFT> *> currentSegment(key,
                                                                     nullptr);
         std::pair<typename SegmentMapT::iterator, bool> segmentInsert(
             _segmentMap.insert(currentSegment));
         if (!segmentInsert.second) {
           segment = segmentInsert.first->second;
         } else {
-          segment = new (_allocator) Segment<ELFT>(_context, "PT_LOAD",
-                                                   llvm::ELF::PT_LOAD);
+          segment = new (_allocator) Segment<ELFT>(
+              _context, "PT_LOAD", llvm::ELF::PT_LOAD, _linkerScriptSema);
           segmentInsert.first->second = segment;
           _segments.push_back(segment);
         }
+        // Insert chunks with linker script expressions that occur at this
+        // point
+        if (_linkerScriptSema.hasRules()) {
+          std::vector<const script::SymbolAssignment *> exprs =
+              _linkerScriptSema.getExprs(section->ruleId());
+          for (auto expr : exprs) {
+            auto expChunk =
+                new (_allocator) ExpressionChunk<ELFT>(_context, expr);
+            segment->append(expChunk);
+          }
+        }
         segment->append(section);
       }
     }
   }
   if (_context.isDynamic() && !_context.isDynamicLibrary()) {
-    Segment<ELFT> *segment =
-        new (_allocator) ProgramHeaderSegment<ELFT>(_context);
+    Segment<ELFT> *segment = new (_allocator)
+        ProgramHeaderSegment<ELFT>(_context, _linkerScriptSema);
     _segments.push_back(segment);
     segment->append(_elfHeader);
     segment->append(_programHeader);
   }
 }
 
 template<class ELFT>
 void
DefaultLayout<ELFT>::assignVirtualAddress() {
   Segment<ELFT> *firstLoadSegment = nullptr;
   for (auto si : _segments) {
     if (si->segmentType() == llvm::ELF::PT_LOAD) {
       firstLoadSegment = si;
       si->firstSection()->setAlign(si->alignment());
       break;
     }
   }
+  assert(firstLoadSegment != nullptr && "No loadable segment!");
   firstLoadSegment->prepend(_programHeader);
   firstLoadSegment->prepend(_elfHeader);
   bool newSegmentHeaderAdded = true;
   bool virtualAddressAssigned = false;
   bool fileOffsetAssigned = false;
   while (true) {
     for (auto si : _segments) {
       si->finalize();

lib/ReaderWriter/ELF/ELFFile.h

template <class ELFT> std::error_code ELFFile<ELFT>::createMergeableAtoms() {
 
   // Create Mergeable atoms
   for (const MergeString *tai : tokens) {
     ArrayRef<uint8_t> content((const uint8_t *)tai->_string.data(),
                               tai->_string.size());
     ErrorOr<ELFMergeAtom<ELFT> *> mergeAtom =
         handleMergeString(tai->_sectionName, tai->_shdr, content, tai->_offset);
     (*mergeAtom)->setOrdinal(++_ordinal);
+    if (!_ctx.linkerScriptSema().hasRules())
+      (*mergeAtom)->setRuleId(0);
+    else
+      (*mergeAtom)
+          ->setRuleId(_ctx.linkerScriptSema().getRuleId(
+              this->archivePath(), this->memberPath(), tai->_sectionName));
     _definedAtoms._atoms.push_back(*mergeAtom);
     _mergeAtoms.push_back(*mergeAtom);
   }
   return std::error_code();
 }
 
 template <class ELFT>
 std::error_code ELFFile<ELFT>::createSymbolsFromAtomizableSections() {
if (isAbsoluteSymbol(&*SymI)) {
       ErrorOr<ELFUndefinedAtom<ELFT> *> undefAtom =
           handleUndefinedSymbol(*symbolName, &*SymI);
       _undefinedAtoms._atoms.push_back(*undefAtom);
       _symbolToAtomMapping.insert(std::make_pair(&*SymI, *undefAtom));
     } else if (isCommonSymbol(&*SymI)) {
       ErrorOr<ELFCommonAtom<ELFT> *> commonAtom =
           handleCommonSymbol(*symbolName, &*SymI);
       (*commonAtom)->setOrdinal(++_ordinal);
+      if (!_ctx.linkerScriptSema().hasRules())
+        (*commonAtom)->setRuleId(0);
+      else {
+        ErrorOr<StringRef> sectionName = this->getSectionName(section);
+        if (std::error_code ec = sectionName.getError())
+          (*commonAtom)->setRuleId(0);
+        else
+          (*commonAtom)
+              ->setRuleId(_ctx.linkerScriptSema().getRuleId(
+                  this->archivePath(), this->memberPath(), *sectionName));
+      }
       _definedAtoms._atoms.push_back(*commonAtom);
       _symbolToAtomMapping.insert(std::make_pair(&*SymI, *commonAtom));
     } else if (isDefinedSymbol(&*SymI)) {
       _sectionSymbols[section].push_back(SymI);
     } else {
       llvm::errs() << "Unable to create atom for: " << *symbolName << "\n";
       return llvm::object::object_error::parse_failed;
     }
for (auto &i : _sectionSymbols) {
 
     if (isSectionMemberOfGroup(section))
       addAtoms = false;
 
     if (handleSectionWithNoSymbols(section, symbols)) {
       ELFDefinedAtom<ELFT> *newAtom =
           createSectionAtom(section, *sectionName, *sectionContents);
       newAtom->setOrdinal(++_ordinal);
+      if (!_ctx.linkerScriptSema().hasRules())
+        newAtom->setRuleId(0);
+      else
+        newAtom->setRuleId(_ctx.linkerScriptSema().getRuleId(
+            this->archivePath(), this->memberPath(), *sectionName));
       if (addAtoms)
         _definedAtoms._atoms.push_back(newAtom);
       else
         atomsForSection[*sectionName].push_back(newAtom);
       continue;
     }
 
     ELFDefinedAtom<ELFT> *previousAtom = nullptr;
for (auto si = symbols.begin(), se = symbols.end(); si != se; ++si) {
       // merged away as well as these symbols have to be part of symbol
       // resolution
       if (isMergeableStringSection(section)) {
         if (symbol->getBinding() == llvm::ELF::STB_GLOBAL) {
           auto definedMergeAtom = handleDefinedSymbol(
               symbolName, *sectionName, &**si, section, symbolData,
               _references.size(), _references.size(), _references);
           (*definedMergeAtom)->setOrdinal(++_ordinal);
+          if (!_ctx.linkerScriptSema().hasRules())
+            (*definedMergeAtom)->setRuleId(0);
+          else
+            (*definedMergeAtom)
+                ->setRuleId(_ctx.linkerScriptSema().getRuleId(
+                    this->archivePath(), this->memberPath(), *sectionName));
           if (addAtoms)
             _definedAtoms._atoms.push_back(*definedMergeAtom);
           else
             atomsForSection[*sectionName].push_back(*definedMergeAtom);
         }
         continue;
       }
 
for (auto si = symbols.begin(), se = symbols.end(); si != se; ++si) {
               ELFReference<ELFT>(lld::Reference::kindLayoutAfter);
           anonAtom->addReference(anonFollowedBy);
         }
       }
 
       ELFDefinedAtom<ELFT> *newAtom = createDefinedAtomAndAssignRelocations(
           symbolName, *sectionName, &*symbol, section, symbolData,
           *sectionContents);
+      if (!_ctx.linkerScriptSema().hasRules())
+        newAtom->setRuleId(0);
+      else
+        newAtom->setRuleId(_ctx.linkerScriptSema().getRuleId(
+            this->archivePath(), this->memberPath(), *sectionName));
       newAtom->setOrdinal(++_ordinal);
 
       // If the atom was a weak symbol, let's create a followon reference to
       // the anonymous atom that we created.
       if (anonAtom)
         createEdge(newAtom, anonAtom, Reference::kindLayoutAfter);
 
       if (previousAtom) {
for (auto si = symbols.begin(), se = symbols.end(); si != se; ++si) {
       if (addAtoms)
         _definedAtoms._atoms.push_back(newAtom);
       else
         atomsForSection[*sectionName].push_back(newAtom);
 
       _symbolToAtomMapping.insert(std::make_pair(&*symbol, newAtom));
       if (anonAtom) {
         anonAtom->setOrdinal(++_ordinal);
+        if (!_ctx.linkerScriptSema().hasRules())
+          anonAtom->setRuleId(0);
+        else
+          anonAtom->setRuleId(_ctx.linkerScriptSema().getRuleId(
+              this->archivePath(), this->memberPath(), *sectionName));
         if (addAtoms)
           _definedAtoms._atoms.push_back(anonAtom);
         else
           atomsForSection[*sectionName].push_back(anonAtom);
       }
     }
   }
 
ELFFile<ELFT>::createSectionAtom(const Elf_Shdr *section, StringRef sectionName,
   sym->setBindingAndType(llvm::ELF::STB_LOCAL, llvm::ELF::STT_SECTION);
   sym->st_other = 0;
   sym->st_shndx = 0;
   sym->st_value = 0;
   sym->st_size = 0;
   auto *newAtom = createDefinedAtomAndAssignRelocations(
       "", sectionName, sym, section, content, content);
   newAtom->setOrdinal(++_ordinal);
+  if (!_ctx.linkerScriptSema().hasRules())
+    newAtom->setRuleId(0);
+  else
+    newAtom->setRuleId(_ctx.linkerScriptSema().getRuleId(
+        this->archivePath(), this->memberPath(), sectionName));
   return newAtom;
 }
 
 template <class ELFT>
 uint64_t ELFFile<ELFT>::symbolContentSize(const Elf_Shdr *section,
                                           const Elf_Sym *symbol,
                                           const Elf_Sym *nextSymbol) {
   const auto symValue = getSymbolValue(symbol);

lib/ReaderWriter/ELF/ELFLinkingContext.cpp

ELFLinkingContext::ELFLinkingContext(
     : _outputELFType(llvm::ELF::ET_EXEC), _triple(triple),
       _targetHandler(std::move(targetHandler)), _baseAddress(0),
       _isStaticExecutable(false), _noInhibitExec(false), _exportDynamic(false),
       _mergeCommonStrings(false), _useShlibUndefines(true),
       _dynamicLinkerArg(false), _noAllowDynamicLibraries(false),
       _mergeRODataToTextSegment(true), _demangle(true),
       _stripSymbols(false), _alignSegments(true), _collectStats(false),
       _outputMagic(OutputMagic::DEFAULT), _initFunction("_init"),
-      _finiFunction("_fini"), _sysrootPath("") {}
+      _finiFunction("_fini"), _sysrootPath(""), _linkerScriptSema() {}
 
 void ELFLinkingContext::addPasses(PassManager &pm) {
   pm.add(llvm::make_unique<elf::OrderPass>());
 }
 
 uint16_t ELFLinkingContext::getOutputMachine() const {
   switch (getTriple().getArch()) {
   case llvm::Triple::x86:

lib/ReaderWriter/ELF/Hexagon/HexagonTargetHandler.h

 /// \brief TargetLayout for Hexagon
 template <class HexagonELFType>
 class HexagonTargetLayout final : public TargetLayout<HexagonELFType> {
 public:
   enum HexagonSectionOrder {
     ORDER_SDATA = 205
   };
 
-  HexagonTargetLayout(const HexagonLinkingContext &hti)
+  HexagonTargetLayout(HexagonLinkingContext &hti)
       : TargetLayout<HexagonELFType>(hti), _sdataSection(nullptr),
         _gotSymAtom(nullptr), _cachedGotSymAtom(false) {
     _sdataSection = new (_alloc) SDataSection<HexagonELFType>(hti);
   }
 
   /// \brief Return the section order for a input section
   virtual Layout::SectionOrder getSectionOrder(
       StringRef name, int32_t contentType, int32_t contentPermissions) {

lib/ReaderWriter/ELF/Mips/MipsTargetHandler.h

 
 namespace lld {
 namespace elf {
 
 /// \brief TargetLayout for Mips
 template <class ELFType>
 class MipsTargetLayout final : public TargetLayout<ELFType> {
 public:
-  MipsTargetLayout(const MipsLinkingContext &ctx)
+  MipsTargetLayout(MipsLinkingContext &ctx)
       : TargetLayout<ELFType>(ctx),
         _gotSection(new (_alloc) MipsGOTSection<ELFType>(ctx)),
         _pltSection(new (_alloc) MipsPLTSection<ELFType>(ctx)) {}
 
   const MipsGOTSection<ELFType> &getGOTSection() const { return *_gotSection; }
   const MipsPLTSection<ELFType> &getPLTSection() const { return *_pltSection; }
 
   AtomSection<ELFType> *

lib/ReaderWriter/ELF/OrderPass.h

 //===- lib/ReaderWriter/ELF/OrderPass.h -----------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_READER_WRITER_ELF_ORDER_PASS_H
 #define LLD_READER_WRITER_ELF_ORDER_PASS_H
 
 #include "lld/Core/Parallel.h"
+#include "lld/ReaderWriter/LinkerScript.h"
 #include <limits>
 
 namespace lld {
 namespace elf {
 
 /// \brief This pass sorts atoms by file and atom ordinals.
 /// .{init,fini}_array.<priority> sections are handled specially.
 class OrderPass : public Pass {

lib/ReaderWriter/ELF/SegmentChunks.h

 //  the segment is just a way to concatenate sections to segments
 template<class ELFT>
 class Segment : public Chunk<ELFT> {
 public:
   typedef typename std::vector<SegmentSlice<ELFT> *>::iterator SliceIter;
   typedef typename std::vector<Chunk<ELFT> *>::iterator SectionIter;
 
   Segment(const ELFLinkingContext &context, StringRef name,
-          const Layout::SegmentType type);
+          const Layout::SegmentType type, script::Sema &linkerScriptSema);
 
   /// \brief the Order of segments that appear in the output file
   enum SegmentOrder {
     permUnknown,
     permRWX,
     permRX,
     permR,
     permRWL,
     permRW,
     permNonAccess
   };
 
   /// append a section to a segment
   virtual void append(Section<ELFT> *chunk);
 
   /// append a chunk to a segment, this function
   /// is used by the ProgramHeader segment
-  virtual void append(Chunk<ELFT> *chunk) {}
+  virtual void append(Chunk<ELFT> *chunk) { _sections.push_back(chunk); }
 
   /// Sort segments depending on the property
   /// If we have a Program Header segment, it should appear first
   /// If we have a INTERP segment, that should appear after the Program Header
   /// All Loadable segments appear next in this order
   /// All Read Write Execute segments follow
   /// All Read Execute segments appear next
   /// All Read only segments appear first

 protected:
   /// \brief Section or some other chunk type.
   std::vector<Chunk<ELFT> *> _sections;
   std::vector<SegmentSlice<ELFT> *> _segmentSlices;
   Layout::SegmentType _segmentType;
   uint64_t _flags;
   int64_t _atomflags;
   llvm::BumpPtrAllocator _segmentAllocate;
+  script::Sema &_linkerScriptSema;
+};
+
+template <class ELFT> class ExpressionChunk : public Chunk<ELFT> {
+public:
+  ExpressionChunk(const ELFLinkingContext &ctx,
+                  const script::SymbolAssignment *expr)
+      : Chunk<ELFT>(StringRef(), Chunk<ELFT>::Kind::Expression, ctx),
+        _expr(expr) {
+    this->_alignment = 1;
+  }
+
+  static bool classof(const Chunk<ELFT> *c) {
+    return c->kind() == Chunk<ELFT>::Kind::Expression;
+  }
+
+  const script::SymbolAssignment *get() const { return _expr; }
+
+  int getContentType() const override {
+    return Chunk<ELFT>::ContentType::Unknown;
+  }
+  void write(ELFWriter *, TargetLayout<ELFT> &,
+             llvm::FileOutputBuffer &) override {}
+  void doPreFlight() override {}
+  void finalize() override {}
+
+private:
+  const script::SymbolAssignment *_expr;
 };
 
 /// \brief A Program Header segment contains a set of chunks instead of sections
 /// The segment doesn't contain any slice
 template <class ELFT> class ProgramHeaderSegment : public Segment<ELFT> {
 public:
-  ProgramHeaderSegment(const ELFLinkingContext &context)
-      : Segment<ELFT>(context, "PHDR", llvm::ELF::PT_PHDR) {
+  ProgramHeaderSegment(const ELFLinkingContext &context,
+                       script::Sema &linkerScriptSema)
+      : Segment<ELFT>(context, "PHDR", llvm::ELF::PT_PHDR, linkerScriptSema) {
     this->_alignment = 8;
     this->_flags = (llvm::ELF::SHF_ALLOC | llvm::ELF::SHF_EXECINSTR);
   }
 
   /// append a section to a segment
   void append(Chunk<ELFT> *chunk) { _sections.push_back(chunk); }
 
   /// Finalize the segment, before we want to write the segment header

 
 protected:
   /// \brief Section or some other chunk type.
   std::vector<Chunk<ELFT> *> _sections;
 };
 
 template <class ELFT>
 Segment<ELFT>::Segment(const ELFLinkingContext &context, StringRef name,
-                       const Layout::SegmentType type)
+                       const Layout::SegmentType type, script::Sema &s)
     : Chunk<ELFT>(name, Chunk<ELFT>::Kind::ELFSegment, context),
-      _segmentType(type), _flags(0), _atomflags(0) {
+      _segmentType(type), _flags(0), _atomflags(0), _linkerScriptSema(s) {
   this->_alignment = 0;
   this->_fsize = 0;
   _outputMagic = context.getOutputMagic();
 }
 
 // This function actually is used, but not in all instantiations of Segment.
 LLVM_ATTRIBUTE_UNUSED
 static DefinedAtom::ContentPermissions toAtomPerms(uint64_t flags) {

 
 template <class ELFT>
 void Segment<ELFT>::assignFileOffsets(uint64_t startOffset) {
   uint64_t fileOffset = startOffset;
   uint64_t curSliceFileOffset = fileOffset;
   bool isDataPageAlignedForNMagic = false;
   bool alignSegments = this->_context.alignSegments();
   uint64_t p_align = this->_context.getPageSize();
+  uint64_t lastVirtualAddress = 0;
 
   this->setFileOffset(startOffset);
   for (auto &slice : slices()) {
     bool isFirstSection = true;
     for (auto section : slice->sections()) {
+      // Handle linker script expressions, which may change the offset
+      if (!isFirstSection)
+        if (auto expr = dyn_cast<ExpressionChunk<ELFT>>(section))
+          fileOffset += expr->virtualAddr() - lastVirtualAddress;
       // Align fileoffset to the alignment of the section.
       fileOffset = llvm::RoundUpToAlignment(fileOffset, section->alignment());
       // If the linker outputmagic is set to OutputMagic::NMAGIC, align the Data
       // to a page boundary
       if (isFirstSection &&
           _outputMagic != ELFLinkingContext::OutputMagic::NMAGIC &&
           _outputMagic != ELFLinkingContext::OutputMagic::OMAGIC) {
         // Align to a page only if the output is not
for (auto section : slice->sections()) {
       }
       if (isFirstSection) {
         slice->setFileOffset(fileOffset);
         isFirstSection = false;
         curSliceFileOffset = fileOffset;
       }
       section->setFileOffset(fileOffset);
       fileOffset += section->fileSize();
+      lastVirtualAddress = section->virtualAddr() + section->memSize();
     }
     slice->setFileSize(fileOffset - curSliceFileOffset);
   }
   this->setFileSize(fileOffset - startOffset);
 }
 
 /// \brief Assign virtual addresses to the slices
 template <class ELFT> void Segment<ELFT>::assignVirtualAddress(uint64_t addr) {
template <class ELFT> void Segment<ELFT>::assignVirtualAddress(uint64_t addr) {
   startSectionIter = _sections.begin();
   startSection = 0;
   bool isFirstSection = true;
   bool isDataPageAlignedForNMagic = false;
   uint64_t startAddr = addr;
   SegmentSlice<ELFT> *slice = nullptr;
   uint64_t tlsStartAddr = 0;
   bool alignSegments = this->_context.alignSegments();
-  StringRef prevOutputSectionName;
+  StringRef prevOutputSectionName = StringRef();
 
   for (auto si = _sections.begin(); si != _sections.end(); ++si) {
     // If this is first section in the segment, page align the section start
     // address. The linker needs to align the data section to a page boundary
     // only if NMAGIC is set.
     if (isFirstSection) {
       isFirstSection = false;
       if (alignSegments &&
           _outputMagic != ELFLinkingContext::OutputMagic::NMAGIC &&
           _outputMagic != ELFLinkingContext::OutputMagic::OMAGIC)
         // Align to a page only if the output is not
         // OutputMagic::NMAGIC/OutputMagic::OMAGIC
         startAddr =
             llvm::RoundUpToAlignment(startAddr, this->_context.getPageSize());
       else if (!isDataPageAlignedForNMagic && needAlign(*si)) {
         // If the linker outputmagic is set to OutputMagic::NMAGIC, align the
         // Data to a page boundary.
         startAddr =
             llvm::RoundUpToAlignment(startAddr, this->_context.getPageSize());
         isDataPageAlignedForNMagic = true;
       }
       // align the startOffset to the section alignment
       uint64_t newAddr = llvm::RoundUpToAlignment(startAddr, (*si)->alignment());
+      // Handle linker script expressions, which *may update newAddr* if the
+      // expression assigns to "."
+      if (auto expr = dyn_cast<ExpressionChunk<ELFT>>(*si))
+        _linkerScriptSema.evalExpr(expr->get(), newAddr);
       curSliceAddress = newAddr;
       sliceAlign = (*si)->alignment();
       (*si)->setVirtualAddr(curSliceAddress);
 
       // Handle TLS.
       if (auto section = dyn_cast<Section<ELFT>>(*si)) {
         if (section->getSegmentType() == llvm::ELF::PT_TLS) {
           tlsStartAddr =
if (isFirstSection) {
         // If the linker outputmagic is set to OutputMagic::NMAGIC, align the
         // Data
         // to a page boundary
         curAddr =
             llvm::RoundUpToAlignment(curAddr, this->_context.getPageSize());
         isDataPageAlignedForNMagic = true;
       }
       uint64_t newAddr = llvm::RoundUpToAlignment(curAddr, (*si)->alignment());
+      // Handle linker script expressions, which *may update newAddr* if the
+      // expression assigns to "."
+      if (auto expr = dyn_cast<ExpressionChunk<ELFT>>(*si))
+        _linkerScriptSema.evalExpr(expr->get(), newAddr);
       Section<ELFT> *sec = dyn_cast<Section<ELFT>>(*si);
-      StringRef curOutputSectionName =
-          sec ? sec->outputSectionName() : (*si)->name();
+      StringRef curOutputSectionName;
+      if (sec)
+        curOutputSectionName = sec->outputSectionName();
+      else {
+        // If this is a linker script expression, propagate the name of the
+        // previous section instead
+        if (isa<ExpressionChunk<ELFT>>(*si))
+          curOutputSectionName = prevOutputSectionName;
+        else
+          curOutputSectionName = (*si)->name();
+      }
       bool autoCreateSlice = true;
       if (curOutputSectionName == prevOutputSectionName)
         autoCreateSlice = false;
       // If the newAddress computed is more than a page away, let's create
       // a separate segment, so that memory is not used up while running.
       // Dont create a slice, if the new section falls in the same output
       // section as the previous section.
       if (autoCreateSlice &&

lib/ReaderWriter/ELF/TargetLayout.h

 
 namespace lld {
 namespace elf {
 /// \brief The target can override certain functions in the DefaultLayout
 /// class so that the order, the name of the section and the segment type could
 /// be changed in the final layout
 template <class ELFT> class TargetLayout : public DefaultLayout<ELFT> {
 public:
-  TargetLayout(const ELFLinkingContext &context)
+  TargetLayout(ELFLinkingContext &context)
       : DefaultLayout<ELFT>(context) {}
 };
 } // end namespace elf
 } // end namespace lld
 
 #endif

lib/ReaderWriter/LinkerScript.cpp

Sections *Parser::parseSections() {
   if (!expectAndConsume(
           Token::r_brace,
           "expected symbol assignment, entry, overlay or output section name."))
     return nullptr;
 
   return new (_alloc) Sections(*this, sectionsCommands);
 }
 
+Sema::Sema()
+    : _scripts(), _rules(), _idMap(), _fileToRuleId(), _archiveToRuleId(),
+      _symbolTable() {}
+
 } // end namespace script
 } // end namespace lld

test/elf/Inputs/prog1.o.yaml

+---
+FileHeader:      
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  OSABI:           ELFOSABI_GNU
+  Type:            ET_REL
+  Machine:         EM_X86_64
+Sections:        
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    AddressAlign:    0x0000000000000010
+    Content:         554889E5B000E800000000BF01000000BA0E0000004889C6E80000000031C05DC3
+  - Name:            .rela.text
+    Type:            SHT_RELA
+    Link:            .symtab
+    AddressAlign:    0x0000000000000008
+    Info:            .text
+    Relocations:     
+      - Offset:          0x0000000000000007
+        Symbol:          prog2
+        Type:            R_X86_64_PC32
+        Addend:          -4
+      - Offset:          0x0000000000000019
+        Symbol:          write
+        Type:            R_X86_64_PC32
+        Addend:          -4
+  - Name:            .data
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_WRITE, SHF_ALLOC ]
+    AddressAlign:    0x0000000000000004
+    Content:         ''
+  - Name:            .bss
+    Type:            SHT_NOBITS
+    Flags:           [ SHF_WRITE, SHF_ALLOC ]
+    AddressAlign:    0x0000000000000004
+    Content:         ''
+  - Name:            .comment
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_MERGE, SHF_STRINGS ]
+    AddressAlign:    0x0000000000000001
+    Content:         00636C616E672076657273696F6E20332E372E302028687474703A2F2F6C6C766D2E6F72672F6769742F636C616E672E6769742036336134646334616430343938646139623934386330383263623735336430353735323938346638292028687474703A2F2F6C6C766D2E6F72672F6769742F6C6C766D2E67697420623838363135326664656538376564653738613565643965616638663664313839343033616266312900
+  - Name:            .note.GNU-stack
+    Type:            SHT_PROGBITS
+    AddressAlign:    0x0000000000000001
+    Content:         ''
+  - Name:            .eh_frame
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC ]
+    AddressAlign:    0x0000000000000008
+    Content:         1400000000000000037A5200017810011B0C0708900100001C0000001C000000000000002100000000410E108602430D0600000000000000
+  - Name:            .rela.eh_frame
+    Type:            SHT_RELA
+    Link:            .symtab
+    AddressAlign:    0x0000000000000008
+    Info:            .eh_frame
+    Relocations:     
+      - Offset:          0x0000000000000020
+        Symbol:          .text
+        Type:            R_X86_64_PC32
+Symbols:         
+  Local:           
+    - Name:            .text
+      Type:            STT_SECTION
+      Section:         .text
+    - Name:            .data
+      Type:            STT_SECTION
+      Section:         .data
+    - Name:            .bss
+      Type:            STT_SECTION
+      Section:         .bss
+    - Name:            .comment
+      Type:            STT_SECTION
+      Section:         .comment
+    - Name:            .note.GNU-stack
+      Type:            STT_SECTION
+      Section:         .note.GNU-stack
+    - Name:            .eh_frame
+      Type:            STT_SECTION
+      Section:         .eh_frame
+  Global:          
+    - Name:            main
+      Type:            STT_FUNC
+      Section:         .text
+      Size:            0x0000000000000021
+    - Name:            prog2
+    - Name:            write
+...

test/elf/Inputs/prog2.o.yaml

+---
+FileHeader:      
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  OSABI:           ELFOSABI_GNU
+  Type:            ET_REL
+  Machine:         EM_X86_64
+Sections:        
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    AddressAlign:    0x0000000000000010
+    Content:         554889E548B800000000000000005DC3
+  - Name:            .rela.text
+    Type:            SHT_RELA
+    Link:            .symtab
+    AddressAlign:    0x0000000000000008
+    Info:            .text
+    Relocations:     
+      - Offset:          0x0000000000000006
+        Symbol:          .rodata.str1.1
+        Type:            R_X86_64_64
+  - Name:            .data
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_WRITE, SHF_ALLOC ]
+    AddressAlign:    0x0000000000000004
+    Content:         ''
+  - Name:            .bss
+    Type:            SHT_NOBITS
+    Flags:           [ SHF_WRITE, SHF_ALLOC ]
+    AddressAlign:    0x0000000000000004
+    Content:         ''
+  - Name:            .rodata.str1.1
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_MERGE, SHF_STRINGS ]
+    AddressAlign:    0x0000000000000001
+    Content:         48656C6C6F2C20776F726C64210A00
+  - Name:            .comment
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_MERGE, SHF_STRINGS ]
+    AddressAlign:    0x0000000000000001
+    Content:         00636C616E672076657273696F6E20332E372E302028687474703A2F2F6C6C766D2E6F72672F6769742F636C616E672E6769742036336134646334616430343938646139623934386330383263623735336430353735323938346638292028687474703A2F2F6C6C766D2E6F72672F6769742F6C6C766D2E67697420623838363135326664656538376564653738613565643965616638663664313839343033616266312900
+  - Name:            .note.GNU-stack
+    Type:            SHT_PROGBITS
+    AddressAlign:    0x0000000000000001
+    Content:         ''
+  - Name:            .eh_frame
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC ]
+    AddressAlign:    0x0000000000000008
+    Content:         1400000000000000037A5200017810011B0C0708900100001C0000001C000000000000001000000000410E108602430D0600000000000000
+  - Name:            .rela.eh_frame
+    Type:            SHT_RELA
+    Link:            .symtab
+    AddressAlign:    0x0000000000000008
+    Info:            .eh_frame
+    Relocations:     
+      - Offset:          0x0000000000000020
+        Symbol:          .text
+        Type:            R_X86_64_PC32
+Symbols:         
+  Local:           
+    - Name:            .text
+      Type:            STT_SECTION
+      Section:         .text
+    - Name:            .data
+      Type:            STT_SECTION
+      Section:         .data
+    - Name:            .bss
+      Type:            STT_SECTION
+      Section:         .bss
+    - Name:            .rodata.str1.1
+      Type:            STT_SECTION
+      Section:         .rodata.str1.1
+    - Name:            .comment
+      Type:            STT_SECTION
+      Section:         .comment
+    - Name:            .note.GNU-stack
+      Type:            STT_SECTION
+      Section:         .note.GNU-stack
+    - Name:            .eh_frame
+      Type:            STT_SECTION
+      Section:         .eh_frame
+  Global:          
+    - Name:            prog2
+      Type:            STT_FUNC
+      Section:         .text
+      Size:            0x0000000000000010
+...

test/elf/Inputs/prog3.o.yaml

+---
+FileHeader:      
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  OSABI:           ELFOSABI_GNU
+  Type:            ET_REL
+  Machine:         EM_X86_64
+Sections:        
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    AddressAlign:    0x0000000000000004
+    Content:         B8010000000F05C3E800000000B83C0000000F05C3
+  - Name:            .rela.text
+    Type:            SHT_RELA
+    Link:            .symtab
+    AddressAlign:    0x0000000000000008
+    Info:            .text
+    Relocations:     
+      - Offset:          0x0000000000000009
+        Symbol:          main
+        Type:            R_X86_64_PC32
+        Addend:          -4
+  - Name:            .data
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_WRITE, SHF_ALLOC ]
+    AddressAlign:    0x0000000000000004
+    Content:         ''
+  - Name:            .bss
+    Type:            SHT_NOBITS
+    Flags:           [ SHF_WRITE, SHF_ALLOC ]
+    AddressAlign:    0x0000000000000004
+    Content:         ''
+Symbols:         
+  Local:           
+    - Name:            .text
+      Type:            STT_SECTION
+      Section:         .text
+    - Name:            .data
+      Type:            STT_SECTION
+      Section:         .data
+    - Name:            .bss
+      Type:            STT_SECTION
+      Section:         .bss
+  Global:          
+    - Name:            _start
+      Section:         .text
+      Value:           0x0000000000000008
+    - Name:            write
+      Section:         .text
+    - Name:            main
+...

test/elf/script-section-order.test

+/*
+Tests a simple linker script that changes the order of output sections and
+also changes the address of output sections by using simple expressions.
+
+This test uses three X86-64 input objects, prog1.o, prog2.o and prog3.o,
+which were created with the following C or assembly code:
+
+*** prog1.o:
+
+(command line clang -c prog1.c -o prog1.o)
+
+const char *prog2();
+void write(int, const char *, int);
+
+int main() {
+  write(1, prog2(), 14);
+}
+
+*** prog2.o:
+
+(command line clang -c prog2.c -o prog2.o)
+
+const char *prog2() {
+ return "Hello, world!\n";
+}
+
+*** prog3.o:
+
+(command line clang -c prog3.S -o prog3.o)
+
+      .globl write
+write:
+      mov $1, %eax
+      syscall
+      ret
+
+      .globl _start
+_start:
+      call  main
+      mov $60, %eax
+      syscall
+      ret
+
+We use the following linker script for this test:
+*/
+
+ENTRY(_start)
+
+SECTIONS
+{
+  . = 0x500000;
+  .text : { prog1.o(.text) }
+  .mystring : { prog2.o(.rodata.str1.1) }
+  . = . + 0x6000;
+  .text.2 : {prog3.o(.text) prog2.o(.text) }
+}
+
+/*
+RUN: yaml2obj -format=elf %p/Inputs/prog1.o.yaml -o=%T/prog1.o
+RUN: yaml2obj -format=elf %p/Inputs/prog2.o.yaml -o=%T/prog2.o
+RUN: yaml2obj -format=elf %p/Inputs/prog3.o.yaml -o=%T/prog3.o
+
+RUN: cd %T
+RUN: lld -flavor gnu  -target x86_64 -T %s prog1.o prog2.o prog3.o \
+RUN:   -static -o %t1
+RUN: llvm-readobj -s %t1 | FileCheck -check-prefix CHECKSECTIONS %s
+
+CHECKSECTIONS:       Index: 1
+CHECKSECTIONS:       Name: .text
+CHECKSECTIONS:       Address: 0x500000
+CHECKSECTIONS:       Size: 33
+
+CHECKSECTIONS:       Index: 2
+CHECKSECTIONS:       Name: .mystring
+CHECKSECTIONS:       Address: 0x500021
+CHECKSECTIONS:       Size: 15
+
+CHECKSECTIONS:       Index: 3
+CHECKSECTIONS:       Name: .text.2
+CHECKSECTIONS:       Address: 0x506030
+CHECKSECTIONS:       Size: 48
+
+RUN: llvm-readobj -symbols %t1 | FileCheck -check-prefix CHECKSYMS %s
+
+CHECKSYMS:      Name: main
+CHECKSYMS-NEXT: Value: 0x500000
+
+CHECKSYMS:      Name: write
+CHECKSYMS-NEXT: Value: 0x506030
+
+CHECKSYMS:      Name: _start
+CHECKSYMS-NEXT: Value: 0x506038
+
+CHECKSYMS:      Name: prog2
+CHECKSYMS-NEXT: Value: 0x506050
+*/