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 #include <optional>
19 
20 using namespace lldb_private;
21 using namespace lldb_private::postfix;
22 using namespace lldb_private::dwarf;
23 
24 static std::optional<BinaryOpNode::OpType>
25 GetBinaryOpType(llvm::StringRef token) {
26   if (token.size() != 1)
27     return std::nullopt;
28   switch (token[0]) {
29   case '@':
30     return BinaryOpNode::Align;
31   case '-':
32     return BinaryOpNode::Minus;
33   case '+':
34     return BinaryOpNode::Plus;
35   }
36   return std::nullopt;
37 }
38 
39 static std::optional<UnaryOpNode::OpType>
40 GetUnaryOpType(llvm::StringRef token) {
41   if (token == "^")
42     return UnaryOpNode::Deref;
43   return std::nullopt;
44 }
45 
46 Node *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 
89 std::vector<std::pair<llvm::StringRef, Node *>>
90 postfix::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 
109 namespace {
110 class SymbolResolver : public Visitor<bool> {
111 public:
112   SymbolResolver(llvm::function_ref<Node *(SymbolNode &symbol)> replacer)
113       : m_replacer(replacer) {}
114 
115   using Visitor<bool>::Dispatch;
116 
117 private:
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 
143 class DWARFCodegen : public Visitor<> {
144 public:
145   DWARFCodegen(Stream &stream) : m_out_stream(stream) {}
146 
147   using Visitor<>::Dispatch;
148 
149 private:
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 
181 void DWARFCodegen::Visit(BinaryOpNode &binary, Node *&) {
182   Dispatch(binary.Left());
183   Dispatch(binary.Right());
184 
185   switch (binary.GetOpType()) {
186   case BinaryOpNode::Plus:
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;
191   case BinaryOpNode::Minus:
192     m_out_stream.PutHex8(DW_OP_minus);
193     break;
194   case BinaryOpNode::Align:
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 
208 void 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 
217 void 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 
231 void DWARFCodegen::Visit(UnaryOpNode &unary, Node *&) {
232   Dispatch(unary.Operand());
233 
234   switch (unary.GetOpType()) {
235   case UnaryOpNode::Deref:
236     m_out_stream.PutHex8(DW_OP_deref);
237     break;
238   }
239   // Stack depth unchanged.
240 }
241 
242 bool postfix::ResolveSymbols(
243     Node *&node, llvm::function_ref<Node *(SymbolNode &)> replacer) {
244   return SymbolResolver(replacer).Dispatch(node);
245 }
246 
247 void postfix::ToDWARF(Node &node, Stream &stream) {
248   Node *ptr = &node;
249   DWARFCodegen(stream).Dispatch(ptr);
250 }
251