LinkerScript: Add parsing of the MEMORY command

[meadori]

Summary

This patch implements parsing of the GNU ld MEMORY command [1].
The command and the memory block definitions are parsed as
specified (including the slightly strange "o" and "l" keywords).
Evaluation will be added at a later point in time.

[1] https://sourceware.org/binutils/docs-2.25/ld/MEMORY.html

[shankarke]

LGTM.

[davide]

This looks good to me. Do you have commit access, or you want me to commit it on your behalf?

[meadori]

I have commit access and will apply the patch shortly. Thanks for the quick review y'all.

include/lld/ReaderWriter/LinkerScript.h

enum Kind {
     kw_at,
     kw_discard,
     kw_entry,
     kw_exclude_file,
     kw_group,
     kw_hidden,
     kw_input,
     kw_keep,
+    kw_length,
+    kw_memory,
+    kw_origin,
     kw_provide,
     kw_provide_hidden,
     kw_only_if_ro,
     kw_only_if_rw,
     kw_output,
     kw_output_arch,
     kw_output_format,
     kw_overlay,

 ///
 class Command {
 public:
   enum class Kind {
     Entry,
     Group,
     Input,
     InputSectionsCmd,
+    Memory,
     Output,
     OutputArch,
     OutputFormat,
     OutputSectionDescription,
     Overlay,
     SearchDir,
     Sections,
     SymbolAssignment,
public:
   void dump(raw_ostream &os) const override;
   const_iterator begin() const { return _sectionsCommands.begin(); }
   const_iterator end() const { return _sectionsCommands.end(); }
 
 private:
   llvm::ArrayRef<const Command *> _sectionsCommands;
 };
 
+/// Represents a single memory block definition in a MEMORY {} command.
+class MemoryBlock {
+public:
+  MemoryBlock(StringRef name, StringRef attr,
+              const Expression *origin, const Expression *length)
+      : _name(name), _attr(attr), _origin(origin), _length(length) {}
+
+  void dump(raw_ostream &os) const;
+
+private:
+  StringRef _name;
+  StringRef _attr;
+  const Expression *_origin;
+  const Expression *_length;
+};
+
+/// Represents all the contents of the MEMORY {} command.
+class Memory : public Command {
+public:
+  Memory(Parser &ctx,
+         const SmallVectorImpl<const MemoryBlock *> &blocks)
+      : Command(ctx, Kind::Memory) {
+    size_t numBlocks = blocks.size();
+    const MemoryBlock **blocksStart =
+        getAllocator().Allocate<const MemoryBlock *>(numBlocks);
+    std::copy(std::begin(blocks), std::end(blocks), blocksStart);
+    _blocks = llvm::makeArrayRef(blocksStart, numBlocks);
+  }
+
+  static bool classof(const Command *c) {
+    return c->getKind() == Kind::Memory;
+  }
+
+  void dump(raw_ostream &os) const override;
+
+private:
+  llvm::ArrayRef<const MemoryBlock *> _blocks;
+};
+
+
 /// Stores the parse tree of a linker script.
 class LinkerScript {
 public:
   void dump(raw_ostream &os) const {
     for (const Command *c : _commands) {
       c->dump(os);
       if (isa<SymbolAssignment>(c))
         os << "\n";
private:
   ///   SECTIONS {
   ///   ^~~~ parseSections()
   ///     . = 0x100000;
   ///     .data : { *(.data) }
   ///   }
   ///
   Sections *parseSections();
 
+  /// Parse the MEMORY linker script command.
+  /// Example:
+  ///
+  ///   MEMORY {
+  ///   ^~~~ parseMemory()
+  ///     ram (rwx) : ORIGIN = 0x20000000, LENGTH = 96K
+  ///     rom (rx)  : ORIGIN = 0x0,        LENGTH = 256K
+  ///   }
+  ///
+  Memory *parseMemory();
+
 private:
   // Owns the entire linker script AST nodes
   llvm::BumpPtrAllocator _alloc;
 
   // The top-level/entry-point linker script AST node
   LinkerScript _script;
 
   Lexer _lex;

lib/ReaderWriter/LinkerScript.cpp

case Token::name:                                                            \
     CASE(kw_at)
     CASE(kw_discard)
     CASE(kw_entry)
     CASE(kw_exclude_file)
     CASE(kw_group)
     CASE(kw_hidden)
     CASE(kw_input)
     CASE(kw_keep)
+    CASE(kw_length)
+    CASE(kw_memory)
+    CASE(kw_origin)
     CASE(kw_provide)
     CASE(kw_provide_hidden)
     CASE(kw_only_if_ro)
     CASE(kw_only_if_rw)
     CASE(kw_output)
     CASE(kw_output_arch)
     CASE(kw_output_format)
     CASE(kw_overlay)
Token::Kind kind =
             .Case("AS_NEEDED", Token::kw_as_needed)
             .Case("AT", Token::kw_at)
             .Case("ENTRY", Token::kw_entry)
             .Case("EXCLUDE_FILE", Token::kw_exclude_file)
             .Case("GROUP", Token::kw_group)
             .Case("HIDDEN", Token::kw_hidden)
             .Case("INPUT", Token::kw_input)
             .Case("KEEP", Token::kw_keep)
+            .Case("LENGTH", Token::kw_length)
+            .Case("l", Token::kw_length)
+            .Case("len", Token::kw_length)
+            .Case("MEMORY", Token::kw_memory)
             .Case("ONLY_IF_RO", Token::kw_only_if_ro)
             .Case("ONLY_IF_RW", Token::kw_only_if_rw)
+            .Case("ORIGIN", Token::kw_origin)
+            .Case("o", Token::kw_origin)
+            .Case("org", Token::kw_origin)
             .Case("OUTPUT", Token::kw_output)
             .Case("OUTPUT_ARCH", Token::kw_output_arch)
             .Case("OUTPUT_FORMAT", Token::kw_output_format)
             .Case("OVERLAY", Token::kw_overlay)
             .Case("PROVIDE", Token::kw_provide)
             .Case("PROVIDE_HIDDEN", Token::kw_provide_hidden)
             .Case("SEARCH_DIR", Token::kw_search_dir)
             .Case("SECTIONS", Token::kw_sections)
void Sections::dump(raw_ostream &os) const {
   os << "SECTIONS\n{\n";
   for (auto &command : _sectionsCommands) {
     command->dump(os);
     os << "\n";
   }
   os << "}\n";
 }
 
+// Memory functions
+void MemoryBlock::dump(raw_ostream &os) const {
+    os << _name;
+
+    if (!_attr.empty())
+      os << " (" << _attr << ")";
+
+    os << " : ";
+
+    os << "ORIGIN = ";
+    _origin->dump(os);
+    os << ", ";
+
+    os << "LENGTH = ";
+    _length->dump(os);
+}
+
+void Memory::dump(raw_ostream &os) const {
+  os << "MEMORY\n{\n";
+  for (auto &block : _blocks) {
+    block->dump(os);
+    os << "\n";
+  }
+  os << "}\n";
+}
+
 // Parser functions
 std::error_code Parser::parse() {
   // Get the first token.
   _lex.lex(_tok);
   // Parse top level commands.
   while (true) {
     switch (_tok._kind) {
     case Token::eof:
while (true) {
     case Token::kw_provide:
     case Token::kw_provide_hidden: {
       const Command *cmd = parseSymbolAssignment();
       if (!cmd)
         return LinkerScriptReaderError::parse_error;
       _script._commands.push_back(cmd);
       break;
     }
+    case Token::kw_memory: {
+      const Command *cmd = parseMemory();
+      if (!cmd)
+        return LinkerScriptReaderError::parse_error;
+      _script._commands.push_back(cmd);
+      break;
+    }
     default:
       // Unexpected.
       error(_tok, "expected linker script command");
       return LinkerScriptReaderError::parse_error;
     }
   }
   return LinkerScriptReaderError::parse_error;
 }
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);
 }
 
+Memory *Parser::parseMemory() {
+  assert(_tok._kind == Token::kw_memory && "Expected MEMORY!");
+  consumeToken();
+  if (!expectAndConsume(Token::l_brace, "expected {"))
+    return nullptr;
+  SmallVector<const MemoryBlock *, 8> blocks;
+
+  bool unrecognizedToken = false;
+  // Parse zero or more memory block descriptors.
+  while (!unrecognizedToken) {
+    if (_tok._kind == Token::identifier) {
+      StringRef name;
+      StringRef attrs;
+      const Expression *origin = nullptr;
+      const Expression *length = nullptr;
+
+      name = _tok._range;
+      consumeToken();
+
+      // Parse optional memory region attributes.
+      if (_tok._kind == Token::l_paren) {
+        consumeToken();
+
+        if (_tok._kind != Token::identifier) {
+          error(_tok, "Expected memory attribute string.");
+          return nullptr;
+        }
+        attrs = _tok._range;
+        consumeToken();
+
+        if (!expectAndConsume(Token::r_paren, "expected )"))
+          return nullptr;
+      }
+
+      if (!expectAndConsume(Token::colon, "expected :"))
+        return nullptr;
+
+      // Parse the ORIGIN (base address of memory block).
+      if (!expectAndConsume(Token::kw_origin, "expected ORIGIN"))
+        return nullptr;
+
+      if (!expectAndConsume(Token::equal, "expected ="))
+        return nullptr;
+
+      origin = parseExpression();
+      if (!origin)
+        return nullptr;
+
+      if (!expectAndConsume(Token::comma, "expected ,"))
+        return nullptr;
+
+      // Parse the LENGTH (length of memory block).
+      if (!expectAndConsume(Token::kw_length, "expected LENGTH"))
+        return nullptr;
+
+      if (!expectAndConsume(Token::equal, "expected ="))
+        return nullptr;
+
+      length = parseExpression();
+      if (!length)
+        return nullptr;
+
+      MemoryBlock *block =
+          new (_alloc) MemoryBlock(name, attrs, origin, length);
+      blocks.push_back(block);
+    } else {
+      unrecognizedToken = true;
+    }
+  }
+  if (!expectAndConsume(
+          Token::r_brace,
+          "expected memory block definition."))
+    return nullptr;
+
+  return new (_alloc) Memory(*this, blocks);
+}
+
 } // end namespace script
 } // end namespace lld

test/LinkerScript/memory-empty.test

+/*
+  RUN: linker-script-test %s | FileCheck %s
+*/
+
+MEMORY
+{
+}
+
+/*
+CHECK: kw_memory: MEMORY
+CHECK: l_brace: {
+CHECK: r_brace: }
+CHECK: eof:
+CHECK: MEMORY
+CHECK: {
+CHECK: }
+*/

test/LinkerScript/memory-missing-attrs.test

+/*
+  RUN: linker-script-test %s 2> %t | FileCheck %s
+  RUN: FileCheck -input-file %t -check-prefix=CHECK-ERR %s
+*/
+
+MEMORY
+{
+  ram () : ORIGIN = 0x20000000, LENGTH = 128M
+/*
+CHECK-ERR: [[@LINE-2]]:8: error: Expected memory attribute string.
+CHECK-ERR-NEXT: {{^  ram \(\) : ORIGIN = 0x20000000, LENGTH = 128M}}
+CHECK-ERR-NEXT: {{^        \^}}
+*/
+}
+
+/*
+CHECK: kw_memory: MEMORY
+CHECK: l_brace: {
+CHECK: identifier: ram
+CHECK: l_paren: (
+CHECK: r_paren: )
+CHECK: colon: :
+CHECK: kw_origin: ORIGIN
+CHECK: equal: =
+CHECK: number: 0x20000000
+CHECK: comma: ,
+CHECK: kw_length: LENGTH
+CHECK: equal: =
+CHECK: number: 128M
+CHECK: r_brace: }
+CHECK: eof:
+*/

test/LinkerScript/memory-missing-length.test

+/*
+  RUN: linker-script-test %s 2> %t | FileCheck %s
+  RUN: FileCheck -input-file %t -check-prefix=CHECK-ERR %s
+*/
+
+MEMORY
+{
+  ram (rwx) : ORIGIN = 0x20000000,
+}
+/*
+CHECK-ERR: [[@LINE-2]]:1: error: expected LENGTH
+CHECK-ERR-NEXT: {{^}}}
+CHECK-ERR-NEXT: {{^\^}}
+*/
+
+/*
+CHECK: kw_memory: MEMORY
+CHECK: l_brace: {
+CHECK: identifier: ram
+CHECK: l_paren: (
+CHECK: identifier: rwx
+CHECK: r_paren: )
+CHECK: colon: :
+CHECK: kw_origin: ORIGIN
+CHECK: equal: =
+CHECK: number: 0x20000000
+CHECK: r_brace: }
+CHECK: eof:
+*/

test/LinkerScript/memory-missing-name.test

+/*
+  RUN: linker-script-test %s 2> %t | FileCheck %s
+  RUN: FileCheck -input-file %t -check-prefix=CHECK-ERR %s
+*/
+
+MEMORY
+{
+  (rwx) : ORIGIN = 0x20000000, LENGTH = 128M
+/*
+CHECK-ERR: [[@LINE-2]]:3: error: expected memory block definition.
+CHECK-ERR-NEXT: {{^  \(rwx\) : ORIGIN = 0x20000000, LENGTH = 128M}}
+CHECK-ERR-NEXT: {{^  \^}}
+*/
+}
+
+/*
+CHECK: kw_memory: MEMORY
+CHECK: l_brace: {
+CHECK: l_paren: (
+CHECK: r_paren: )
+CHECK: colon: :
+CHECK: kw_origin: ORIGIN
+CHECK: equal: =
+CHECK: number: 0x20000000
+CHECK: comma: ,
+CHECK: kw_length: LENGTH
+CHECK: equal: =
+CHECK: number: 128M
+CHECK: r_brace: }
+CHECK: eof:
+*/

test/LinkerScript/memory-missing-origin.test

+/*
+  RUN: linker-script-test %s 2> %t | FileCheck %s
+  RUN: FileCheck -input-file %t -check-prefix=CHECK-ERR %s
+*/
+
+MEMORY
+{
+  ram (rwx) : LENGTH = 128M
+/*
+CHECK-ERR: [[@LINE-2]]:15: error: expected ORIGIN
+CHECK-ERR-NEXT: {{^  ram \(rwx\) : LENGTH = 128M}}
+CHECK-ERR-NEXT: {{^               \^}}
+*/
+
+}
+
+/*
+CHECK: kw_memory: MEMORY
+CHECK: l_brace: {
+CHECK: identifier: ram
+CHECK: l_paren: (
+CHECK: identifier: rwx
+CHECK: r_paren: )
+CHECK: colon: :
+CHECK: kw_length: LENGTH
+CHECK: equal: =
+CHECK: number: 128M
+CHECK: r_brace: }
+CHECK: eof:
+*/

test/LinkerScript/memory-valid.test

+/*
+  RUN: linker-script-test %s | FileCheck %s
+*/
+
+MEMORY
+{
+  ram (rwx) : ORIGIN = 0x20000000, LENGTH = 96K
+  rom (rx) : org = 0x0, len = 256K
+  boot : o = 0x1000000, l = 0x5f00
+}
+
+/*
+CHECK: kw_memory: MEMORY
+CHECK: l_brace: {
+CHECK: identifier: ram
+CHECK: l_paren: (
+CHECK: identifier: rwx
+CHECK: r_paren: )
+CHECK: colon: :
+CHECK: kw_origin: ORIGIN
+CHECK: equal: =
+CHECK: number: 0x20000000
+CHECK: comma: ,
+CHECK: kw_length: LENGTH
+CHECK: equal: =
+CHECK: number: 96K
+CHECK: identifier: rom
+CHECK: l_paren: (
+CHECK: identifier: rx
+CHECK: r_paren: )
+CHECK: colon: :
+CHECK: kw_origin: org
+CHECK: equal: =
+CHECK: number: 0x0
+CHECK: comma: ,
+CHECK: kw_length: len
+CHECK: equal: =
+CHECK: number: 256K
+CHECK: identifier: boot
+CHECK: colon: :
+CHECK: kw_origin: o
+CHECK: equal: =
+CHECK: number: 0x1000000
+CHECK: comma: ,
+CHECK: kw_length: l
+CHECK: equal: =
+CHECK: number: 0x5f00
+CHECK: r_brace: }
+CHECK: eof:
+CHECK: MEMORY
+CHECK: {
+CHECK: ram (rwx) : ORIGIN = 536870912, LENGTH = 98304
+CHECK: rom (rx) : ORIGIN = 0, LENGTH = 262144
+CHECK: boot : ORIGIN = 16777216, LENGTH = 24320
+CHECK: }
+*/