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