1//===-- PostfixExpression.cpp ---------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9//  This file implements support for postfix expressions found in several symbol
10//  file formats, and their conversion to DWARF.
11//
12//===----------------------------------------------------------------------===//
13
14#include "lldb/Symbol/PostfixExpression.h"
15#include "lldb/Core/dwarf.h"
16#include "lldb/Utility/Stream.h"
17#include "llvm/ADT/StringExtras.h"
18#include <optional>
19
20using namespace lldb_private;
21using namespace lldb_private::postfix;
22using namespace lldb_private::dwarf;
23
24static std::optional<BinaryOpNode::OpType>
25GetBinaryOpType(llvm::StringRef token) {
26  if (token.size() != 1)
27    return std::nullopt;
28  switch (token[0]) {
29  case '@':
30    return BinaryOpNode::Align;
31  case '-':
32    return BinaryOpNode::Minus;
33  case '+':
34    return BinaryOpNode::Plus;
35  }
36  return std::nullopt;
37}
38
39static std::optional<UnaryOpNode::OpType>
40GetUnaryOpType(llvm::StringRef token) {
41  if (token == "^")
42    return UnaryOpNode::Deref;
43  return std::nullopt;
44}
45
46Node *postfix::ParseOneExpression(llvm::StringRef expr,
47                                  llvm::BumpPtrAllocator &alloc) {
48  llvm::SmallVector<Node *, 4> stack;
49
50  llvm::StringRef token;
51  while (std::tie(token, expr) = getToken(expr), !token.empty()) {
52    if (auto op_type = GetBinaryOpType(token)) {
53      // token is binary operator
54      if (stack.size() < 2)
55        return nullptr;
56
57      Node *right = stack.pop_back_val();
58      Node *left = stack.pop_back_val();
59      stack.push_back(MakeNode<BinaryOpNode>(alloc, *op_type, *left, *right));
60      continue;
61    }
62
63    if (auto op_type = GetUnaryOpType(token)) {
64      // token is unary operator
65      if (stack.empty())
66        return nullptr;
67
68      Node *operand = stack.pop_back_val();
69      stack.push_back(MakeNode<UnaryOpNode>(alloc, *op_type, *operand));
70      continue;
71    }
72
73    int64_t value;
74    if (to_integer(token, value, 10)) {
75      // token is integer literal
76      stack.push_back(MakeNode<IntegerNode>(alloc, value));
77      continue;
78    }
79
80    stack.push_back(MakeNode<SymbolNode>(alloc, token));
81  }
82
83  if (stack.size() != 1)
84    return nullptr;
85
86  return stack.back();
87}
88
89std::vector<std::pair<llvm::StringRef, Node *>>
90postfix::ParseFPOProgram(llvm::StringRef prog, llvm::BumpPtrAllocator &alloc) {
91  llvm::SmallVector<llvm::StringRef, 4> exprs;
92  prog.split(exprs, '=');
93  if (exprs.empty() || !exprs.back().trim().empty())
94    return {};
95  exprs.pop_back();
96
97  std::vector<std::pair<llvm::StringRef, Node *>> result;
98  for (llvm::StringRef expr : exprs) {
99    llvm::StringRef lhs;
100    std::tie(lhs, expr) = getToken(expr);
101    Node *rhs = ParseOneExpression(expr, alloc);
102    if (!rhs)
103      return {};
104    result.emplace_back(lhs, rhs);
105  }
106  return result;
107}
108
109namespace {
110class SymbolResolver : public Visitor<bool> {
111public:
112  SymbolResolver(llvm::function_ref<Node *(SymbolNode &symbol)> replacer)
113      : m_replacer(replacer) {}
114
115  using Visitor<bool>::Dispatch;
116
117private:
118  bool Visit(BinaryOpNode &binary, Node *&) override {
119    return Dispatch(binary.Left()) && Dispatch(binary.Right());
120  }
121
122  bool Visit(InitialValueNode &, Node *&) override { return true; }
123  bool Visit(IntegerNode &, Node *&) override { return true; }
124  bool Visit(RegisterNode &, Node *&) override { return true; }
125
126  bool Visit(SymbolNode &symbol, Node *&ref) override {
127    if (Node *replacement = m_replacer(symbol)) {
128      ref = replacement;
129      if (replacement != &symbol)
130        return Dispatch(ref);
131      return true;
132    }
133    return false;
134  }
135
136  bool Visit(UnaryOpNode &unary, Node *&) override {
137    return Dispatch(unary.Operand());
138  }
139
140  llvm::function_ref<Node *(SymbolNode &symbol)> m_replacer;
141};
142
143class DWARFCodegen : public Visitor<> {
144public:
145  DWARFCodegen(Stream &stream) : m_out_stream(stream) {}
146
147  using Visitor<>::Dispatch;
148
149private:
150  void Visit(BinaryOpNode &binary, Node *&) override;
151
152  void Visit(InitialValueNode &val, Node *&) override;
153
154  void Visit(IntegerNode &integer, Node *&) override {
155    m_out_stream.PutHex8(DW_OP_consts);
156    m_out_stream.PutSLEB128(integer.GetValue());
157    ++m_stack_depth;
158  }
159
160  void Visit(RegisterNode &reg, Node *&) override;
161
162  void Visit(SymbolNode &symbol, Node *&) override {
163    llvm_unreachable("Symbols should have been resolved by now!");
164  }
165
166  void Visit(UnaryOpNode &unary, Node *&) override;
167
168  Stream &m_out_stream;
169
170  /// The number keeping track of the evaluation stack depth at any given
171  /// moment. Used for implementing InitialValueNodes. We start with
172  /// m_stack_depth = 1, assuming that the initial value is already on the
173  /// stack. This initial value will be the value of all InitialValueNodes. If
174  /// the expression does not contain InitialValueNodes, then m_stack_depth is
175  /// not used, and the generated expression will run correctly even without an
176  /// initial value.
177  size_t m_stack_depth = 1;
178};
179} // namespace
180
181void DWARFCodegen::Visit(BinaryOpNode &binary, Node *&) {
182  Dispatch(binary.Left());
183  Dispatch(binary.Right());
184
185  switch (binary.GetOpType()) {
186  case BinaryOpNode::Plus:
187    m_out_stream.PutHex8(DW_OP_plus);
188    // NOTE: can be optimized by using DW_OP_plus_uconst opcpode
189    //       if right child node is constant value
190    break;
191  case BinaryOpNode::Minus:
192    m_out_stream.PutHex8(DW_OP_minus);
193    break;
194  case BinaryOpNode::Align:
195    // emit align operator a @ b as
196    // a & ~(b - 1)
197    // NOTE: implicitly assuming that b is power of 2
198    m_out_stream.PutHex8(DW_OP_lit1);
199    m_out_stream.PutHex8(DW_OP_minus);
200    m_out_stream.PutHex8(DW_OP_not);
201
202    m_out_stream.PutHex8(DW_OP_and);
203    break;
204  }
205  --m_stack_depth; // Two pops, one push.
206}
207
208void DWARFCodegen::Visit(InitialValueNode &, Node *&) {
209  // We never go below the initial stack, so we can pick the initial value from
210  // the bottom of the stack at any moment.
211  assert(m_stack_depth >= 1);
212  m_out_stream.PutHex8(DW_OP_pick);
213  m_out_stream.PutHex8(m_stack_depth - 1);
214  ++m_stack_depth;
215}
216
217void DWARFCodegen::Visit(RegisterNode &reg, Node *&) {
218  uint32_t reg_num = reg.GetRegNum();
219  assert(reg_num != LLDB_INVALID_REGNUM);
220
221  if (reg_num > 31) {
222    m_out_stream.PutHex8(DW_OP_bregx);
223    m_out_stream.PutULEB128(reg_num);
224  } else
225    m_out_stream.PutHex8(DW_OP_breg0 + reg_num);
226
227  m_out_stream.PutSLEB128(0);
228  ++m_stack_depth;
229}
230
231void DWARFCodegen::Visit(UnaryOpNode &unary, Node *&) {
232  Dispatch(unary.Operand());
233
234  switch (unary.GetOpType()) {
235  case UnaryOpNode::Deref:
236    m_out_stream.PutHex8(DW_OP_deref);
237    break;
238  }
239  // Stack depth unchanged.
240}
241
242bool postfix::ResolveSymbols(
243    Node *&node, llvm::function_ref<Node *(SymbolNode &)> replacer) {
244  return SymbolResolver(replacer).Dispatch(node);
245}
246
247void postfix::ToDWARF(Node &node, Stream &stream) {
248  Node *ptr = &node;
249  DWARFCodegen(stream).Dispatch(ptr);
250}
251