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