1 //===-- PDBFPOProgramToDWARFExpression.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 #include "PdbFPOProgramToDWARFExpression.h"
10 #include "CodeViewRegisterMapping.h"
11 
12 #include "lldb/Core/StreamBuffer.h"
13 #include "lldb/Core/dwarf.h"
14 #include "lldb/Symbol/PostfixExpression.h"
15 #include "lldb/Utility/LLDBAssert.h"
16 #include "lldb/Utility/Stream.h"
17 #include "llvm/ADT/DenseMap.h"
18 
19 #include "llvm/ADT/StringExtras.h"
20 #include "llvm/DebugInfo/CodeView/CodeView.h"
21 #include "llvm/DebugInfo/CodeView/EnumTables.h"
22 
23 using namespace lldb;
24 using namespace lldb_private;
25 using namespace lldb_private::postfix;
26 
27 namespace {
28 
29 class NodeAllocator {
30 public:
31   template <typename T, typename... Args> T *makeNode(Args &&... args) {
32     static_assert(std::is_trivially_destructible<T>::value,
33                   "This object will not be destroyed!");
34     void *new_node_mem = m_alloc.Allocate(sizeof(T), alignof(T));
35     return new (new_node_mem) T(std::forward<Args>(args)...);
36   }
37 
38 private:
39   llvm::BumpPtrAllocator m_alloc;
40 };
41 
42 class FPOProgramASTVisitorMergeDependent : public Visitor<> {
43 public:
44   void Visit(BinaryOpNode &binary, Node *&) override {
45     Dispatch(binary.Left());
46     Dispatch(binary.Right());
47   }
48 
49   void Visit(UnaryOpNode &unary, Node *&) override {
50     Dispatch(unary.Operand());
51   }
52 
53   void Visit(RegisterNode &, Node *&) override {}
54   void Visit(IntegerNode &, Node *&) override {}
55   void Visit(SymbolNode &symbol, Node *&ref) override;
56 
57   static void
58   Merge(const llvm::DenseMap<llvm::StringRef, Node *> &dependent_programs,
59         Node *&ast) {
60     FPOProgramASTVisitorMergeDependent(dependent_programs).Dispatch(ast);
61   }
62 
63 private:
64   FPOProgramASTVisitorMergeDependent(
65       const llvm::DenseMap<llvm::StringRef, Node *> &dependent_programs)
66       : m_dependent_programs(dependent_programs) {}
67 
68   const llvm::DenseMap<llvm::StringRef, Node *> &m_dependent_programs;
69 };
70 
71 void FPOProgramASTVisitorMergeDependent::Visit(SymbolNode &symbol, Node *&ref) {
72   auto it = m_dependent_programs.find(symbol.GetName());
73   if (it == m_dependent_programs.end())
74     return;
75 
76   ref = it->second;
77   Dispatch(ref);
78 }
79 
80 class FPOProgramASTVisitorResolveRegisterRefs : public Visitor<bool> {
81 public:
82   static bool
83   Resolve(const llvm::DenseMap<llvm::StringRef, Node *> &dependent_programs,
84           llvm::Triple::ArchType arch_type, NodeAllocator &alloc, Node *&ast) {
85     return FPOProgramASTVisitorResolveRegisterRefs(dependent_programs,
86                                                    arch_type, alloc)
87         .Dispatch(ast);
88   }
89 
90   bool Visit(BinaryOpNode &binary, Node *&) override {
91     return Dispatch(binary.Left()) && Dispatch(binary.Right());
92   }
93 
94   bool Visit(UnaryOpNode &unary, Node *&) override {
95     return Dispatch(unary.Operand());
96   }
97 
98   bool Visit(RegisterNode &, Node *&) override { return true; }
99 
100   bool Visit(IntegerNode &, Node *&) override { return true; }
101 
102   bool Visit(SymbolNode &symbol, Node *&ref) override;
103 
104 private:
105   FPOProgramASTVisitorResolveRegisterRefs(
106       const llvm::DenseMap<llvm::StringRef, Node *> &dependent_programs,
107       llvm::Triple::ArchType arch_type, NodeAllocator &alloc)
108       : m_dependent_programs(dependent_programs), m_arch_type(arch_type),
109         m_alloc(alloc) {}
110 
111   const llvm::DenseMap<llvm::StringRef, Node *> &m_dependent_programs;
112   llvm::Triple::ArchType m_arch_type;
113   NodeAllocator &m_alloc;
114 };
115 
116 static uint32_t ResolveLLDBRegisterNum(llvm::StringRef reg_name, llvm::Triple::ArchType arch_type) {
117   // lookup register name to get lldb register number
118   llvm::ArrayRef<llvm::EnumEntry<uint16_t>> register_names =
119       llvm::codeview::getRegisterNames();
120   auto it = llvm::find_if(
121       register_names,
122       [&reg_name](const llvm::EnumEntry<uint16_t> &register_entry) {
123         return reg_name.compare_lower(register_entry.Name) == 0;
124       });
125 
126   if (it == register_names.end())
127     return LLDB_INVALID_REGNUM;
128 
129   auto reg_id = static_cast<llvm::codeview::RegisterId>(it->Value);
130   return npdb::GetLLDBRegisterNumber(arch_type, reg_id);
131 }
132 
133 bool FPOProgramASTVisitorResolveRegisterRefs::Visit(SymbolNode &symbol,
134                                                     Node *&ref) {
135   // Look up register reference as lvalue in preceding assignments.
136   auto it = m_dependent_programs.find(symbol.GetName());
137   if (it != m_dependent_programs.end()) {
138     // Dependent programs are handled elsewhere.
139     return true;
140   }
141 
142   uint32_t reg_num =
143       ResolveLLDBRegisterNum(symbol.GetName().drop_front(1), m_arch_type);
144 
145   if (reg_num == LLDB_INVALID_REGNUM)
146     return false;
147 
148   ref = m_alloc.makeNode<RegisterNode>(reg_num);
149   return true;
150 }
151 
152 class FPOProgramASTVisitorDWARFCodegen : public Visitor<> {
153 public:
154   static void Emit(Stream &stream, Node *&ast) {
155     FPOProgramASTVisitorDWARFCodegen(stream).Dispatch(ast);
156   }
157 
158   void Visit(RegisterNode &reg, Node *&);
159   void Visit(BinaryOpNode &binary, Node *&);
160   void Visit(UnaryOpNode &unary, Node *&);
161   void Visit(SymbolNode &symbol, Node *&) {
162     llvm_unreachable("Symbols should have been resolved by now!");
163   }
164   void Visit(IntegerNode &integer, Node *&);
165 
166 private:
167   FPOProgramASTVisitorDWARFCodegen(Stream &stream) : m_out_stream(stream) {}
168 
169   Stream &m_out_stream;
170 };
171 
172 void FPOProgramASTVisitorDWARFCodegen::Visit(RegisterNode &reg, Node *&) {
173   uint32_t reg_num = reg.GetRegNum();
174   lldbassert(reg_num != LLDB_INVALID_REGNUM);
175 
176   if (reg_num > 31) {
177     m_out_stream.PutHex8(DW_OP_bregx);
178     m_out_stream.PutULEB128(reg_num);
179   } else
180     m_out_stream.PutHex8(DW_OP_breg0 + reg_num);
181 
182   m_out_stream.PutSLEB128(0);
183 }
184 
185 void FPOProgramASTVisitorDWARFCodegen::Visit(IntegerNode &integer, Node *&) {
186   uint32_t value = integer.GetValue();
187   m_out_stream.PutHex8(DW_OP_constu);
188   m_out_stream.PutULEB128(value);
189 }
190 
191 void FPOProgramASTVisitorDWARFCodegen::Visit(BinaryOpNode &binary, Node *&) {
192   Dispatch(binary.Left());
193   Dispatch(binary.Right());
194 
195   switch (binary.GetOpType()) {
196   case BinaryOpNode::Plus:
197     m_out_stream.PutHex8(DW_OP_plus);
198     // NOTE: can be optimized by using DW_OP_plus_uconst opcpode
199     //       if right child node is constant value
200     break;
201   case BinaryOpNode::Minus:
202     m_out_stream.PutHex8(DW_OP_minus);
203     break;
204   case BinaryOpNode::Align:
205     // emit align operator a @ b as
206     // a & ~(b - 1)
207     // NOTE: implicitly assuming that b is power of 2
208     m_out_stream.PutHex8(DW_OP_lit1);
209     m_out_stream.PutHex8(DW_OP_minus);
210     m_out_stream.PutHex8(DW_OP_not);
211 
212     m_out_stream.PutHex8(DW_OP_and);
213     break;
214   }
215 }
216 
217 void FPOProgramASTVisitorDWARFCodegen::Visit(UnaryOpNode &unary, Node *&) {
218   Dispatch(unary.Operand());
219 
220   switch (unary.GetOpType()) {
221   case UnaryOpNode::Deref:
222     m_out_stream.PutHex8(DW_OP_deref);
223     break;
224   }
225 }
226 
227 } // namespace
228 
229 static bool ParseFPOSingleAssignmentProgram(llvm::StringRef program,
230                                             NodeAllocator &alloc,
231                                             llvm::StringRef &register_name,
232                                             Node *&ast) {
233   llvm::SmallVector<llvm::StringRef, 16> tokens;
234   llvm::SplitString(program, tokens, " ");
235 
236   if (tokens.empty())
237     return false;
238 
239   llvm::SmallVector<Node *, 4> eval_stack;
240 
241   llvm::DenseMap<llvm::StringRef, BinaryOpNode::OpType> ops_binary = {
242       {"+", BinaryOpNode::Plus},
243       {"-", BinaryOpNode::Minus},
244       {"@", BinaryOpNode::Align},
245   };
246 
247   llvm::DenseMap<llvm::StringRef, UnaryOpNode::OpType> ops_unary = {
248       {"^", UnaryOpNode::Deref},
249   };
250 
251   constexpr llvm::StringLiteral ra_search_keyword = ".raSearch";
252 
253   // lvalue of assignment is always first token
254   // rvalue program goes next
255   for (size_t i = 1; i < tokens.size(); ++i) {
256     llvm::StringRef cur = tokens[i];
257 
258     auto ops_binary_it = ops_binary.find(cur);
259     if (ops_binary_it != ops_binary.end()) {
260       // token is binary operator
261       if (eval_stack.size() < 2) {
262         return false;
263       }
264       Node *right = eval_stack.pop_back_val();
265       Node *left = eval_stack.pop_back_val();
266       Node *node =
267           alloc.makeNode<BinaryOpNode>(ops_binary_it->second, *left, *right);
268       eval_stack.push_back(node);
269       continue;
270     }
271 
272     auto ops_unary_it = ops_unary.find(cur);
273     if (ops_unary_it != ops_unary.end()) {
274       // token is unary operator
275       if (eval_stack.empty()) {
276         return false;
277       }
278       Node *operand = eval_stack.pop_back_val();
279       Node *node = alloc.makeNode<UnaryOpNode>(ops_unary_it->second, *operand);
280       eval_stack.push_back(node);
281       continue;
282     }
283 
284     if (cur.startswith("$")) {
285       eval_stack.push_back(alloc.makeNode<SymbolNode>(cur));
286       continue;
287     }
288 
289     if (cur == ra_search_keyword) {
290       // TODO: .raSearch is unsupported
291       return false;
292     }
293 
294     uint32_t value;
295     if (!cur.getAsInteger(10, value)) {
296       // token is integer literal
297       eval_stack.push_back(alloc.makeNode<IntegerNode>(value));
298       continue;
299     }
300 
301     // unexpected token
302     return false;
303   }
304 
305   if (eval_stack.size() != 1) {
306     return false;
307   }
308 
309   register_name = tokens[0];
310   ast = eval_stack.pop_back_val();
311 
312   return true;
313 }
314 
315 static Node *ParseFPOProgram(llvm::StringRef program,
316                              llvm::StringRef register_name,
317                              llvm::Triple::ArchType arch_type,
318                              NodeAllocator &alloc) {
319   llvm::DenseMap<llvm::StringRef, Node *> dependent_programs;
320 
321   size_t cur = 0;
322   while (true) {
323     size_t assign_index = program.find('=', cur);
324     if (assign_index == llvm::StringRef::npos) {
325       llvm::StringRef tail = program.slice(cur, llvm::StringRef::npos);
326       if (!tail.trim().empty()) {
327         // missing assign operator
328         return nullptr;
329       }
330       break;
331     }
332     llvm::StringRef assignment_program = program.slice(cur, assign_index);
333 
334     llvm::StringRef lvalue_name;
335     Node *rvalue_ast = nullptr;
336     if (!ParseFPOSingleAssignmentProgram(assignment_program, alloc, lvalue_name,
337                                          rvalue_ast)) {
338       return nullptr;
339     }
340 
341     lldbassert(rvalue_ast);
342 
343     // check & resolve assignment program
344     if (!FPOProgramASTVisitorResolveRegisterRefs::Resolve(
345             dependent_programs, arch_type, alloc, rvalue_ast))
346       return nullptr;
347 
348     if (lvalue_name == register_name) {
349       // found target assignment program - no need to parse further
350 
351       // emplace valid dependent subtrees to make target assignment independent
352       // from predecessors
353       FPOProgramASTVisitorMergeDependent::Merge(dependent_programs, rvalue_ast);
354 
355       return rvalue_ast;
356     }
357 
358     dependent_programs[lvalue_name] = rvalue_ast;
359     cur = assign_index + 1;
360   }
361 
362   return nullptr;
363 }
364 
365 bool lldb_private::npdb::TranslateFPOProgramToDWARFExpression(
366     llvm::StringRef program, llvm::StringRef register_name,
367     llvm::Triple::ArchType arch_type, Stream &stream) {
368   NodeAllocator node_alloc;
369   Node *target_program =
370       ParseFPOProgram(program, register_name, arch_type, node_alloc);
371   if (target_program == nullptr) {
372     return false;
373   }
374 
375   FPOProgramASTVisitorDWARFCodegen::Emit(stream, target_program);
376   return true;
377 }
378