[lld] [LinkerScript] Implement linker script expression evaluation

[rafaelauler]

Summary

As suggested by Rui, I broke up the original patch in D7915 in two, separating
the part that implements the linker script expression evaluation.

The expression evaluation is needed when interpreting linker scripts, in order
to calculate the value for new symbols or to determine a new position to load
sections in memory. This patch extends Expression nodes from the linker script
AST with evaluation functions. It also contains a unit test.

[ruiu]

lib/ReaderWriter/LinkerScript.cpp

545

Maybe you want to use find and compare the return value with end, so that you don't look up the table twice.

583

nit: return -childRes;

589

Remove this line. I believe llvm_unreachable has attribute((noreturn)), so no warning would be issued.

674

Ditto

704

Is it okay to compute both "then" and "else" clauses regardless of a condition value? In a normal programming language, we don't do that -- for example, if (true) {} else { 1 / 0; } doesn't fail.

[shankarke]

include/lld/ReaderWriter/ELFLinkingContext.h

304–306

do you want to add a boolean hasLinkerScript that checks the size and returns ?

include/lld/ReaderWriter/LinkerScript.h

366

you could replace this with a llvm::DenseMap<StringRef, int64_t> and use a common StringRefMappingInfo.

794–795

Use lld::range,once you replace it with range, you can remove the typedef for const_iterator.

lib/ReaderWriter/LinkerScript.cpp

582

Do you want to handle Unary::Plus ??

585

I thought linker script uses only a boolean value of a Unary Not, no ??

702

no need of else.

unittests/DriverTests/GnuLdDriverTest.cpp

262

Can we change SymbolAssignment::Normal to SymbolAssignment::Default ?

Looks like you are using the same SymboAssignment to name two different things, assignmentKind and assignmentVisibilty. I would recommend separating them.

[rafaelauler]

Hi all,

Thank you for your fast replies. Comments inline.

include/lld/ReaderWriter/ELFLinkingContext.h

304–306

Well, I added this function just to make this patch self-contained and allow us to properly unit-test the evaluator. It gets deleted in the follow-up patch because script::Sema is introduced to manage Parser copies.

include/lld/ReaderWriter/LinkerScript.h

366

I used this type because that is what Clang uses for its symbol table, but added the comment to make it easier to refactor this later in favour of other data structures, if needed.

But If we're gonna use std::map<std::string, T>, I'd rather stick with llvm::StringMap, since it is available in the LLVM library :)

794–795

Thanks for the tip. Now that I'm thinking about this, there is also little reason to also use the typedef here, since we typically iterate through these elements with "auto", so we don't need to type the full name anyway. I used this mostly to keep code consistent with other classes and to make function signature cleaner. But if we're changing this, I'd rather do it in the follow-up patch, which introduces a whole lot more of iterators for accessing linker script AST nodes.

lib/ReaderWriter/LinkerScript.cpp

545

Thanks, will do.

582

I guess this is currently not supported by the parser. Pardon my ignorance, but what is the semantic for this?

583

Fixed

585

That would be the token "!", but currently Unary::Not comes from parsing "~" tokens. I will update the parser to recognize "!" as a unary operator in a separate patch.

589

Ok

702

Fixed

704

I previously thought that:

if (true) {} else { undefined_symbol + 1 }

should return an error, even though the else branch is not used. But now I see that this is just wrong, since, if we want to generate diagnostics for my example above, we should do this in the semantic analysis, not in the evaluator. I will fix this.

unittests/DriverTests/GnuLdDriverTest.cpp

262

Sure, I changed the names.

About separating the concept of visibility, I'll do it in a separate patch when appropriate, thanks for the heads up.

[rafaelauler]

Addressed reviewers' concerns.

[• shankar.easwaran]

LGTM

[ruiu]

LGTM with this change.

include/lld/ReaderWriter/LinkerScript.h

794–795

Typedef is fine and preferred. I found lld::range is used in some places in LLD to "hide" actual types of return values. It on first sight seemed like a good idea, but it actually introduced a dependency to lld::range instead of to an actual type, adding an additional layer which doesn't do anything specific. Use of lld::range cannot be replaced with llvm::iterator_range in some cases because there is code assuming lld::range is a random access iterator (llvm::iterator_range isn't). I don't disagree that an abstraction like lld::range would be meaningful in some cases, but many existing use cases in LLD doesn't make much sense.

lib/ReaderWriter/LinkerScript.cpp

699

You can just return a return value of evalExpr.

if (conditional) {
  return _trueExpr->evalExpr(symbolTable);
return _falseExpr->evalExpr(symbolTable);

[rafaelauler]

Committed r231707.

include/lld/Core/Error.h

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

include/lld/ReaderWriter/ELFLinkingContext.h

public:
   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; }
 
 private:
   ELFLinkingContext() = delete;
 

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/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 <vector>

 ///               | | ^~~~> Constant : Expression
 ///               | |   ^~~~> BinOp : Expression
 ///               ^~~~> Constant : Expression
 ///                 ^~~~> BinOp : Expression  (the top-level Expression node)
 /// }
 ///
 class Expression {
 public:
+  // The symbol table does not need to own its string keys and the use of StringMap
+  // here is an overkill.
+  typedef llvm::StringMap<int64_t, llvm::BumpPtrAllocator> SymbolTableTy;
+
   enum class Kind { Constant, Symbol, FunctionCall, Unary, BinOp,
                     TernaryConditional };
   Kind getKind() const { return _kind; }
   inline llvm::BumpPtrAllocator &getAllocator() const;
   virtual void dump(raw_ostream &os) const = 0;
+  virtual ErrorOr<int64_t> evalExpr(SymbolTableTy &symbolTable) const = 0;
   virtual ~Expression() {}
 
 protected:
   Expression(class Parser &ctx, Kind k) : _ctx(ctx), _kind(k) {}
 
 private:
   Parser &_ctx;
   Kind _kind;
 };
 
 /// A constant value is stored as unsigned because it represents absolute
 /// values. We represent negative numbers by composing the unary '-' operator
 /// with a constant.
 class Constant : public Expression {
 public:
   Constant(Parser &ctx, uint64_t num)
       : Expression(ctx, Kind::Constant), _num(num) {}
   void dump(raw_ostream &os) const override;
 
   static bool classof(const Expression *c) {
     return c->getKind() == Kind::Constant;
   }
 
+  ErrorOr<int64_t> evalExpr(SymbolTableTy &symbolTable) const override;
+
 private:
   uint64_t _num;
 };
 
 class Symbol : public Expression {
 public:
   Symbol(Parser &ctx, StringRef name)
       : Expression(ctx, Kind::Symbol), _name(name) {}
   void dump(raw_ostream &os) const override;
 
   static bool classof(const Expression *c) {
     return c->getKind() == Kind::Symbol;
   }
 
+  ErrorOr<int64_t> evalExpr(SymbolTableTy &symbolTable) const override;
+
 private:
   StringRef _name;
 };
 
 class FunctionCall : public Expression {
 public:
   FunctionCall(Parser &ctx, StringRef name,
                const SmallVectorImpl<const Expression *> &args)
       : Expression(ctx, Kind::FunctionCall), _name(name) {
     size_t numArgs = args.size();
     const Expression **argsStart =
         getAllocator().Allocate<const Expression *>(numArgs);
     std::copy(std::begin(args), std::end(args), argsStart);
     _args = llvm::makeArrayRef(argsStart, numArgs);
   }
 
   void dump(raw_ostream &os) const override;
 
   static bool classof(const Expression *c) {
     return c->getKind() == Kind::FunctionCall;
   }
 
+  ErrorOr<int64_t> evalExpr(SymbolTableTy &symbolTable) const override;
+
 private:
   StringRef _name;
   llvm::ArrayRef<const Expression *> _args;
 };
 
 class Unary : public Expression {
 public:
   enum Operation {
     Minus,
     Not
   };
 
   Unary(Parser &ctx, Operation op, const Expression *child)
       : Expression(ctx, Kind::Unary), _op(op), _child(child) {}
   void dump(raw_ostream &os) const override;
 
   static bool classof(const Expression *c) {
     return c->getKind() == Kind::Unary;
   }
 
+  ErrorOr<int64_t> evalExpr(SymbolTableTy &symbolTable) const override;
+
 private:
   Operation _op;
   const Expression *_child;
 };
 
 class BinOp : public Expression {
 public:
   enum Operation {
BinOp(Parser &ctx, const Expression *lhs, Operation op, const Expression *rhs)
       : Expression(ctx, Kind::BinOp), _op(op), _lhs(lhs), _rhs(rhs) {}
 
   void dump(raw_ostream &os) const override;
 
   static bool classof(const Expression *c) {
     return c->getKind() == Kind::BinOp;
   }
 
+  ErrorOr<int64_t> evalExpr(SymbolTableTy &symbolTable) const override;
+
 private:
   Operation _op;
   const Expression *_lhs;
   const Expression *_rhs;
 };
 
 /// Operands of the ternary operator can be any expression, similar to the other
 /// operations, including another ternary operator. To disambiguate the parse
TernaryConditional(Parser &ctx, const Expression *conditional,
         _trueExpr(trueExpr), _falseExpr(falseExpr) {}
 
   void dump(raw_ostream &os) const override;
 
   static bool classof(const Expression *c) {
     return c->getKind() == Kind::TernaryConditional;
   }
 
+  ErrorOr<int64_t> evalExpr(SymbolTableTy &symbolTable) const override;
+
 private:
   const Expression *_conditional;
   const Expression *_trueExpr;
   const Expression *_falseExpr;
 };
 
 /// Symbol assignments of the form "symbolname = <expression>" may occur either
 /// as sections-commands or as output-section-commands.
 /// Example:
 ///
 /// SECTIONS {
 ///   mysymbol = .         /* SymbolAssignment as a sections-command */
 ///   .data : {
 ///     othersymbol = .    /* SymbolAssignment as an output-section-command */
 ///   }
 ///}
 ///
 class SymbolAssignment : public Command {
 public:
   enum AssignmentKind { Simple, Sum, Sub, Mul, Div, Shl, Shr, And, Or };
-  enum AssignmentVisibility { Normal, Hidden, Provide, ProvideHidden };
+  enum AssignmentVisibility { Default, Hidden, Provide, ProvideHidden };
 
   SymbolAssignment(Parser &ctx, StringRef name, const Expression *expr,
                    AssignmentKind kind, AssignmentVisibility visibility)
       : Command(ctx, Kind::SymbolAssignment), _expression(expr), _symbol(name),
         _assignmentKind(Simple), _assignmentVisibility(visibility) {}
 
   static bool classof(const Command *c) {
     return c->getKind() == Kind::SymbolAssignment;
   }
 
   void dump(raw_ostream &os) const override;
+  const Expression *expr() const { return _expression; }
+  StringRef symbol() const { return _symbol; }
+  AssignmentKind assignmentKind() const { return _assignmentKind; }
+  AssignmentVisibility assignmentVisibility() const {
+    return _assignmentVisibility;
+  }
 
 private:
   const Expression *_expression;
   StringRef _symbol;
   AssignmentKind _assignmentKind;
   AssignmentVisibility _assignmentVisibility;
 };
 
public:
   }
 
   void dump(raw_ostream &os) const override { os << "Overlay description\n"; }
 };
 
 /// Represents all the contents of the SECTIONS {} construct.
 class Sections : public Command {
 public:
+  typedef llvm::ArrayRef<const Command *>::const_iterator const_iterator;
+
   Sections(Parser &ctx,
            const SmallVectorImpl<const Command *> &sectionsCommands)
       : Command(ctx, Kind::Sections) {
     size_t numCommands = sectionsCommands.size();
     const Command **commandsStart =
         getAllocator().Allocate<const Command *>(numCommands);
     std::copy(std::begin(sectionsCommands), std::end(sectionsCommands),
               commandsStart);
     _sectionsCommands = llvm::makeArrayRef(commandsStart, numCommands);
   }
 
   static bool classof(const Command *c) {
     return c->getKind() == Kind::Sections;
   }
 
   void dump(raw_ostream &os) const override;
+  const_iterator begin() const { return _sectionsCommands.begin(); }
+  const_iterator end() const { return _sectionsCommands.end(); }
 
 private:
   llvm::ArrayRef<const Command *> _sectionsCommands;
 };
 
 /// Stores the parse tree of a linker script.
 class LinkerScript {
 public:

lib/Core/Error.cpp

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

lib/ReaderWriter/LinkerScript.cpp

default:
       return;
     }
   }
 }
 
 // Constant functions
 void Constant::dump(raw_ostream &os) const { os << _num; }
 
+ErrorOr<int64_t> Constant::evalExpr(SymbolTableTy &symbolTable) const {
+  return _num;
+}
+
 // Symbol functions
 void Symbol::dump(raw_ostream &os) const { os << _name; }
 
+ErrorOr<int64_t> Symbol::evalExpr(SymbolTableTy &symbolTable) const {
+  auto it = symbolTable.find(_name);
+  if (it == symbolTable.end())
+    return LinkerScriptReaderError::unknown_symbol_in_expr;
+  return it->second;
+}
+
 // FunctionCall functions
 void FunctionCall::dump(raw_ostream &os) const {
   os << _name << "(";
   for (unsigned i = 0, e = _args.size(); i != e; ++i) {
     if (i)
       os << ", ";
     _args[i]->dump(os);
   }
   os << ")";
 }
 
+ErrorOr<int64_t> FunctionCall::evalExpr(SymbolTableTy &symbolTable) const {
+  return LinkerScriptReaderError::unrecognized_function_in_expr;
+}
+
 // Unary functions
 void Unary::dump(raw_ostream &os) const {
   os << "(";
   if (_op == Unary::Minus)
     os << "-";
   else
     os << "~";
   _child->dump(os);
   os << ")";
 }
 
+ErrorOr<int64_t> Unary::evalExpr(SymbolTableTy &symbolTable) const {
+  auto child = _child->evalExpr(symbolTable);
+  if (child.getError())
+    return child.getError();
+
+  int64_t childRes = *child;
+  switch (_op) {
+  case Unary::Minus:
+    return -childRes;
+  case Unary::Not:
+    return ~childRes;
+  }
+
+  llvm_unreachable("");
+}
+
 // BinOp functions
 void BinOp::dump(raw_ostream &os) const {
   os << "(";
   _lhs->dump(os);
   os << " ";
   switch (_op) {
   case Sum:
     os << "+";
case CompareGreaterEqual:
     os << ">=";
     break;
   }
   os << " ";
   _rhs->dump(os);
   os << ")";
 }
 
+ErrorOr<int64_t> BinOp::evalExpr(SymbolTableTy &symbolTable) const {
+  auto lhs = _lhs->evalExpr(symbolTable);
+  if (lhs.getError())
+    return lhs.getError();
+  auto rhs = _rhs->evalExpr(symbolTable);
+  if (rhs.getError())
+    return rhs.getError();
+
+  int64_t lhsRes = *lhs;
+  int64_t rhsRes = *rhs;
+
+  switch(_op) {
+  case And:                 return lhsRes & rhsRes;
+  case CompareDifferent:    return lhsRes != rhsRes;
+  case CompareEqual:        return lhsRes == rhsRes;
+  case CompareGreater:      return lhsRes > rhsRes;
+  case CompareGreaterEqual: return lhsRes >= rhsRes;
+  case CompareLess:         return lhsRes < rhsRes;
+  case CompareLessEqual:    return lhsRes <= rhsRes;
+  case Div:                 return lhsRes / rhsRes;
+  case Mul:                 return lhsRes * rhsRes;
+  case Or:                  return lhsRes | rhsRes;
+  case Shl:                 return lhsRes << rhsRes;
+  case Shr:                 return lhsRes >> rhsRes;
+  case Sub:                 return lhsRes - rhsRes;
+  case Sum:                 return lhsRes + rhsRes;
+  }
+
+  llvm_unreachable("");
+}
+
 // TernaryConditional functions
 void TernaryConditional::dump(raw_ostream &os) const {
   _conditional->dump(os);
   os << " ? ";
   _trueExpr->dump(os);
   os << " : ";
   _falseExpr->dump(os);
 }
 
+ErrorOr<int64_t>
+TernaryConditional::evalExpr(SymbolTableTy &symbolTable) const {
+  auto conditional = _conditional->evalExpr(symbolTable);
+  if (conditional.getError())
+    return conditional.getError();
+  if (*conditional) {
+    auto trueExpr = _trueExpr->evalExpr(symbolTable);
+    if (trueExpr.getError())
+      return trueExpr.getError();
+    return *trueExpr;
+  }
+  auto falseExpr = _falseExpr->evalExpr(symbolTable);
+  if (falseExpr.getError())
+    return falseExpr.getError();
+  return *falseExpr;
+}
+
 // SymbolAssignment functions
 void SymbolAssignment::dump(raw_ostream &os) const {
   int numParen = 0;
 
-  if (_assignmentVisibility != Normal) {
+  if (_assignmentVisibility != Default) {
     switch (_assignmentVisibility) {
     case Hidden:
       os << "HIDDEN(";
       break;
     case Provide:
       os << "PROVIDE(";
       break;
     case ProvideHidden:
SearchDir *Parser::parseSearchDir() {
   return new (_alloc) SearchDir(*this, searchPath);
 }
 
 const SymbolAssignment *Parser::parseSymbolAssignment() {
   assert((_tok._kind == Token::identifier || _tok._kind == Token::kw_hidden ||
           _tok._kind == Token::kw_provide ||
           _tok._kind == Token::kw_provide_hidden) &&
          "Expected identifier!");
-  SymbolAssignment::AssignmentVisibility visibility = SymbolAssignment::Normal;
+  SymbolAssignment::AssignmentVisibility visibility = SymbolAssignment::Default;
   SymbolAssignment::AssignmentKind kind;
   int numParen = 0;
 
   switch (_tok._kind) {
   case Token::kw_hidden:
     visibility = SymbolAssignment::Hidden;
     ++numParen;
     consumeToken();

unittests/DriverTests/GnuLdDriverTest.cpp

 }
 
 // Test that search paths are ignored when nostdlib is set.
 TEST_F(LinkerScriptTest, IgnoreSearchDirNoStdLib) {
   parse("SEARCH_DIR(\"/foo/bar\")", true /*nostdlib*/);
   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());
+
+  script::LinkerScript *ls = _ctx->scripts()[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);
+  EXPECT_TRUE(sa1 != nullptr);
+  EXPECT_EQ(script::SymbolAssignment::Simple, sa1->assignmentKind());
+  EXPECT_EQ(script::SymbolAssignment::Default, sa1->assignmentVisibility());
+
+  ++command;
+  auto *sa2 = dyn_cast<const script::SymbolAssignment>(*command);
+  EXPECT_TRUE(sa2 != nullptr);
+  EXPECT_EQ(script::SymbolAssignment::Simple, sa2->assignmentKind());
+  EXPECT_EQ(script::SymbolAssignment::Default, sa2->assignmentVisibility());
+
+  script::Expression::SymbolTableTy mySymbolTable;
+  auto ans = sa1->expr()->evalExpr(mySymbolTable);
+  EXPECT_FALSE(ans.getError());
+  int64_t result = *ans;
+  EXPECT_EQ(0x4040, result);
+  mySymbolTable[sa1->symbol()] = result;
+
+  auto ans2 = sa2->expr()->evalExpr(mySymbolTable);
+  EXPECT_FALSE(ans2.getError());
+  result = *ans2;
+  EXPECT_EQ(0x14000, result);
+  EXPECT_EQ(0, sa2->symbol().compare(StringRef(".")));
+}
+