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(args&: token, args&: expr) = getToken(Source: 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(Elt: MakeNode<BinaryOpNode>(alloc, args&: *op_type, args&: *left, args&: *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(Elt: MakeNode<UnaryOpNode>(alloc, args&: *op_type, args&: *operand));
70 continue;
71 }
72
73 int64_t value;
74 if (to_integer(S: token, Num&: value, Base: 10)) {
75 // token is integer literal
76 stack.push_back(Elt: MakeNode<IntegerNode>(alloc, args&: value));
77 continue;
78 }
79
80 stack.push_back(Elt: MakeNode<SymbolNode>(alloc, args&: 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(A&: exprs, Separator: '=');
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(args&: lhs, args&: expr) = getToken(Source: expr);
101 Node *rhs = ParseOneExpression(expr, alloc);
102 if (!rhs)
103 return {};
104 result.emplace_back(args&: lhs, args&: 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(node&: binary.Left()) && Dispatch(node&: 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(node&: ref);
131 return true;
132 }
133 return false;
134 }
135
136 bool Visit(UnaryOpNode &unary, Node *&) override {
137 return Dispatch(node&: 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(uvalue: DW_OP_consts);
156 m_out_stream.PutSLEB128(uval: 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(node&: binary.Left());
183 Dispatch(node&: binary.Right());
184
185 switch (binary.GetOpType()) {
186 case BinaryOpNode::Plus:
187 m_out_stream.PutHex8(uvalue: 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(uvalue: 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(uvalue: DW_OP_lit1);
199 m_out_stream.PutHex8(uvalue: DW_OP_minus);
200 m_out_stream.PutHex8(uvalue: DW_OP_not);
201
202 m_out_stream.PutHex8(uvalue: 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(uvalue: DW_OP_pick);
213 m_out_stream.PutHex8(uvalue: 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(uvalue: DW_OP_bregx);
223 m_out_stream.PutULEB128(uval: reg_num);
224 } else
225 m_out_stream.PutHex8(uvalue: DW_OP_breg0 + reg_num);
226
227 m_out_stream.PutSLEB128(uval: 0);
228 ++m_stack_depth;
229}
230
231void DWARFCodegen::Visit(UnaryOpNode &unary, Node *&) {
232 Dispatch(node&: unary.Operand());
233
234 switch (unary.GetOpType()) {
235 case UnaryOpNode::Deref:
236 m_out_stream.PutHex8(uvalue: 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(node&: ptr);
250}
251

source code of lldb/source/Symbol/PostfixExpression.cpp