LLDB  mainline
PostfixExpression.cpp
Go to the documentation of this file.
1 //===-- PostfixExpression.cpp -----------------------------------*- C++ -*-===//
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::Parse(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc) {
45  llvm::SmallVector<Node *, 4> stack;
46 
47  llvm::StringRef token;
48  while (std::tie(token, expr) = getToken(expr), !token.empty()) {
49  if (auto op_type = GetBinaryOpType(token)) {
50  // token is binary operator
51  if (stack.size() < 2)
52  return nullptr;
53 
54  Node *right = stack.pop_back_val();
55  Node *left = stack.pop_back_val();
56  stack.push_back(MakeNode<BinaryOpNode>(alloc, *op_type, *left, *right));
57  continue;
58  }
59 
60  if (auto op_type = GetUnaryOpType(token)) {
61  // token is unary operator
62  if (stack.empty())
63  return nullptr;
64 
65  Node *operand = stack.pop_back_val();
66  stack.push_back(MakeNode<UnaryOpNode>(alloc, *op_type, *operand));
67  continue;
68  }
69 
70  uint32_t value;
71  if (to_integer(token, value, 10)) {
72  // token is integer literal
73  stack.push_back(MakeNode<IntegerNode>(alloc, value));
74  continue;
75  }
76 
77  stack.push_back(MakeNode<SymbolNode>(alloc, token));
78  }
79 
80  if (stack.size() != 1)
81  return nullptr;
82 
83  return stack.back();
84 }
85 
86 namespace {
87 class SymbolResolver : public Visitor<bool> {
88 public:
89  SymbolResolver(llvm::function_ref<Node *(SymbolNode &symbol)> replacer)
90  : m_replacer(replacer) {}
91 
93 
94 private:
95  bool Visit(BinaryOpNode &binary, Node *&) override {
96  return Dispatch(binary.Left()) && Dispatch(binary.Right());
97  }
98 
99  bool Visit(InitialValueNode &, Node *&) override { return true; }
100  bool Visit(IntegerNode &, Node *&) override { return true; }
101  bool Visit(RegisterNode &, Node *&) override { return true; }
102 
103  bool Visit(SymbolNode &symbol, Node *&ref) override {
104  if (Node *replacement = m_replacer(symbol)) {
105  ref = replacement;
106  if (replacement != &symbol)
107  return Dispatch(ref);
108  return true;
109  }
110  return false;
111  }
112 
113  bool Visit(UnaryOpNode &unary, Node *&) override {
114  return Dispatch(unary.Operand());
115  }
116 
117  llvm::function_ref<Node *(SymbolNode &symbol)> m_replacer;
118 };
119 
120 class DWARFCodegen : public Visitor<> {
121 public:
122  DWARFCodegen(Stream &stream) : m_out_stream(stream) {}
123 
124  using Visitor<>::Dispatch;
125 
126 private:
127  void Visit(BinaryOpNode &binary, Node *&) override;
128 
129  void Visit(InitialValueNode &val, Node *&) override;
130 
131  void Visit(IntegerNode &integer, Node *&) override {
132  m_out_stream.PutHex8(DW_OP_constu);
133  m_out_stream.PutULEB128(integer.GetValue());
134  ++m_stack_depth;
135  }
136 
137  void Visit(RegisterNode &reg, Node *&) override;
138 
139  void Visit(SymbolNode &symbol, Node *&) override {
140  llvm_unreachable("Symbols should have been resolved by now!");
141  }
142 
143  void Visit(UnaryOpNode &unary, Node *&) override;
144 
145  Stream &m_out_stream;
146 
147  /// The number keeping track of the evaluation stack depth at any given
148  /// moment. Used for implementing InitialValueNodes. We start with
149  /// m_stack_depth = 1, assuming that the initial value is already on the
150  /// stack. This initial value will be the value of all InitialValueNodes. If
151  /// the expression does not contain InitialValueNodes, then m_stack_depth is
152  /// not used, and the generated expression will run correctly even without an
153  /// initial value.
154  size_t m_stack_depth = 1;
155 };
156 } // namespace
157 
158 void DWARFCodegen::Visit(BinaryOpNode &binary, Node *&) {
159  Dispatch(binary.Left());
160  Dispatch(binary.Right());
161 
162  switch (binary.GetOpType()) {
163  case BinaryOpNode::Plus:
164  m_out_stream.PutHex8(DW_OP_plus);
165  // NOTE: can be optimized by using DW_OP_plus_uconst opcpode
166  // if right child node is constant value
167  break;
168  case BinaryOpNode::Minus:
169  m_out_stream.PutHex8(DW_OP_minus);
170  break;
171  case BinaryOpNode::Align:
172  // emit align operator a @ b as
173  // a & ~(b - 1)
174  // NOTE: implicitly assuming that b is power of 2
175  m_out_stream.PutHex8(DW_OP_lit1);
176  m_out_stream.PutHex8(DW_OP_minus);
177  m_out_stream.PutHex8(DW_OP_not);
178 
179  m_out_stream.PutHex8(DW_OP_and);
180  break;
181  }
182  --m_stack_depth; // Two pops, one push.
183 }
184 
185 void DWARFCodegen::Visit(InitialValueNode &, Node *&) {
186  // We never go below the initial stack, so we can pick the initial value from
187  // the bottom of the stack at any moment.
188  assert(m_stack_depth >= 1);
189  m_out_stream.PutHex8(DW_OP_pick);
190  m_out_stream.PutHex8(m_stack_depth - 1);
191  ++m_stack_depth;
192 }
193 
194 void DWARFCodegen::Visit(RegisterNode &reg, Node *&) {
195  uint32_t reg_num = reg.GetRegNum();
196  assert(reg_num != LLDB_INVALID_REGNUM);
197 
198  if (reg_num > 31) {
199  m_out_stream.PutHex8(DW_OP_bregx);
200  m_out_stream.PutULEB128(reg_num);
201  } else
202  m_out_stream.PutHex8(DW_OP_breg0 + reg_num);
203 
204  m_out_stream.PutSLEB128(0);
205  ++m_stack_depth;
206 }
207 
208 void DWARFCodegen::Visit(UnaryOpNode &unary, Node *&) {
209  Dispatch(unary.Operand());
210 
211  switch (unary.GetOpType()) {
212  case UnaryOpNode::Deref:
213  m_out_stream.PutHex8(DW_OP_deref);
214  break;
215  }
216  // Stack depth unchanged.
217 }
218 
220  Node *&node, llvm::function_ref<Node *(SymbolNode &)> replacer) {
221  return SymbolResolver(replacer).Dispatch(node);
222 }
223 
224 void postfix::ToDWARF(Node &node, Stream &stream) {
225  Node *ptr = &node;
226  DWARFCodegen(stream).Dispatch(ptr);
227 }
void ToDWARF(Node &node, Stream &stream)
Serialize the given expression tree as DWARF.
Enumerations for broadcasting.
Definition: SBLaunchInfo.h:14
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:
Node * Parse(llvm::StringRef expr, llvm::BumpPtrAllocator &alloc)
Parse the given postfix expression.
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.
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)
#define LLDB_INVALID_REGNUM
Definition: lldb-defines.h:90