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

[rafaelauler]

Summary

This patch should work on top of D8156 because it needs linker script
expression evaluation.

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 special sort orders. I added two LIT test as practical examples of which
sections directives are currently supported.

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.

The difference D7915 is that I implemented several suggestions from Rui and
Shankar:

• there is no exposed "id". Clients always ask how to order a section, and whether we use "ids" to sort or not is internal to the Sema class implementation. (suggestion from Rui)
• improved the input sections ordering and addressed the test case mentioned by Shankar (second LIT test case in this patch) (suggestion from Shankar)
• refactored the code in DefaultLayout to live in ScriptLayout (suggestion from Shankar)

I also took the opportunity to improve the code and implement simple
SORT directives and wildcard matching.

[shankarke]

can we split this patch by functionalities too, its easier for review.

include/lld/ReaderWriter/LinkerScript.h

168

Could you represent all the different kinds of functions that can operate on the input sections as Functions instead of InputSectionKinds ?

759–760

this could be simplified if you use lld::range.

1122

can you rename this to archiveNameOrPath

1127–1130

caching layout order is error prone, as users may selectively want to specify a layout order from one rule to another.

1154

All the end users should be using Sema right ? So This function could be made private.

1159

returns void ?

1186

Could we evaluate as and when the input section is appended to the output section ?

lib/ReaderWriter/ELF/DefaultLayout.h

229–235

If you can associate the expression also to an outputsection, this would not be needed. The code gets overly simplified too.

lib/ReaderWriter/ELF/SegmentChunks.h

437

why would you do this ?

[ruiu]

As a general comment, this patch is still too large, and I prefer smaller, incremental patches. For examples, we could drop some directives from this patch, or remove some features such as wildcard pattern matching from this, and basic features should still work. And then we could add missing features one by one. It may be too late, and I read the whole patch anyway, but please consider doing that way next time. Thanks!

Review comments are inline.

include/lld/ReaderWriter/LinkerScript.h

1130

Instead of defining a class (struct) implementing an operator=(const SectionKey &), you can simply define of a function (int64_t f(const SectionKey &)) and pass it to std::unordered_map.

You want to move this below private:.

1138

Ditto

1154

Returning a const std::vector would be better?

lib/ReaderWriter/ELF/DefaultLayout.h

346

Merge this with DefaultLayout and remove this class.

569

It's good to add a brief comment here, like, section names may be renamed by linker scripts.

973

This code is complicated. If we just want to group sections by content type, can you just stable_sort them by content type?

lib/ReaderWriter/LinkerScript.cpp

2099

I think you need to check whether or not i is not greater than the length of name on each iteration.

2111

StringRef::find returns npos if not found.

2198

This loop content is duplicate of the previous one. Do we really need to separate non-wildcard patterns and wildcard patterns? Technically, the former is a special case of the latter, and I don't think we have to optimize this routine. Simplicity is preferred, I guess.

2366

You can do

if (Sections *sec = dyn_cast<Sections>(c))
  linearlizeAst(sec)

[ruiu]

include/lld/ReaderWriter/LinkerScript.h

759–760

This cannot be replaced with lld::range since these two methods allows us to directly use this class in range-based for loops. Also, don't use lld::range anymore. We cannot justify having that generic library only inside LLD.

1159

Returning void is fine. Don't make this function return std::error_code "just in case".

[rafaelauler]

Thank you all for your patience with this patch size and for the reviews. I'll keep the next patches shorter. Comments inline.

include/lld/ReaderWriter/LinkerScript.h

168

I'm afraid I'm not on the same page, which functions are you mentioning?

1122

I was under the impression that, from the linker script perspective, we should always work with file names instead of paths. For example, to make my test case work correctly, I need to drop the path that comes from the File object and use only the file name. Only then I can match it with a linker script rule because they omit the full path. Can a linker script specify a full path to an archive?

1130

I don't understand how caching here would be error prone. I'm simply implementing the design that was suggested from the previous thread of D7915:

• Make DefaultLayout ask Sema about the order of two sections by section name (or, more precisely, section "key") and do not expose "ids".

• Since these questions are frequently asked for the same input section, we cache the result.

Which users do you refer to? You mean, the TargetLayout?

1154

Rui: Yes, I should return a const std::vector.

You are right, Shankar, but this function is currently not private to enable unit testing of linker script expression evaluation.

lib/ReaderWriter/ELF/DefaultLayout.h

229–235

Ok, I'll work on this. Thanks.

346

No problem, but first can we get a consensus on whether do we need ScriptLayout or not? I'm asking this because I only moved the code out of DefaultLayout due to Shankar's solicitation.

569

Sure

973

Unfortunately this turned out to be more complicated than intended. Here is the problem:

We can't sort everything again because this would undo the linker script order. We can only move sections that weren't assigned by the linker script.

If we stable_sort everything by content_type, we may also move sections that should be pinned by the linker script.

lib/ReaderWriter/ELF/SegmentChunks.h

437

This is used to keep in sync the file image with the memory image.

lib/ReaderWriter/LinkerScript.cpp

2099

Will do.

2111

Thanks for pointing out, I will fix this.

2198

I will refactor this.

2366

Thanks, will do.

[shankarke]

include/lld/ReaderWriter/LinkerScript.h

168

Thinking about this again, Its ok.

1122

I think so, you can specify a full path to the archive too. why not ?

1130

Yes, TargetLayout.

lib/ReaderWriter/ELF/DefaultLayout.h

346

DefaultLayout was designed as a class to handle generic ELF Layout when not having linker scripts. Some of the linker script usecases are not even relevant for the DefaultLayout. Conditionally executing things in the DefaultLayout if we have a linker script IMO is a bad design.

lib/ReaderWriter/ELF/SegmentChunks.h

437

Do you have a specific test for this ? I would like to see that to understand here.

[ruiu]

lib/ReaderWriter/ELF/DefaultLayout.h

346

I'm sorry but I completely disagree. I need to keep an eye on this kind of overkill abstraction as the history of this project shows. I spent so much time to reduce complexity of the linker, such as removal of InputGraph. Don't overdesign class hierarchy. That's going to become technical debt.

[shankarke]

lib/ReaderWriter/ELF/DefaultLayout.h

346

I dont think making changes in the DefaultLayout to accomodate LinkerScripts is a good idea.

If others / Rafael think its a great idea, please go for it.

[rafaelauler]

include/lld/ReaderWriter/LinkerScript.h

1122

I checked the manual and you are right, thanks for pointing out. I renamed this to archivePath (and the other to memberPath) to maintain consistency with file.archivePath, which also can be a name or a path.

I also deleted a function call that I was using to retrieve the file name from a path in DefaultLayout. Now I checked with GNU ld that if the linker script has a full path inside it, it must only match inputs with this exact name, and vice-verse (if the input file was specified with a full path, it does not match a rule that only specifies the file name).

1130

Ok, but in this current implementation, it is impossible for TargetLayouts to change this id, since this is private to Sema. If the user wants to change this order, we can later implement an interface to do this in a clean way that also updates our caches.

1138

I'm under the impression that std::unordered_map only accepts functors, no? I tried to remove this from the class, but I couldn't get this to work. Am I missing something? But I moved this to private.

1186

Woudn't this be equivalent to evaluating once we append to segments? I mean, the algorithm I have in mind is exactly the same. Before adding a section to the output section, we gather all expressions and put it there. This is exactly the same as putting expressions once we attach an input section to a segment.

lib/ReaderWriter/ELF/DefaultLayout.h

229–235

See above.

346

I guess currently we only have a few functions for ScriptLayout, so I merged them back into DefaultLayout. I tried to maintain them factored out from the rest of DefaultLayout, so as to be easy to see where script-related functions hook in the default behavior.

569

After a comment from Shankar explaining that we may need the full path (instead of just the file name), I removed this behavior (I don't call llvm::sys::path::filename() anymore).

lib/ReaderWriter/ELF/SegmentChunks.h

437

Well, the test attached to this patch tests this. Let me try to briefly show what's happening here:

you see the line below, "fileOffset = llvm::RoundUpToAlignment..." ?

Well, it is fixing the offset because when we assigned virtual addresses, we may have changed the address where a given chunk resides to meet alignment contraints. Thus, to keep the fileOffset in sync with the virtual addresses (memory image), this line fixes this.

However, the linker script also has power to change the current virtual address (we see now that not only alignments can change this). So I added these three lines of code that basically checks if we are calculating the address of an expression chunk and, if yes, check if our virtual address (calculated when assigning virtual addresses to chunks) is deviating from the expected value found in "lastVirtualAddress". If yes, we need to fix "fileOffset" by adding this "gap". It's just like a "custom alignment".

To see how this is necessary, any test case that uses a linker script that changes any address will suffice. The attached test case works: it requests a .ro.data section to start somewhere around address 0x506000 (actually, it is 0x50600 added to the size of previously emitted sections), but the current address for sections is around 0x500000 + previous sections size. If this code is removed, even though symbols get fixed up as though these sections reside at 0x506000, the memory content at run time will not reflect this because the file contents will be created putting everything cluttered at 0x500000.

lib/ReaderWriter/LinkerScript.cpp

2198

I gave a look at this and thinks are already refactored. The real contents of the loop are actually seen in "matchSectionName()". However, I can't merge these two different loops into one because they are iterating over quite different things: the first iterates over a range of a multimap that contains names associated with "order ids", while the second iterated over a vector. I don't see how I can "blend" these two different ranges into the same loop. But if you have an idea of how to simplify this and there is something I'm missing here, I'll gladly implement it.

[rafaelauler]

Addressed reviewers' concerns.

[ruiu]

LGTM

[shankarke]

include/lld/ReaderWriter/LinkerScript.h

1186

You cannot get all the expressions and evaluate them for a simple case like this :-

SECTIONS {

.text : {
start_text_val = .;
. = . + 1000;
end_text_val = .;
*(.text)
}

}

[rafaelauler]

include/lld/ReaderWriter/LinkerScript.h

1186

Thanks for detecting this unhandled corner case. To fix this, we need to return all expressions in "getExprs()" in the original order of the linker script. Currently, we return it in the reverse order, so "end_text_val = ." is evaluated before others. I'll reverse the order and I'll add this test as a new test case.

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));
-  }
-
-  const std::vector<std::unique_ptr<script::Parser>> &scripts() const {
-    return _scripts;
-  }
-
   // --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/DenseSet.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;
 

 /// 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; }
+  WildcardSortMode sortMode() 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 llvm::ArrayRef<const InputSection *>::const_iterator const_iterator;
   typedef std::vector<const InputSection *> VectorTy;
 
-  InputSectionsCmd(Parser &ctx, StringRef fileName, StringRef archiveName,
+  InputSectionsCmd(Parser &ctx, StringRef memberName, StringRef archiveName,
                    bool keep, WildcardSortMode fileSortMode,
                    WildcardSortMode archiveSortMode,
                    const SmallVectorImpl<const InputSection *> &sections)
-      : Command(ctx, Kind::InputSectionsCmd), _fileName(fileName),
+      : Command(ctx, Kind::InputSectionsCmd), _memberName(memberName),
         _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 memberName() const { return _memberName; }
+  StringRef archiveName() const { return _archiveName; }
+  const_iterator begin() const { return _sections.begin(); }
+  const_iterator end() const { return _sections.end(); }
+  WildcardSortMode archiveSortMode() const { return _archiveSortMode; }
+  WildcardSortMode fileSortMode() const { return _fileSortMode; }
+
 private:
-  StringRef _fileName;
+  StringRef _memberName;
   StringRef _archiveName;
   bool _keep;
   WildcardSortMode _fileSortMode;
   WildcardSortMode _archiveSortMode;
   llvm::ArrayRef<const InputSection *> _sections;
 };
 
 /// A sections-command to specify which input sections and symbols compose a
 /// given output section.
 /// Example:
 ///
 /// SECTIONS {
 ///   .x: { *(.text) ; symbol = .; }
 /// /*^~~~~~~~~~~~~~~~~~~~~~~~~~~~~^   OutputSectionDescription */
 ///   .y: { w:z(SORT(.text*)) }
 /// /*^~~~~~~~~~~~~~~~~~~~~~~~^  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;
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 populate
+/// internal data structures to be able to answer the following questions:
+///
+///   * According to the linker script, which input section goes first in the
+///     output file layout, input section A or input section B?
+///
+///   * What is the name of the output section that input section A should be
+///     mapped to?
+///
+///   * Which linker script expressions should be calculated before emitting
+///     a given section?
+///
+///   * How to evaluate a given linker script expression?
+///
+class Sema {
+public:
+  /// From the linker script point of view, this class represents the minimum
+  /// set of information to uniquely identify an input section.
+  struct SectionKey {
+    StringRef archivePath;
+    StringRef memberPath;
+    StringRef sectionName;
+  };
+
+  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));
+  }
+
+  const std::vector<std::unique_ptr<Parser>> &getLinkerScripts() {
+    return _scripts;
+  }
+
+  /// Prepare our data structures according to the linker scripts currently in
+  /// our control (control given via addLinkerScript()). Called once all linker
+  /// scripts have been parsed.
+  void perform();
+
+  /// Answer if we have layout commands (section mapping rules). If we don't,
+  /// the output file writer can assume there is no linker script special rule
+  /// to handle.
+  bool hasLayoutCommands() const { return _layoutCommands.size() > 0; }
+
+  /// Return true if this section has a mapping rule in the linker script
+  bool hasMapping(const SectionKey &key) const {
+    return getLayoutOrder(key, true) >= 0;
+  }
+
+  /// Order function - used to sort input sections in the output file according
+  /// to linker script custom mappings. Return true if lhs should appear before
+  /// rhs.
+  bool less(const SectionKey &lhs, const SectionKey &rhs) const;
+
+  /// Retrieve the name of the output section that this input section is mapped
+  /// to, according to custom linker script mappings.
+  StringRef getOutputSection(const SectionKey &key) const;
+
+  /// Retrieve all the linker script expressions that need to be evaluated
+  /// before the given section is emitted. This is *not* const because the
+  /// first section to retrieve a given set of expression is the only one to
+  /// receive it. This set is marked as "delivered" and no other sections can
+  /// retrieve this set again. If we don't do this, multiple sections may map
+  /// to the same set of expressions because of wildcards rules.
+  std::vector<const SymbolAssignment *> getExprs(const SectionKey &key);
+
+  /// Evaluate a single linker script expression according to our current
+  /// context (symbol table). This function is *not* constant because it can
+  /// update our symbol table with new symbols calculated in this expression.
+  std::error_code evalExpr(const SymbolAssignment *assgn, uint64_t &curPos);
+
+  void dump() const;
+
+private:
+  /// A custom hash operator to teach the STL how to handle our custom keys.
+  /// This will be used in our hash table mapping Sections to a Layout Order
+  /// number (caching results).
+  struct SectionKeyHash {
+    int64_t operator()(const SectionKey &k) const {
+      return llvm::hash_combine(k.archivePath, k.memberPath, k.sectionName);
+    }
+  };
+
+  /// Teach the STL when two section keys are the same. This will be used in
+  /// our hash table mapping Sections to a Layout Order number (caching results)
+  struct SectionKeyEq {
+    bool operator()(const SectionKey &lhs, const SectionKey &rhs) const {
+      return ((lhs.archivePath == rhs.archivePath) &&
+              (lhs.memberPath == rhs.memberPath) &&
+              (lhs.sectionName == rhs.sectionName));
+    }
+  };
+
+  /// Given an order id, check if it matches the tuple
+  /// <archivePath, memberPath, sectionName> and returns the
+  /// internal id that matched, or -1 if no matches.
+  int matchSectionName(int id, const SectionKey &key) const;
+
+  /// Returns a number that will determine the order of this input section
+  /// in the final layout. If coarse is true, we simply return the layour order
+  /// of the higher-level node InputSectionsCmd, used to order input sections.
+  /// If coarse is false, we return the layout index down to the internal
+  /// InputSectionsCmd arrangement, used to get the set of preceding linker
+  ///expressions.
+  int getLayoutOrder(const SectionKey &key, bool coarse) const;
+
+  /// Compare two sections that have the same mapping rule (i.e., are matched
+  /// by the same InputSectionsCmd).
+  /// Determine if lhs < rhs by analyzing the InputSectionsCmd structure.
+  bool localCompare(int order, const SectionKey &lhs,
+                    const SectionKey &rhs) const;
+
+
+  /// Our goal with all linearizeAST overloaded functions is to
+  /// traverse the linker script AST while putting nodes in a vector and
+  /// thus enforcing order among nodes (which comes first).
+  ///
+  /// The order among nodes is determined by their indexes in this vector
+  /// (_layoutCommands). This index allows us to solve the problem of
+  /// establishing the order among two different input sections: we match each
+  /// input sections with their respective layout command and use the indexes
+  /// of these commands to order these sections.
+  ///
+  /// Example:
+  ///
+  ///     Given the linker script:
+  ///       SECTIONS {
+  ///         .text : { *(.text) }
+  ///         .data : { *(.data) }
+  ///       }
+  ///
+  ///     The _layoutCommands vector should contain:
+  ///         id 0 : <OutputSectionDescription> (_sectionName = ".text")
+  ///         id 1 : <InputSectionsCmd> (_memberName = "*")
+  ///         id 2 : <InputSectionName> (_name = ".text)
+  ///         id 3 : <OutputSectionDescription> (_sectionName = ".data")
+  ///         id 4 : <InputSectionsCmd> (_memberName = "*")
+  ///         id 5 : <InputSectionName> (_name = ".data")
+  ///
+  ///     If we need to sort the following input sections:
+  ///
+  ///     input section A:  .text from libc.a (member errno.o)
+  ///     input section B:  .data from libc.a (member write.o)
+  ///
+  ///     Then we match input section A with the InputSectionsCmd of id 1, and
+  ///     input section B with the InputSectionsCmd of id 4. Since 1 < 4, we
+  ///     put A before B.
+  ///
+  /// The second problem handled by the linearization of the AST is the task
+  /// of finding all preceding expressions that need to be calculated before
+  /// emitting a given section. This task is easier to deal with when all nodes
+  /// are in a vector because otherwise we would need to traverse multiple
+  /// levels of the AST to find the set of expressions that preceed a layout
+  /// command.
+  ///
+  /// The linker script commands that are linearized ("layout commands") are:
+  ///
+  ///   * 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
+  ///   * SymbolAssignment, containing an expression that may
+  ///     change the address where the linker is outputting data
+  ///
+  void linearizeAST(const Sections *sections);
+  void linearizeAST(const InputSectionsCmd *inputSections);
+  void linearizeAST(const InputSection *inputSection);
+
+  void perform(const LinkerScript *ls);
+
+  std::vector<std::unique_ptr<Parser>> _scripts;
+  std::vector<const Command *> _layoutCommands;
+  std::unordered_multimap<std::string, int> _memberToLayoutOrder;
+  std::vector<std::pair<StringRef, int>> _memberNameWildcards;
+  mutable std::unordered_map<SectionKey, int, SectionKeyHash, SectionKeyEq>
+      _cacheSectionOrder, _cacheExpressionOrder;
+  llvm::DenseSet<int> _deliveredExprs;
+
+  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/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/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) {}
   virtual ~Chunk() {}

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;
+  virtual StringRef getOutputSectionName(StringRef archivePath,
+                                         StringRef memberPath,
+                                         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:
   AbsoluteAtomIterT findAbsoluteAtom(StringRef name) {
     return std::find_if(_absoluteAtoms.begin(), _absoluteAtoms.end(),
                         FindByName(name));
   }
 
   // Output sections with the same name into a OutputSection
   void createOutputSections();
 
+  /// \brief Sort the sections by their order as defined by the layout,
+  /// preparing all sections to be assigned to a segment.
+  virtual void sortInputSections();
+
+  /// \brief Add extra chunks to a segment just before including the input
+  /// section given by <archivePath, memberPath, sectionName>. This
+  /// is used to add linker script expressions before each section.
+  virtual void addExtraChunksToSegment(Segment<ELFT> *segment,
+                                       StringRef archivePath,
+                                       StringRef memberPath,
+                                       StringRef sectionName);
+
   void assignSectionsToSegments() override;
 
   void assignVirtualAddress() override;
 
   void assignFileOffsetsForMiscSections();
 
   range<AbsoluteAtomIterT> absoluteAtoms() { return _absoluteAtoms; }
 
   void addSection(Chunk<ELFT> *c) { _sections.push_back(c); }
 
   void finalize() {
protected:
   std::vector<OutputSection<ELFT> *> _outputSections;
   ELFHeader<ELFT> *_elfHeader;
   ProgramHeader<ELFT> *_programHeader;
   unique_bump_ptr<RelocationTable<ELFT>> _dynamicRelocationTable;
   unique_bump_ptr<RelocationTable<ELFT>> _pltRelocationTable;
   std::vector<lld::AtomLayout *> _absoluteAtoms;
   AtomSetT _referencedDynAtoms;
   llvm::StringSet<> _copiedDynSymNames;
-  const ELFLinkingContext &_context;
+  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:
     return llvm::StringSwitch<Layout::SectionOrder>(name)
         .StartsWith(".eh_frame_hdr", ORDER_EH_FRAMEHDR)
         .StartsWith(".eh_frame", ORDER_EH_FRAME)
         .StartsWith(".init", ORDER_INIT)
if (da->sectionChoice() == DefinedAtom::sectionBasedOnContent) {
     }
   }
   return da->customSectionName();
 }
 
 /// \brief This maps the input sections to the output section names.
 template <class ELFT>
 StringRef
-DefaultLayout<ELFT>::getOutputSectionName(StringRef inputSectionName) const {
+DefaultLayout<ELFT>::getOutputSectionName(StringRef archivePath,
+                                          StringRef memberPath,
+                                          StringRef inputSectionName) const {
+  StringRef outputSectionName;
+  if (_linkerScriptSema.hasLayoutCommands() &&
+      !(outputSectionName = _linkerScriptSema.getOutputSection(
+           {archivePath, memberPath, inputSectionName})).empty())
+    return outputSectionName;
+
   return llvm::StringSwitch<StringRef>(inputSectionName)
       .StartsWith(".text", ".text")
       .StartsWith(".ctors", ".ctors")
       .StartsWith(".dtors", ".dtors")
       .StartsWith(".rodata", ".rodata")
       .StartsWith(".gcc_except_table", ".gcc_except_table")
       .StartsWith(".data.rel.ro", ".data.rel.ro")
       .StartsWith(".data.rel.local", ".data.rel.local")
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));
+
+  newSec->setOutputSectionName(getOutputSectionName(
+      da->file().archivePath(), da->file().memberPath(), sectionName));
   newSec->setOrder(sectionOrder);
+  newSec->setArchiveNameOrPath(da->file().archivePath());
+  newSec->setMemberNameOrPath(da->file().memberPath());
   _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)) {
for (auto &si : _sections) {
     outputSection->appendSection(si);
   }
 }
 
 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();
-  });
+  sortInputSections();
   // 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);
             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);
           segmentInsert.first->second = segment;
           _segments.push_back(segment);
         }
+        // Insert chunks with linker script expressions that occur at this
+        // point, just before appending a new input section
+        addExtraChunksToSegment(segment, section->archivePath(),
+                                section->memberPath(),
+                                section->inputSectionName());
         segment->append(section);
       }
     }
   }
   if (_context.isDynamic() && !_context.isDynamicLibrary()) {
     Segment<ELFT> *segment =
         new (_allocator) ProgramHeaderSegment<ELFT>(_context);
     _segments.push_back(segment);
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();
for (auto si : _sections) {
     if (section && DefaultLayout<ELFT>::hasOutputSegment(section))
       continue;
     fileoffset = llvm::RoundUpToAlignment(fileoffset, si->alignment());
     si->setFileOffset(fileoffset);
     si->setVirtualAddr(0);
     fileoffset += si->fileSize();
   }
 }
+
+template <class ELFT> void DefaultLayout<ELFT>::sortInputSections() {
+  // First, sort according to default layout's order
+  std::stable_sort(
+      _sections.begin(), _sections.end(),
+      [](Chunk<ELFT> *A, Chunk<ELFT> *B) { return A->order() < B->order(); });
+
+  if (!_linkerScriptSema.hasLayoutCommands())
+    return;
+
+  // Sort the sections by their order as defined by the linker script
+  std::stable_sort(this->_sections.begin(), this->_sections.end(),
+                   [this](Chunk<ELFT> *A, Chunk<ELFT> *B) {
+                     auto *a = dyn_cast<Section<ELFT>>(A);
+                     auto *b = dyn_cast<Section<ELFT>>(B);
+
+                     if (a == nullptr)
+                       return false;
+                     if (b == nullptr)
+                       return true;
+
+                     return _linkerScriptSema.less(
+                         {a->archivePath(), a->memberPath(),
+                          a->inputSectionName()},
+                         {b->archivePath(), b->memberPath(),
+                          b->inputSectionName()});
+                   });
+  // Now try to arrange sections with no mapping rules to sections with
+  // similar content
+  auto p = this->_sections.begin();
+  // Find first section that has no assigned rule id
+  while (p != this->_sections.end()) {
+    auto *sect = dyn_cast<AtomSection<ELFT>>(*p);
+    if (!sect)
+      break;
+
+    if (!_linkerScriptSema.hasMapping({sect->archivePath(),
+                                       sect->memberPath(),
+                                       sect->inputSectionName()}))
+      break;
+
+    ++p;
+  }
+  // For all sections that have no assigned rule id, try to move them near a
+  // section with similar contents
+  if (p != this->_sections.begin()) {
+    for (; p != this->_sections.end(); ++p) {
+      auto q = p;
+      --q;
+      while (q != this->_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);
+      }
+    }
+  }
+}
+
+template <class ELFT>
+void DefaultLayout<ELFT>::addExtraChunksToSegment(Segment<ELFT> *segment,
+                                                  StringRef archivePath,
+                                                  StringRef memberPath,
+                                                  StringRef sectionName) {
+  if (!_linkerScriptSema.hasLayoutCommands())
+    return;
+
+  std::vector<const script::SymbolAssignment *> exprs =
+      _linkerScriptSema.getExprs({archivePath, memberPath, sectionName});
+  for (auto expr : exprs) {
+    auto expChunk =
+        new (this->_allocator) ExpressionChunk<ELFT>(this->_context, expr);
+    segment->append(expChunk);
+  }
+}
+
 } // end namespace elf
 } // end namespace lld
 
 #endif

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/SectionChunks.h

public:
   virtual StringRef inputSectionName() const { return _inputSectionName; }
 
   virtual StringRef outputSectionName() const { return _outputSectionName; }
 
   virtual void setOutputSectionName(StringRef outputSectionName) {
     _outputSectionName = outputSectionName;
   }
 
+  void setArchiveNameOrPath(StringRef name) { _archivePath = name; }
+
+  void setMemberNameOrPath(StringRef name) { _memberPath = name; }
+
+  StringRef archivePath() { return _archivePath; }
+
+  StringRef memberPath() { return _memberPath; }
+
 protected:
   /// \brief OutputSection this Section is a member of, or nullptr.
   OutputSection<ELFT> *_outputSection;
   /// \brief ELF SHF_* flags.
   uint64_t _flags;
   /// \brief The size of each entity.
   uint64_t _entSize;
   /// \brief ELF SHT_* type.
   uint32_t _type;
   /// \brief sh_link field.
   uint32_t _link;
   /// \brief the sh_info field.
   uint32_t _info;
   /// \brief Is this the first section in the output section.
   bool _isFirstSectionInOutputSection;
   /// \brief the output ELF segment type of this section.
   Layout::SegmentType _segmentType;
   /// \brief Input section name.
   StringRef _inputSectionName;
   /// \brief Output section name.
   StringRef _outputSectionName;
+  StringRef _archivePath;
+  StringRef _memberPath;
 };
 
 /// \brief A section containing atoms.
 template <class ELFT> class AtomSection : public Section<ELFT> {
 public:
   AtomSection(const ELFLinkingContext &context, StringRef sectionName,
               int32_t contentType, int32_t permissions, int32_t order)
       : Section<ELFT>(context, sectionName, "AtomSection",

lib/ReaderWriter/ELF/SegmentChunks.h

enum SegmentOrder {
     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:
   std::vector<Chunk<ELFT> *> _sections;
   std::vector<SegmentSlice<ELFT> *> _segmentSlices;
   Layout::SegmentType _segmentType;
   uint64_t _flags;
   int64_t _atomflags;
   llvm::BumpPtrAllocator _segmentAllocate;
 };
 
+/// This chunk represents a linker script expression that needs to be calculated
+/// at the time the virtual addresses for the parent segment are being assigned.
+template <class ELFT> class ExpressionChunk : public Chunk<ELFT> {
+public:
+  ExpressionChunk(ELFLinkingContext &ctx, const script::SymbolAssignment *expr)
+      : Chunk<ELFT>(StringRef(), Chunk<ELFT>::Kind::Expression, ctx),
+        _expr(expr), _linkerScriptSema(ctx.linkerScriptSema()) {
+    this->_alignment = 1;
+  }
+
+  static bool classof(const Chunk<ELFT> *c) {
+    return c->kind() == Chunk<ELFT>::Kind::Expression;
+  }
+
+  int getContentType() const override {
+    return Chunk<ELFT>::ContentType::Unknown;
+  }
+  void write(ELFWriter *, TargetLayout<ELFT> &,
+             llvm::FileOutputBuffer &) override {}
+  void doPreFlight() override {}
+  void finalize() override {}
+
+  std::error_code evalExpr(uint64_t &curPos) {
+    return _linkerScriptSema.evalExpr(_expr, curPos);
+  }
+
+private:
+  const script::SymbolAssignment *_expr;
+  script::Sema &_linkerScriptSema;
+};
+
 /// \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) {
     this->_alignment = 8;
     this->_flags = (llvm::ELF::SHF_ALLOC | llvm::ELF::SHF_EXECINSTR);

 
 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))
+        expr->evalExpr(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))
+        expr->evalExpr(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)
-      : DefaultLayout<ELFT>(context) {}
+  TargetLayout(ELFLinkingContext &context) : DefaultLayout<ELFT>(context) {}
 };
 } // end namespace elf
 } // end namespace lld
 
 #endif

lib/ReaderWriter/LinkerScript.cpp

 }
 
 // InputSectionsCmd functions
 void InputSectionsCmd::dump(raw_ostream &os) const {
   if (_keep)
     os << "KEEP(";
 
   int numParen = dumpSortDirectives(os, _fileSortMode);
-  os << _fileName;
+  os << _memberName;
   for (int i = 0; i < numParen; ++i)
     os << ")";
 
   if (_archiveName.size() > 0) {
     os << ":";
     numParen = dumpSortDirectives(os, _archiveSortMode);
     os << _archiveName;
     for (int i = 0; i < numParen; ++i)
assert((_tok._kind == Token::identifier || _tok._kind == Token::colon ||
           _tok._kind == Token::kw_sort_by_alignment ||
           _tok._kind == Token::kw_sort_by_init_priority ||
           _tok._kind == Token::kw_sort_none) &&
          "Expected input section first tokens!");
   int numParen = 1;
   bool keep = false;
   WildcardSortMode fileSortMode = WildcardSortMode::NA;
   WildcardSortMode archiveSortMode = WildcardSortMode::NA;
-  StringRef fileName;
+  StringRef memberName;
   StringRef archiveName;
 
   if (_tok._kind == Token::kw_keep) {
     consumeToken();
     if (!expectAndConsume(Token::l_paren, "expected ("))
       return nullptr;
     ++numParen;
     keep = true;
   }
 
   // Input name
   if (_tok._kind != Token::colon) {
     int numParen = parseSortDirectives(fileSortMode);
     if (numParen == -1)
       return nullptr;
-    fileName = _tok._range;
+    memberName = _tok._range;
     consumeToken();
     if (numParen) {
       while (numParen--)
         if (!expectAndConsume(Token::r_paren, "expected )"))
           return nullptr;
     }
   }
   if (_tok._kind == Token::colon) {
if (!expectAndConsume(Token::r_paren, "expected )"))
     return nullptr;
     }
   }
 
   SmallVector<const InputSection *, 8> inputSections;
 
   if (_tok._kind != Token::l_paren)
     return new (_alloc)
-        InputSectionsCmd(*this, fileName, archiveName, keep, fileSortMode,
+        InputSectionsCmd(*this, memberName, archiveName, keep, fileSortMode,
                          archiveSortMode, inputSections);
   consumeToken();
 
   while (_tok._kind == Token::identifier ||
          _tok._kind == Token::kw_exclude_file ||
          _tok._kind == Token::kw_sort_by_name ||
          _tok._kind == Token::kw_sort_by_alignment ||
          _tok._kind == Token::kw_sort_by_init_priority ||
default:
       llvm_unreachable("Unknown token");
     }
   }
 
   for (int i = 0; i < numParen; ++i)
     if (!expectAndConsume(Token::r_paren, "expected )"))
       return nullptr;
   return new (_alloc)
-      InputSectionsCmd(*this, fileName, archiveName, keep, fileSortMode,
+      InputSectionsCmd(*this, memberName, archiveName, keep, fileSortMode,
                        archiveSortMode, inputSections);
 }
 
 const OutputSectionDescription *Parser::parseOutputSectionDescription() {
   assert((_tok._kind == Token::kw_discard || _tok._kind == Token::identifier) &&
          "Expected /DISCARD/ or identifier!");
   StringRef sectionName;
   const Expression *address = nullptr;
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);
 }
 
-} // end namespace script
+// Sema member functions
+Sema::Sema()
+    : _scripts(), _layoutCommands(), _memberToLayoutOrder(),
+      _memberNameWildcards(), _cacheSectionOrder(), _cacheExpressionOrder(),
+      _deliveredExprs(), _symbolTable() {}
+
+void Sema::perform() {
+  for (auto &parser : _scripts)
+    perform(parser->get());
+}
+
+bool Sema::less(const SectionKey &lhs, const SectionKey &rhs) const {
+  int a = getLayoutOrder(lhs, true);
+  int b = getLayoutOrder(rhs, true);
+
+  if (a != b) {
+    if (a < 0)
+      return false;
+    if (b < 0)
+      return true;
+    return a < b;
+  }
+
+  // If both sections are not mapped anywhere, they have the same order
+  if (a < 0)
+    return false;
+
+  // If both sections fall into the same layout order, we need to find their
+  // relative position as written in the (InputSectionsCmd).
+  return localCompare(a, lhs, rhs);
+}
+
+StringRef Sema::getOutputSection(const SectionKey &key) const {
+  int layoutOrder = getLayoutOrder(key, true);
+  if (layoutOrder < 0)
+    return StringRef();
+
+  for (int i = layoutOrder - 1; i >= 0; --i) {
+    if (!isa<OutputSectionDescription>(_layoutCommands[i]))
+      continue;
+
+    const OutputSectionDescription *out =
+        dyn_cast<OutputSectionDescription>(_layoutCommands[i]);
+    return out->name();
+  }
+
+  return StringRef();
+}
+
+std::vector<const SymbolAssignment *>
+Sema::getExprs(const SectionKey &key) {
+  int layoutOrder = getLayoutOrder(key, false);
+  auto ans = std::vector<const SymbolAssignment *>();
+
+  if (layoutOrder < 0 || _deliveredExprs.count(layoutOrder) > 0)
+    return ans;
+
+  for (int i = layoutOrder - 1; i >= 0; --i) {
+    if (isa<InputSection>(_layoutCommands[i]))
+      break;
+    if (auto assgn = dyn_cast<SymbolAssignment>(_layoutCommands[i]))
+      ans.push_back(assgn);
+  }
+
+  // Mark this layout number as delivered
+  _deliveredExprs.insert(layoutOrder);
+  return ans;
+}
+
+std::error_code Sema::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 Sema::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 < _layoutCommands.size(); ++i) {
+    os << "LayoutOrder " << i << ":\n";
+    _layoutCommands[i]->dump(os);
+    os << "\n\n";
+  }
+}
+
+/// Given a string "pattern" with wildcard characters, return true if it
+/// matches "name". This function is useful when checking if a given name
+/// pattern written in the linker script, i.e. ".text*", should match
+/// ".text.anytext".
+static bool wildcardMatch(StringRef pattern, StringRef name) {
+  auto i = name.begin();
+
+  // Check if each char in pattern also appears in our input name, handling
+  // special wildcard characters.
+  for (auto j = pattern.begin(), e = pattern.end(); j != e; ++j) {
+    if (i == name.end())
+      return false;
+
+    switch (*j) {
+    case '*':
+      while (!wildcardMatch(pattern.drop_front(j - pattern.begin() + 1),
+                            name.drop_front(i - name.begin() + 1))) {
+        if (i == name.end())
+          return false;
+        ++i;
+      }
+      break;
+    case '?':
+      // Matches any character
+      break;
+    case '[': {
+      // Matches a range of characters specified between brackets
+      size_t end = pattern.find(']', j - pattern.begin());
+      if (end == pattern.size())
+        return false;
+
+      StringRef chars = pattern.slice(j - pattern.begin(), end);
+      if (chars.find(i) == StringRef::npos)
+        return false;
+
+      j = pattern.begin() + end;
+      break;
+    }
+    case '\\':
+      ++j;
+      if (*j != *i)
+        return false;
+      break;
+    default:
+      // No wildcard character means we must match exactly the same char
+      if (*j != *i)
+        return false;
+      break;
+    }
+    ++i;
+  }
+
+  // If our pattern has't consumed the entire string, it is not a match
+  return i == name.end();
+}
+
+int Sema::matchSectionName(int id, const SectionKey &key) const {
+  const InputSectionsCmd *cmd = dyn_cast<InputSectionsCmd>(_layoutCommands[id]);
+
+  if (!cmd || !wildcardMatch(cmd->archiveName(), key.archivePath))
+    return -1;
+
+  while ((size_t)++id < _layoutCommands.size() &&
+         (isa<InputSection>(_layoutCommands[id]))) {
+    if (isa<InputSectionSortedGroup>(_layoutCommands[id]))
+      continue;
+
+    const InputSectionName *in =
+        dyn_cast<InputSectionName>(_layoutCommands[id]);
+    if (wildcardMatch(in->name(), key.sectionName))
+      return id;
+  }
+  return -1;
+}
+
+int Sema::getLayoutOrder(const SectionKey &key, bool coarse) const {
+  // First check if we already answered this layout question
+  if (coarse) {
+    auto entry = _cacheSectionOrder.find(key);
+    if (entry != _cacheSectionOrder.end())
+      return entry->second;
+  } else {
+    auto entry = _cacheExpressionOrder.find(key);
+    if (entry != _cacheExpressionOrder.end())
+      return entry->second;
+  }
+
+  // Try to match exact file name
+  auto range = _memberToLayoutOrder.equal_range(key.memberPath);
+  for (auto I = range.first, E = range.second; I != E; ++I) {
+    int order = I->second;
+    int exprOrder = -1;
+
+    if ((exprOrder = matchSectionName(order, key)) >= 0) {
+      if (coarse) {
+        _cacheSectionOrder.insert(std::make_pair(key, order));
+        return order;
+      }
+      _cacheExpressionOrder.insert(std::make_pair(key, exprOrder));
+      return exprOrder;
+    }
+  }
+
+  // If we still couldn't find a rule for this input section, try to match
+  // wildcards
+  for (auto I = _memberNameWildcards.begin(), E = _memberNameWildcards.end();
+       I != E; ++I) {
+    if (!wildcardMatch(I->first, key.memberPath))
+      continue;
+    int order = I->second;
+    int exprOrder = -1;
+
+    if ((exprOrder = matchSectionName(order, key)) >= 0) {
+      if (coarse) {
+        _cacheSectionOrder.insert(std::make_pair(key, order));
+        return order;
+      }
+      _cacheExpressionOrder.insert(std::make_pair(key, exprOrder));
+      return exprOrder;
+    }
+  }
+
+  _cacheSectionOrder.insert(std::make_pair(key, -1));
+  _cacheExpressionOrder.insert(std::make_pair(key, -1));
+  return -1;
+}
+
+static bool compareSortedNames(WildcardSortMode sortMode, StringRef lhs,
+                               StringRef rhs) {
+  switch (sortMode) {
+  case WildcardSortMode::None:
+  case WildcardSortMode::NA:
+    return false;
+  case WildcardSortMode::ByAlignment:
+  case WildcardSortMode::ByInitPriority:
+  case WildcardSortMode::ByAlignmentAndName:
+    assert(false && "Unimplemented sort order");
+    break;
+  case WildcardSortMode::ByName:
+    return lhs.compare(rhs) < 0;
+  case WildcardSortMode::ByNameAndAlignment:
+    int compare = lhs.compare(rhs);
+    if (compare != 0)
+      return compare < 0;
+    return compareSortedNames(WildcardSortMode::ByAlignment, lhs, rhs);
+  }
+  return false;
+}
+
+static bool sortedGroupContains(const InputSectionSortedGroup *cmd,
+                                const Sema::SectionKey &key) {
+  for (const InputSection *child : *cmd) {
+    if (auto i = dyn_cast<InputSectionName>(child)) {
+      if (wildcardMatch(i->name(), key.sectionName))
+        return true;
+      continue;
+    }
+
+    auto *sortedGroup = dyn_cast<InputSectionSortedGroup>(child);
+    assert(sortedGroup && "Expected InputSectionSortedGroup object");
+
+    if (sortedGroupContains(sortedGroup, key))
+      return true;
+  }
+
+  return false;
+}
+
+bool Sema::localCompare(int order, const SectionKey &lhs,
+                        const SectionKey &rhs) const {
+  const InputSectionsCmd *cmd =
+      dyn_cast<InputSectionsCmd>(_layoutCommands[order]);
+
+  assert(cmd && "Invalid InputSectionsCmd index");
+
+  if (lhs.archivePath != rhs.archivePath)
+    return compareSortedNames(cmd->archiveSortMode(), lhs.archivePath,
+                              rhs.archivePath);
+
+  if (lhs.memberPath != rhs.memberPath)
+    return compareSortedNames(cmd->fileSortMode(), lhs.memberPath,
+                              rhs.memberPath);
+
+  // Both sections come from the same exact same file and rule. Start walking
+  // through input section names as written in the linker script and the
+  // first one to match will have higher priority.
+  for (const InputSection *inputSection : *cmd) {
+    if (auto i = dyn_cast<InputSectionName>(inputSection)) {
+      // If both match, return false (both have equal priority)
+      // If rhs match, return false (rhs has higher priority)
+      if (wildcardMatch(i->name(), rhs.sectionName))
+        return false;
+      //  If lhs matches first, it has priority over rhs
+      if (wildcardMatch(i->name(), lhs.sectionName))
+        return true;
+      continue;
+    }
+
+    // Handle sorted subgroups specially
+    auto *sortedGroup = dyn_cast<InputSectionSortedGroup>(inputSection);
+    assert(sortedGroup && "Expected InputSectionSortedGroup object");
+
+    bool a = sortedGroupContains(sortedGroup, lhs);
+    bool b = sortedGroupContains(sortedGroup, rhs);
+    if (a && !b)
+      return false;
+    if (b && !a)
+      return true;
+    if (!a && !a)
+      continue;
+
+    return compareSortedNames(sortedGroup->sortMode(), lhs.sectionName,
+                              rhs.sectionName);
+  }
+
+  llvm_unreachable("");
+  return false;
+}
+
+static bool hasWildcard(StringRef name) {
+  for (auto ch : name)
+    if (ch == '*' || ch == '?' || ch == '[' || ch == '\\')
+      return true;
+  return false;
+}
+
+void Sema::linearizeAST(const InputSection *inputSection) {
+  if (isa<InputSectionName>(inputSection)) {
+    _layoutCommands.push_back(inputSection);
+    return;
+  }
+
+  auto *sortedGroup = dyn_cast<InputSectionSortedGroup>(inputSection);
+  assert(sortedGroup && "Expected InputSectionSortedGroup object");
+
+  for (const InputSection *child : *sortedGroup) {
+    linearizeAST(child);
+  }
+}
+
+void Sema::linearizeAST(const InputSectionsCmd *inputSections) {
+  StringRef memberName = inputSections->memberName();
+  // Populate our maps for fast lookup of InputSectionsCmd
+  if (hasWildcard(memberName))
+    _memberNameWildcards.push_back(
+        std::make_pair(memberName, (int)_layoutCommands.size()));
+  else if (!memberName.empty())
+    _memberToLayoutOrder.insert(
+        std::make_pair(memberName.str(), (int)_layoutCommands.size()));
+
+  _layoutCommands.push_back(inputSections);
+  for (const InputSection *inputSection : *inputSections)
+    linearizeAST(inputSection);
+}
+
+void Sema::linearizeAST(const Sections *sections) {
+  for (const Command *sectionCommand : *sections) {
+    if (isa<SymbolAssignment>(sectionCommand)) {
+      _layoutCommands.push_back(sectionCommand);
+      continue;
+    }
+
+    if (!isa<OutputSectionDescription>(sectionCommand))
+      continue;
+
+    _layoutCommands.push_back(sectionCommand);
+    auto *outSection = dyn_cast<OutputSectionDescription>(sectionCommand);
+
+    for (const Command *outSecCommand : *outSection) {
+      if (isa<SymbolAssignment>(outSecCommand)) {
+        _layoutCommands.push_back(outSecCommand);
+        continue;
+      }
+
+      if (!isa<InputSectionsCmd>(outSecCommand))
+        continue;
+
+      linearizeAST(dyn_cast<InputSectionsCmd>(outSecCommand));
+    }
+  }
+}
+
+void Sema::perform(const LinkerScript *ls) {
+  for (const Command *c : ls->_commands) {
+    if (const Sections *sec = dyn_cast<Sections>(c))
+      linearizeAST(sec);
+  }
+}
+
+} // End namespace script
 } // end namespace lld

test/elf/linkerscript/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/linkerscript/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/linkerscript/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/linkerscript/sections-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: mkdir -p %T
+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
+*/

test/elf/linkerscript/sections-with-wildcards.test

+/*
+Tests a linker script that uses the SECTIONS command with rules containing
+wildcards and simple SORT directives.
+
+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;
+  .foo : { SORT(*)(.text .rodata*) }
+}
+
+/*
+RUN: mkdir -p %T
+RUN: yaml2obj -format=elf %p/Inputs/prog1.o.yaml -o=%T/p1.o
+RUN: yaml2obj -format=elf %p/Inputs/prog2.o.yaml -o=%T/p2.o
+RUN: yaml2obj -format=elf %p/Inputs/prog3.o.yaml -o=%T/p3.o
+RUN: cd %T
+
+RUN: lld -flavor gnu  -target x86_64 -T %s p1.o p2.o p3.o \
+RUN:   -static -o %t1
+RUN: llvm-readobj -s %t1 | FileCheck -check-prefix CHECKSECTIONS %s
+
+CHECKSECTIONS:       Index: 1
+CHECKSECTIONS:       Name: .foo
+CHECKSECTIONS:       Address: 0x500000
+CHECKSECTIONS:       Size: 101
+
+RUN: llvm-readobj -symbols %t1 | FileCheck -check-prefix CHECKSYMS %s
+
+CHECKSYMS:      Name: main
+CHECKSYMS-NEXT: Value: 0x500000
+
+CHECKSYMS:      Name: prog2
+CHECKSYMS-NEXT: Value: 0x500030
+
+CHECKSYMS:      Name: write
+CHECKSYMS-NEXT: Value: 0x500050
+
+CHECKSYMS:      Name: _start
+CHECKSYMS-NEXT: Value: 0x500058
+*/

unittests/DriverTests/GnuLdDriverTest.cpp

TEST_F(LinkerScriptTest, IgnoreSearchDirNoStdLib) {
   std::vector<StringRef> paths = _ctx->getSearchPaths();
   EXPECT_EQ((size_t)0, paths.size());
 }
 
 TEST_F(LinkerScriptTest, ExprEval) {
   parse("SECTIONS { symbol = 0x4000 + 0x40; \n"
         ". = (symbol >= 0x4040)? (0x5001 * 2 & 0xFFF0) << 1 : 0}");
 
-  EXPECT_EQ((size_t)1, _ctx->scripts().size());
+  EXPECT_EQ((size_t)1, _ctx->linkerScriptSema().getLinkerScripts().size());
 
-  script::LinkerScript *ls = _ctx->scripts()[0]->get();
+  script::LinkerScript *ls =
+      _ctx->linkerScriptSema().getLinkerScripts()[0]->get();
   EXPECT_EQ((size_t)1, ls->_commands.size());
 
   auto *secs = dyn_cast<const script::Sections>(*ls->_commands.begin());
   EXPECT_TRUE(secs != nullptr);
   EXPECT_EQ(2, secs->end() - secs->begin());
 
   auto command = secs->begin();
   auto *sa1 = dyn_cast<const script::SymbolAssignment>(*command);