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 
19 using namespace lldb_private;
20 using namespace lldb_private::postfix;
21 
22 static llvm::Optional<BinaryOpNode::OpType>
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>
38 GetUnaryOpType(llvm::StringRef token) {
39  if (token == "^")
40  return UnaryOpNode::Deref;
41  return llvm::None;
42 }
43 
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 *>>
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:
110  SymbolResolver(llvm::function_ref<Node *(SymbolNode &symbol)> replacer)
111  : m_replacer(replacer) {}
112 
114 
115 private:
116  bool Visit(BinaryOpNode &binary, Node *&) override {
117  return Dispatch(binary.Left()) && Dispatch(binary.Right());
118  }
119 
120  bool Visit(InitialValueNode &, Node *&) override { return true; }
121  bool Visit(IntegerNode &, Node *&) override { return true; }
122  bool Visit(RegisterNode &, Node *&) override { return true; }
123 
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 
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:
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 
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 &reg, Node *&) override;
159 
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 
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 
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 
215 void DWARFCodegen::Visit(RegisterNode &reg, 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 
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 
241  Node *&node, llvm::function_ref<Node *(SymbolNode &)> replacer) {
242  return SymbolResolver(replacer).Dispatch(node);
243 }
244 
245 void postfix::ToDWARF(Node &node, Stream &stream) {
246  Node *ptr = &node;
247  DWARFCodegen(stream).Dispatch(ptr);
248 }
void ToDWARF(Node &node, Stream &stream)
Serialize the given expression tree as DWARF.
A class that represents a running process on the host machine.
A stream class that can stream formatted output to a file.
Definition: Stream.h:28
A node representing a symbolic reference to a named entity.
bool ResolveSymbols(Node *&node, llvm::function_ref< Node *(SymbolNode &symbol)> replacer)
A utility function for "resolving" SymbolNodes.
A node representing an integer literal.
A template class implementing a visitor pattern, but with a couple of twists:
A node representing a unary operation.
The base class for all nodes in the parsed postfix tree.
static llvm::Optional< UnaryOpNode::OpType > GetUnaryOpType(llvm::StringRef token)
A node representing a binary expression.
std::vector< std::pair< llvm::StringRef, Node * > > ParseFPOProgram(llvm::StringRef prog, llvm::BumpPtrAllocator &alloc)
A node representing the canonical frame address.
#define integer
A node representing the value of a register with the given register number.
static llvm::Optional< BinaryOpNode::OpType > GetBinaryOpType(llvm::StringRef token)
Node * ParseOneExpression(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc)
Parse the given postfix expression.
#define LLDB_INVALID_REGNUM
Definition: lldb-defines.h:90