[LinkerScript] Implement semantics for simple sections mappings

This commit implements the behaviour of the SECTIONS linker script directive,
used to not only define a custom mapping between input and output sections, but
also order input sections in the output file. To do this, we modify
DefaultLayout with hooks at important places that allow us to re-order input
sections according to a custom order. We also add a hook in SegmentChunk to
allow us to calculate linker script expressions while assigning virtual
addresses to the input sections that live in a segment.

Not all SECTIONS constructs are currently supported, but only the ones that do
not use special sort orders. It adds two LIT test as practical examples of
which sections directives are currently supported.

In terms of high-level changes, it creates 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 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.

http://reviews.llvm.org/D8157

llvm-svn: 232402

9 files changed, 606 insertions, 35 deletions

diff --git a/lld/lib/ReaderWriter/ELF/Chunk.h b/lld/lib/ReaderWriter/ELF/Chunk.h
index 87688ef972c..2658d023b3a 100644
--- a/lld/lib/ReaderWriter/ELF/Chunk.h
+++ b/lld/lib/ReaderWriter/ELF/Chunk.h
@@ -39,7 +39,8 @@ public:
                        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 };
diff --git a/lld/lib/ReaderWriter/ELF/DefaultLayout.h b/lld/lib/ReaderWriter/ELF/DefaultLayout.h
index 49ada5937ff..13d2f5c1946 100644
--- a/lld/lib/ReaderWriter/ELF/DefaultLayout.h
+++ b/lld/lib/ReaderWriter/ELF/DefaultLayout.h
@@ -169,7 +169,8 @@ public:
 
   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,
@@ -180,13 +181,15 @@ public:
   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;
@@ -215,6 +218,18 @@ public:
   // 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;
@@ -323,7 +338,8 @@ protected:
   std::vector<lld::AtomLayout *> _absoluteAtoms;
   AtomSetT _referencedDynAtoms;
   llvm::StringSet<> _copiedDynSymNames;
-  const ELFLinkingContext &_context;
+  ELFLinkingContext &_context;
+  script::Sema &_linkerScriptSema;
 };
 
 template <class ELFT>
@@ -415,7 +431,15 @@ DefaultLayout<ELFT>::getInputSectionName(const DefinedAtom *da) const {
 /// \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")
@@ -533,17 +557,20 @@ 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;
@@ -563,8 +590,8 @@ DefaultLayout<ELFT>::addAtom(const Atom *atom) {
     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) {
@@ -632,10 +659,7 @@ 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
@@ -686,8 +710,8 @@ template <class ELFT> void DefaultLayout<ELFT>::assignSectionsToSegments() {
           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);
           }
@@ -713,11 +737,16 @@ template <class ELFT> void DefaultLayout<ELFT>::assignSectionsToSegments() {
         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);
       }
     }
@@ -754,6 +783,7 @@ DefaultLayout<ELFT>::assignVirtualAddress() {
       break;
     }
   }
+  assert(firstLoadSegment != nullptr && "No loadable segment!");
   firstLoadSegment->prepend(_programHeader);
   firstLoadSegment->prepend(_elfHeader);
   bool newSegmentHeaderAdded = true;
@@ -870,6 +900,86 @@ void DefaultLayout<ELFT>::assignFileOffsetsForMiscSections() {
     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
 
diff --git a/lld/lib/ReaderWriter/ELF/ELFLinkingContext.cpp b/lld/lib/ReaderWriter/ELF/ELFLinkingContext.cpp
index 29388c239fe..c7dffda8a46 100644
--- a/lld/lib/ReaderWriter/ELF/ELFLinkingContext.cpp
+++ b/lld/lib/ReaderWriter/ELF/ELFLinkingContext.cpp
@@ -47,7 +47,7 @@ ELFLinkingContext::ELFLinkingContext(
       _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>());
diff --git a/lld/lib/ReaderWriter/ELF/Hexagon/HexagonTargetHandler.h b/lld/lib/ReaderWriter/ELF/Hexagon/HexagonTargetHandler.h
index 7c6a9c55b7c..f4315f710ec 100644
--- a/lld/lib/ReaderWriter/ELF/Hexagon/HexagonTargetHandler.h
+++ b/lld/lib/ReaderWriter/ELF/Hexagon/HexagonTargetHandler.h
@@ -29,7 +29,7 @@ public:
     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);
diff --git a/lld/lib/ReaderWriter/ELF/Mips/MipsTargetHandler.h b/lld/lib/ReaderWriter/ELF/Mips/MipsTargetHandler.h
index 8f3ea0f3a08..023c7a8ec8c 100644
--- a/lld/lib/ReaderWriter/ELF/Mips/MipsTargetHandler.h
+++ b/lld/lib/ReaderWriter/ELF/Mips/MipsTargetHandler.h
@@ -26,7 +26,7 @@ namespace elf {
 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)) {}
diff --git a/lld/lib/ReaderWriter/ELF/SectionChunks.h b/lld/lib/ReaderWriter/ELF/SectionChunks.h
index f21698ce5db..5363669da49 100644
--- a/lld/lib/ReaderWriter/ELF/SectionChunks.h
+++ b/lld/lib/ReaderWriter/ELF/SectionChunks.h
@@ -123,6 +123,14 @@ public:
     _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;
@@ -144,6 +152,8 @@ protected:
   StringRef _inputSectionName;
   /// \brief Output section name.
   StringRef _outputSectionName;
+  StringRef _archivePath;
+  StringRef _memberPath;
 };
 
 /// \brief A section containing atoms.
diff --git a/lld/lib/ReaderWriter/ELF/SegmentChunks.h b/lld/lib/ReaderWriter/ELF/SegmentChunks.h
index 75c8b6b33e0..f2a975aaeed 100644
--- a/lld/lib/ReaderWriter/ELF/SegmentChunks.h
+++ b/lld/lib/ReaderWriter/ELF/SegmentChunks.h
@@ -269,6 +269,37 @@ protected:
   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> {
@@ -390,11 +421,16 @@ void Segment<ELFT>::assignFileOffsets(uint64_t startOffset) {
   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
@@ -429,6 +465,7 @@ void Segment<ELFT>::assignFileOffsets(uint64_t startOffset) {
       }
       section->setFileOffset(fileOffset);
       fileOffset += section->fileSize();
+      lastVirtualAddress = section->virtualAddr() + section->memSize();
     }
     slice->setFileSize(fileOffset - curSliceFileOffset);
   }
@@ -457,7 +494,7 @@ template <class ELFT> void Segment<ELFT>::assignVirtualAddress(uint64_t 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
@@ -481,6 +518,10 @@ template <class ELFT> void Segment<ELFT>::assignVirtualAddress(uint64_t addr) {
       }
       // 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);
@@ -513,9 +554,22 @@ template <class ELFT> void Segment<ELFT>::assignVirtualAddress(uint64_t addr) {
         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;
diff --git a/lld/lib/ReaderWriter/ELF/TargetLayout.h b/lld/lib/ReaderWriter/ELF/TargetLayout.h
index 13297983459..ab7a7890a27 100644
--- a/lld/lib/ReaderWriter/ELF/TargetLayout.h
+++ b/lld/lib/ReaderWriter/ELF/TargetLayout.h
@@ -20,8 +20,7 @@ namespace elf {
 /// 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
diff --git a/lld/lib/ReaderWriter/LinkerScript.cpp b/lld/lib/ReaderWriter/LinkerScript.cpp
index e264c5c0d2a..34a7d4a79c7 100644
--- a/lld/lib/ReaderWriter/LinkerScript.cpp
+++ b/lld/lib/ReaderWriter/LinkerScript.cpp
@@ -835,7 +835,7 @@ void InputSectionsCmd::dump(raw_ostream &os) const {
     os << "KEEP(";
 
   int numParen = dumpSortDirectives(os, _fileSortMode);
-  os << _fileName;
+  os << _memberName;
   for (int i = 0; i < numParen; ++i)
     os << ")";
 
@@ -1699,7 +1699,7 @@ const InputSectionsCmd *Parser::parseInputSectionsCmd() {
   bool keep = false;
   WildcardSortMode fileSortMode = WildcardSortMode::NA;
   WildcardSortMode archiveSortMode = WildcardSortMode::NA;
-  StringRef fileName;
+  StringRef memberName;
   StringRef archiveName;
 
   if (_tok._kind == Token::kw_keep) {
@@ -1715,7 +1715,7 @@ const InputSectionsCmd *Parser::parseInputSectionsCmd() {
     int numParen = parseSortDirectives(fileSortMode);
     if (numParen == -1)
       return nullptr;
-    fileName = _tok._range;
+    memberName = _tok._range;
     consumeToken();
     if (numParen) {
       while (numParen--)
@@ -1745,7 +1745,7 @@ const InputSectionsCmd *Parser::parseInputSectionsCmd() {
 
   if (_tok._kind != Token::l_paren)
     return new (_alloc)
-        InputSectionsCmd(*this, fileName, archiveName, keep, fileSortMode,
+        InputSectionsCmd(*this, memberName, archiveName, keep, fileSortMode,
                          archiveSortMode, inputSections);
   consumeToken();
 
@@ -1789,7 +1789,7 @@ const InputSectionsCmd *Parser::parseInputSectionsCmd() {
     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);
 }
 
@@ -2141,5 +2141,402 @@ Extern *Parser::parseExtern() {
   return new (_alloc) Extern(*this, symbols);
 }
 
-} // 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);
+  }
+
+  // Reverse this order so we evaluate the expressions in the original order
+  // of the linker script
+  std::reverse(ans.begin(), ans.end());
+
+  // 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