1 files changed, 227 insertions, 0 deletions
diff --git a/source/Symbol/PostfixExpression.cpp b/source/Symbol/PostfixExpression.cpp
new file mode 100644
index 000000000000..148653561a4e
--- /dev/null
+++ b/source/Symbol/PostfixExpression.cpp
@@ -0,0 +1,227 @@
+//===-- PostfixExpression.cpp -----------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file implements support for postfix expressions found in several symbol
+//  file formats, and their conversion to DWARF.
+//
+//===----------------------------------------------------------------------===//
+
+#include "lldb/Symbol/PostfixExpression.h"
+#include "lldb/Core/dwarf.h"
+#include "lldb/Utility/Stream.h"
+#include "llvm/ADT/StringExtras.h"
+
+using namespace lldb_private;
+using namespace lldb_private::postfix;
+
+static llvm::Optional<BinaryOpNode::OpType>
+GetBinaryOpType(llvm::StringRef token) {
+  if (token.size() != 1)
+    return llvm::None;
+  switch (token[0]) {
+  case '@':
+    return BinaryOpNode::Align;
+  case '-':
+    return BinaryOpNode::Minus;
+  case '+':
+    return BinaryOpNode::Plus;
+  }
+  return llvm::None;
+}
+
+static llvm::Optional<UnaryOpNode::OpType>
+GetUnaryOpType(llvm::StringRef token) {
+  if (token == "^")
+    return UnaryOpNode::Deref;
+  return llvm::None;
+}
+
+Node *postfix::Parse(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc) {
+  llvm::SmallVector<Node *, 4> stack;
+
+  llvm::StringRef token;
+  while (std::tie(token, expr) = getToken(expr), !token.empty()) {
+    if (auto op_type = GetBinaryOpType(token)) {
+      // token is binary operator
+      if (stack.size() < 2)
+        return nullptr;
+
+      Node *right = stack.pop_back_val();
+      Node *left = stack.pop_back_val();
+      stack.push_back(MakeNode<BinaryOpNode>(alloc, *op_type, *left, *right));
+      continue;
+    }
+
+    if (auto op_type = GetUnaryOpType(token)) {
+      // token is unary operator
+      if (stack.empty())
+        return nullptr;
+
+      Node *operand = stack.pop_back_val();
+      stack.push_back(MakeNode<UnaryOpNode>(alloc, *op_type, *operand));
+      continue;
+    }
+
+    int64_t value;
+    if (to_integer(token, value, 10)) {
+      // token is integer literal
+      stack.push_back(MakeNode<IntegerNode>(alloc, value));
+      continue;
+    }
+
+    stack.push_back(MakeNode<SymbolNode>(alloc, token));
+  }
+
+  if (stack.size() != 1)
+    return nullptr;
+
+  return stack.back();
+}
+
+namespace {
+class SymbolResolver : public Visitor<bool> {
+public:
+  SymbolResolver(llvm::function_ref<Node *(SymbolNode &symbol)> replacer)
+      : m_replacer(replacer) {}
+
+  using Visitor<bool>::Dispatch;
+
+private:
+  bool Visit(BinaryOpNode &binary, Node *&) override {
+    return Dispatch(binary.Left()) && Dispatch(binary.Right());
+  }
+
+  bool Visit(InitialValueNode &, Node *&) override { return true; }
+  bool Visit(IntegerNode &, Node *&) override { return true; }
+  bool Visit(RegisterNode &, Node *&) override { return true; }
+
+  bool Visit(SymbolNode &symbol, Node *&ref) override {
+    if (Node *replacement = m_replacer(symbol)) {
+      ref = replacement;
+      if (replacement != &symbol)
+        return Dispatch(ref);
+      return true;
+    }
+    return false;
+  }
+
+  bool Visit(UnaryOpNode &unary, Node *&) override {
+    return Dispatch(unary.Operand());
+  }
+
+  llvm::function_ref<Node *(SymbolNode &symbol)> m_replacer;
+};
+
+class DWARFCodegen : public Visitor<> {
+public:
+  DWARFCodegen(Stream &stream) : m_out_stream(stream) {}
+
+  using Visitor<>::Dispatch;
+
+private:
+  void Visit(BinaryOpNode &binary, Node *&) override;
+
+  void Visit(InitialValueNode &val, Node *&) override;
+
+  void Visit(IntegerNode &integer, Node *&) override {
+    m_out_stream.PutHex8(DW_OP_consts);
+    m_out_stream.PutSLEB128(integer.GetValue());
+    ++m_stack_depth;
+  }
+
+  void Visit(RegisterNode &reg, Node *&) override;
+
+  void Visit(SymbolNode &symbol, Node *&) override {
+    llvm_unreachable("Symbols should have been resolved by now!");
+  }
+
+  void Visit(UnaryOpNode &unary, Node *&) override;
+
+  Stream &m_out_stream;
+
+  /// The number keeping track of the evaluation stack depth at any given
+  /// moment. Used for implementing InitialValueNodes. We start with
+  /// m_stack_depth = 1, assuming that the initial value is already on the
+  /// stack. This initial value will be the value of all InitialValueNodes. If
+  /// the expression does not contain InitialValueNodes, then m_stack_depth is
+  /// not used, and the generated expression will run correctly even without an
+  /// initial value.
+  size_t m_stack_depth = 1;
+};
+} // namespace
+
+void DWARFCodegen::Visit(BinaryOpNode &binary, Node *&) {
+  Dispatch(binary.Left());
+  Dispatch(binary.Right());
+
+  switch (binary.GetOpType()) {
+  case BinaryOpNode::Plus:
+    m_out_stream.PutHex8(DW_OP_plus);
+    // NOTE: can be optimized by using DW_OP_plus_uconst opcpode
+    //       if right child node is constant value
+    break;
+  case BinaryOpNode::Minus:
+    m_out_stream.PutHex8(DW_OP_minus);
+    break;
+  case BinaryOpNode::Align:
+    // emit align operator a @ b as
+    // a & ~(b - 1)
+    // NOTE: implicitly assuming that b is power of 2
+    m_out_stream.PutHex8(DW_OP_lit1);
+    m_out_stream.PutHex8(DW_OP_minus);
+    m_out_stream.PutHex8(DW_OP_not);
+
+    m_out_stream.PutHex8(DW_OP_and);
+    break;
+  }
+  --m_stack_depth; // Two pops, one push.
+}
+
+void DWARFCodegen::Visit(InitialValueNode &, Node *&) {
+  // We never go below the initial stack, so we can pick the initial value from
+  // the bottom of the stack at any moment.
+  assert(m_stack_depth >= 1);
+  m_out_stream.PutHex8(DW_OP_pick);
+  m_out_stream.PutHex8(m_stack_depth - 1);
+  ++m_stack_depth;
+}
+
+void DWARFCodegen::Visit(RegisterNode &reg, Node *&) {
+  uint32_t reg_num = reg.GetRegNum();
+  assert(reg_num != LLDB_INVALID_REGNUM);
+
+  if (reg_num > 31) {
+    m_out_stream.PutHex8(DW_OP_bregx);
+    m_out_stream.PutULEB128(reg_num);
+  } else
+    m_out_stream.PutHex8(DW_OP_breg0 + reg_num);
+
+  m_out_stream.PutSLEB128(0);
+  ++m_stack_depth;
+}
+
+void DWARFCodegen::Visit(UnaryOpNode &unary, Node *&) {
+  Dispatch(unary.Operand());
+
+  switch (unary.GetOpType()) {
+  case UnaryOpNode::Deref:
+    m_out_stream.PutHex8(DW_OP_deref);
+    break;
+  }
+  // Stack depth unchanged.
+}
+
+bool postfix::ResolveSymbols(
+    Node *&node, llvm::function_ref<Node *(SymbolNode &)> replacer) {
+  return SymbolResolver(replacer).Dispatch(node);
+}
+
+void postfix::ToDWARF(Node &node, Stream &stream) {
+  Node *ptr = &node;
+  DWARFCodegen(stream).Dispatch(ptr);
+}