LLDB mainline
PostfixExpression.cpp
Go to the documentation of this file.
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
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 '@':
31 case '-':
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()) {
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;
192 m_out_stream.PutHex8(DW_OP_minus);
193 break;
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()) {
236 m_out_stream.PutHex8(DW_OP_deref);
237 break;
238 }
239 // Stack depth unchanged.
240}
241
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}
#define integer
static std::optional< UnaryOpNode::OpType > GetUnaryOpType(llvm::StringRef token)
static std::optional< BinaryOpNode::OpType > GetBinaryOpType(llvm::StringRef token)
A stream class that can stream formatted output to a file.
Definition: Stream.h:28
A node representing a binary expression.
A node representing the canonical frame address.
A node representing an integer literal.
The base class for all nodes in the parsed postfix tree.
A node representing the value of a register with the given register number.
A node representing a symbolic reference to a named entity.
A node representing a unary operation.
A template class implementing a visitor pattern, but with a couple of twists:
virtual ResultT Visit(BinaryOpNode &binary, Node *&ref)=0
ResultT Dispatch(Node *&node)
Invoke the correct Visit function based on the dynamic type of the given node.
#define LLDB_INVALID_REGNUM
Definition: lldb-defines.h:79
Node * ParseOneExpression(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc)
Parse the given postfix expression.
void ToDWARF(Node &node, Stream &stream)
Serialize the given expression tree as DWARF.
bool ResolveSymbols(Node *&node, llvm::function_ref< Node *(SymbolNode &symbol)> replacer)
A utility function for "resolving" SymbolNodes.
std::vector< std::pair< llvm::StringRef, Node * > > ParseFPOProgram(llvm::StringRef prog, llvm::BumpPtrAllocator &alloc)
A class that represents a running process on the host machine.