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 
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 
114   using Visitor<bool>::Dispatch;
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 
241 bool postfix::ResolveSymbols(
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 }
250