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/Utility/LLDBAssert.h"
15 #include "lldb/Utility/Stream.h"
16 #include "llvm/ADT/DenseMap.h"
17 
18 #include "llvm/ADT/StringExtras.h"
19 #include "llvm/DebugInfo/CodeView/CodeView.h"
20 #include "llvm/DebugInfo/CodeView/EnumTables.h"
21 
22 using namespace lldb;
23 using namespace lldb_private;
24 
25 namespace {
26 
27 class FPOProgramNode;
28 class FPOProgramASTVisitor;
29 
30 class NodeAllocator {
31 public:
32   template <typename T, typename... Args> T *makeNode(Args &&... args) {
33     void *new_node_mem = m_alloc.Allocate(sizeof(T), alignof(T));
34     return new (new_node_mem) T(std::forward<Args>(args)...);
35   }
36 
37 private:
38   llvm::BumpPtrAllocator m_alloc;
39 };
40 
41 class FPOProgramNode {
42 public:
43   enum Kind {
44     Symbol,
45     Register,
46     IntegerLiteral,
47     BinaryOp,
48     UnaryOp,
49   };
50 
51 protected:
52   FPOProgramNode(Kind kind) : m_token_kind(kind) {}
53 
54 public:
55   virtual ~FPOProgramNode() = default;
56   virtual void Accept(FPOProgramASTVisitor *visitor) = 0;
57 
58   Kind GetKind() const { return m_token_kind; }
59 
60 private:
61   Kind m_token_kind;
62 };
63 
64 class FPOProgramNodeSymbol: public FPOProgramNode {
65 public:
66   FPOProgramNodeSymbol(llvm::StringRef name)
67       : FPOProgramNode(Symbol), m_name(name) {}
68 
69   void Accept(FPOProgramASTVisitor *visitor) override;
70 
71   llvm::StringRef GetName() const { return m_name; }
72 
73 private:
74   llvm::StringRef m_name;
75 };
76 
77 class FPOProgramNodeRegisterRef : public FPOProgramNode {
78 public:
79   FPOProgramNodeRegisterRef(uint32_t lldb_reg_num)
80       : FPOProgramNode(Register), m_lldb_reg_num(lldb_reg_num) {}
81 
82   void Accept(FPOProgramASTVisitor *visitor) override;
83 
84   uint32_t GetLLDBRegNum() const { return m_lldb_reg_num; }
85 
86 private:
87   uint32_t m_lldb_reg_num;
88 };
89 
90 class FPOProgramNodeIntegerLiteral : public FPOProgramNode {
91 public:
92   FPOProgramNodeIntegerLiteral(uint32_t value)
93       : FPOProgramNode(IntegerLiteral), m_value(value) {}
94 
95   void Accept(FPOProgramASTVisitor *visitor) override;
96 
97   uint32_t GetValue() const { return m_value; }
98 
99 private:
100   uint32_t m_value;
101 };
102 
103 class FPOProgramNodeBinaryOp : public FPOProgramNode {
104 public:
105   enum OpType {
106     Plus,
107     Minus,
108     Align,
109   };
110 
111   FPOProgramNodeBinaryOp(OpType op_type, FPOProgramNode *left,
112                          FPOProgramNode *right)
113       : FPOProgramNode(BinaryOp), m_op_type(op_type), m_left(left),
114         m_right(right) {}
115 
116   void Accept(FPOProgramASTVisitor *visitor) override;
117 
118   OpType GetOpType() const { return m_op_type; }
119 
120   const FPOProgramNode *Left() const { return m_left; }
121   FPOProgramNode *&Left() { return m_left; }
122 
123   const FPOProgramNode *Right() const { return m_right; }
124   FPOProgramNode *&Right() { return m_right; }
125 
126 private:
127   OpType m_op_type;
128   FPOProgramNode *m_left;
129   FPOProgramNode *m_right;
130 };
131 
132 class FPOProgramNodeUnaryOp : public FPOProgramNode {
133 public:
134   enum OpType {
135     Deref,
136   };
137 
138   FPOProgramNodeUnaryOp(OpType op_type, FPOProgramNode *operand)
139       : FPOProgramNode(UnaryOp), m_op_type(op_type), m_operand(operand) {}
140 
141   void Accept(FPOProgramASTVisitor *visitor) override;
142 
143   OpType GetOpType() const { return m_op_type; }
144 
145   const FPOProgramNode *Operand() const { return m_operand; }
146   FPOProgramNode *&Operand() { return m_operand; }
147 
148 private:
149   OpType m_op_type;
150   FPOProgramNode *m_operand;
151 };
152 
153 class FPOProgramASTVisitor {
154 public:
155   virtual ~FPOProgramASTVisitor() = default;
156 
157   virtual void Visit(FPOProgramNodeSymbol *node) {}
158   virtual void Visit(FPOProgramNodeRegisterRef *node) {}
159   virtual void Visit(FPOProgramNodeIntegerLiteral *node) {}
160   virtual void Visit(FPOProgramNodeBinaryOp *node) {}
161   virtual void Visit(FPOProgramNodeUnaryOp *node) {}
162 };
163 
164 void FPOProgramNodeSymbol::Accept(FPOProgramASTVisitor *visitor) {
165   visitor->Visit(this);
166 }
167 
168 void FPOProgramNodeRegisterRef::Accept(FPOProgramASTVisitor *visitor) {
169   visitor->Visit(this);
170 }
171 
172 void FPOProgramNodeIntegerLiteral::Accept(FPOProgramASTVisitor *visitor) {
173   visitor->Visit(this);
174 }
175 
176 void FPOProgramNodeBinaryOp::Accept(FPOProgramASTVisitor *visitor) {
177   visitor->Visit(this);
178 }
179 
180 void FPOProgramNodeUnaryOp::Accept(FPOProgramASTVisitor *visitor) {
181   visitor->Visit(this);
182 }
183 
184 class FPOProgramASTVisitorMergeDependent : public FPOProgramASTVisitor {
185 public:
186   FPOProgramASTVisitorMergeDependent(
187       const llvm::DenseMap<llvm::StringRef, FPOProgramNode *>
188           &dependent_programs)
189       : m_dependent_programs(dependent_programs) {}
190 
191   void Merge(FPOProgramNode *&node_ref);
192 
193 private:
194   void Visit(FPOProgramNodeRegisterRef *node) override {}
195   void Visit(FPOProgramNodeIntegerLiteral *node) override {}
196   void Visit(FPOProgramNodeBinaryOp *node) override;
197   void Visit(FPOProgramNodeUnaryOp *node) override;
198 
199   void TryReplace(FPOProgramNode *&node_ref) const;
200 
201 private:
202   const llvm::DenseMap<llvm::StringRef, FPOProgramNode *> &m_dependent_programs;
203 };
204 
205 void FPOProgramASTVisitorMergeDependent::Merge(FPOProgramNode *&node_ref) {
206   TryReplace(node_ref);
207   node_ref->Accept(this);
208 }
209 
210 void FPOProgramASTVisitorMergeDependent::Visit(FPOProgramNodeBinaryOp *node) {
211   Merge(node->Left());
212   Merge(node->Right());
213 }
214 void FPOProgramASTVisitorMergeDependent::Visit(FPOProgramNodeUnaryOp *node) {
215   Merge(node->Operand());
216 }
217 
218 void FPOProgramASTVisitorMergeDependent::TryReplace(
219     FPOProgramNode *&node_ref) const {
220 
221   while (node_ref->GetKind() == FPOProgramNode::Symbol) {
222     auto *node_symbol_ref = static_cast<FPOProgramNodeSymbol *>(node_ref);
223 
224     auto it = m_dependent_programs.find(node_symbol_ref->GetName());
225     if (it == m_dependent_programs.end()) {
226       break;
227     }
228 
229     node_ref = it->second;
230   }
231 }
232 
233 class FPOProgramASTVisitorResolveRegisterRefs : public FPOProgramASTVisitor {
234 public:
235   FPOProgramASTVisitorResolveRegisterRefs(
236       const llvm::DenseMap<llvm::StringRef, FPOProgramNode *>
237           &dependent_programs,
238       llvm::Triple::ArchType arch_type, NodeAllocator &alloc)
239       : m_dependent_programs(dependent_programs), m_arch_type(arch_type),
240         m_alloc(alloc) {}
241 
242   bool Resolve(FPOProgramNode *&program);
243 
244 private:
245   void Visit(FPOProgramNodeBinaryOp *node) override;
246   void Visit(FPOProgramNodeUnaryOp *node) override;
247 
248   bool TryReplace(FPOProgramNode *&node_ref);
249 
250   const llvm::DenseMap<llvm::StringRef, FPOProgramNode *> &m_dependent_programs;
251   llvm::Triple::ArchType m_arch_type;
252   NodeAllocator &m_alloc;
253   bool m_no_error_flag = true;
254 };
255 
256 bool FPOProgramASTVisitorResolveRegisterRefs::Resolve(FPOProgramNode *&program) {
257   if (!TryReplace(program))
258     return false;
259   program->Accept(this);
260   return m_no_error_flag;
261 }
262 
263 static uint32_t ResolveLLDBRegisterNum(llvm::StringRef reg_name, llvm::Triple::ArchType arch_type) {
264   // lookup register name to get lldb register number
265   llvm::ArrayRef<llvm::EnumEntry<uint16_t>> register_names =
266       llvm::codeview::getRegisterNames();
267   auto it = llvm::find_if(
268       register_names,
269       [&reg_name](const llvm::EnumEntry<uint16_t> &register_entry) {
270         return reg_name.compare_lower(register_entry.Name) == 0;
271       });
272 
273   if (it == register_names.end())
274     return LLDB_INVALID_REGNUM;
275 
276   auto reg_id = static_cast<llvm::codeview::RegisterId>(it->Value);
277   return npdb::GetLLDBRegisterNumber(arch_type, reg_id);
278 }
279 
280 bool FPOProgramASTVisitorResolveRegisterRefs::TryReplace(
281     FPOProgramNode *&node_ref) {
282   if (node_ref->GetKind() != FPOProgramNode::Symbol)
283     return true;
284 
285   auto *symbol = static_cast<FPOProgramNodeSymbol *>(node_ref);
286 
287   // Look up register reference as lvalue in preceding assignments.
288   auto it = m_dependent_programs.find(symbol->GetName());
289   if (it != m_dependent_programs.end()) {
290     // Dependent programs are handled elsewhere.
291     return true;
292   }
293 
294   uint32_t reg_num =
295       ResolveLLDBRegisterNum(symbol->GetName().drop_front(1), m_arch_type);
296 
297   if (reg_num == LLDB_INVALID_REGNUM)
298     return false;
299 
300   node_ref = m_alloc.makeNode<FPOProgramNodeRegisterRef>(reg_num);
301   return true;
302 }
303 
304 void FPOProgramASTVisitorResolveRegisterRefs::Visit(
305     FPOProgramNodeBinaryOp *node) {
306   m_no_error_flag = Resolve(node->Left()) && Resolve(node->Right());
307 }
308 
309 void FPOProgramASTVisitorResolveRegisterRefs::Visit(
310     FPOProgramNodeUnaryOp *node) {
311   m_no_error_flag = Resolve(node->Operand());
312 }
313 
314 class FPOProgramASTVisitorDWARFCodegen : public FPOProgramASTVisitor {
315 public:
316   FPOProgramASTVisitorDWARFCodegen(Stream &stream) : m_out_stream(stream) {}
317 
318   void Emit(FPOProgramNode *program);
319 
320 private:
321   void Visit(FPOProgramNodeRegisterRef *node) override;
322   void Visit(FPOProgramNodeIntegerLiteral *node) override;
323   void Visit(FPOProgramNodeBinaryOp *node) override;
324   void Visit(FPOProgramNodeUnaryOp *node) override;
325 
326 private:
327   Stream &m_out_stream;
328 };
329 
330 void FPOProgramASTVisitorDWARFCodegen::Emit(FPOProgramNode *program) {
331   program->Accept(this);
332 }
333 
334 void FPOProgramASTVisitorDWARFCodegen::Visit(FPOProgramNodeRegisterRef *node) {
335 
336   uint32_t reg_num = node->GetLLDBRegNum();
337   lldbassert(reg_num != LLDB_INVALID_REGNUM);
338 
339   if (reg_num > 31) {
340     m_out_stream.PutHex8(DW_OP_bregx);
341     m_out_stream.PutULEB128(reg_num);
342   } else
343     m_out_stream.PutHex8(DW_OP_breg0 + reg_num);
344 
345   m_out_stream.PutSLEB128(0);
346 }
347 
348 void FPOProgramASTVisitorDWARFCodegen::Visit(
349     FPOProgramNodeIntegerLiteral *node) {
350   uint32_t value = node->GetValue();
351   m_out_stream.PutHex8(DW_OP_constu);
352   m_out_stream.PutULEB128(value);
353 }
354 
355 void FPOProgramASTVisitorDWARFCodegen::Visit(FPOProgramNodeBinaryOp *node) {
356 
357   Emit(node->Left());
358   Emit(node->Right());
359 
360   switch (node->GetOpType()) {
361   case FPOProgramNodeBinaryOp::Plus:
362     m_out_stream.PutHex8(DW_OP_plus);
363     // NOTE: can be optimized by using DW_OP_plus_uconst opcpode
364     //       if right child node is constant value
365     break;
366   case FPOProgramNodeBinaryOp::Minus:
367     m_out_stream.PutHex8(DW_OP_minus);
368     break;
369   case FPOProgramNodeBinaryOp::Align:
370     // emit align operator a @ b as
371     // a & ~(b - 1)
372     // NOTE: implicitly assuming that b is power of 2
373     m_out_stream.PutHex8(DW_OP_lit1);
374     m_out_stream.PutHex8(DW_OP_minus);
375     m_out_stream.PutHex8(DW_OP_not);
376 
377     m_out_stream.PutHex8(DW_OP_and);
378     break;
379   }
380 }
381 
382 void FPOProgramASTVisitorDWARFCodegen::Visit(FPOProgramNodeUnaryOp *node) {
383   Emit(node->Operand());
384 
385   switch (node->GetOpType()) {
386   case FPOProgramNodeUnaryOp::Deref:
387     m_out_stream.PutHex8(DW_OP_deref);
388     break;
389   }
390 }
391 
392 } // namespace
393 
394 static bool ParseFPOSingleAssignmentProgram(llvm::StringRef program,
395                                             NodeAllocator &alloc,
396                                             llvm::StringRef &register_name,
397                                             FPOProgramNode *&ast) {
398   llvm::SmallVector<llvm::StringRef, 16> tokens;
399   llvm::SplitString(program, tokens, " ");
400 
401   if (tokens.empty())
402     return false;
403 
404   llvm::SmallVector<FPOProgramNode *, 4> eval_stack;
405 
406   llvm::DenseMap<llvm::StringRef, FPOProgramNodeBinaryOp::OpType> ops_binary = {
407       {"+", FPOProgramNodeBinaryOp::Plus},
408       {"-", FPOProgramNodeBinaryOp::Minus},
409       {"@", FPOProgramNodeBinaryOp::Align},
410   };
411 
412   llvm::DenseMap<llvm::StringRef, FPOProgramNodeUnaryOp::OpType> ops_unary = {
413       {"^", FPOProgramNodeUnaryOp::Deref},
414   };
415 
416   constexpr llvm::StringLiteral ra_search_keyword = ".raSearch";
417 
418   // lvalue of assignment is always first token
419   // rvalue program goes next
420   for (size_t i = 1; i < tokens.size(); ++i) {
421     llvm::StringRef cur = tokens[i];
422 
423     auto ops_binary_it = ops_binary.find(cur);
424     if (ops_binary_it != ops_binary.end()) {
425       // token is binary operator
426       if (eval_stack.size() < 2) {
427         return false;
428       }
429       FPOProgramNode *right = eval_stack.pop_back_val();
430       FPOProgramNode *left = eval_stack.pop_back_val();
431       FPOProgramNode *node = alloc.makeNode<FPOProgramNodeBinaryOp>(
432           ops_binary_it->second, left, right);
433       eval_stack.push_back(node);
434       continue;
435     }
436 
437     auto ops_unary_it = ops_unary.find(cur);
438     if (ops_unary_it != ops_unary.end()) {
439       // token is unary operator
440       if (eval_stack.empty()) {
441         return false;
442       }
443       FPOProgramNode *operand = eval_stack.pop_back_val();
444       FPOProgramNode *node =
445           alloc.makeNode<FPOProgramNodeUnaryOp>(ops_unary_it->second, operand);
446       eval_stack.push_back(node);
447       continue;
448     }
449 
450     if (cur.startswith("$")) {
451       eval_stack.push_back(alloc.makeNode<FPOProgramNodeSymbol>(cur));
452       continue;
453     }
454 
455     if (cur == ra_search_keyword) {
456       // TODO: .raSearch is unsupported
457       return false;
458     }
459 
460     uint32_t value;
461     if (!cur.getAsInteger(10, value)) {
462       // token is integer literal
463       eval_stack.push_back(alloc.makeNode<FPOProgramNodeIntegerLiteral>(value));
464       continue;
465     }
466 
467     // unexpected token
468     return false;
469   }
470 
471   if (eval_stack.size() != 1) {
472     return false;
473   }
474 
475   register_name = tokens[0];
476   ast = eval_stack.pop_back_val();
477 
478   return true;
479 }
480 
481 static FPOProgramNode *ParseFPOProgram(llvm::StringRef program,
482                                        llvm::StringRef register_name,
483                                        llvm::Triple::ArchType arch_type,
484                                        NodeAllocator &alloc) {
485   llvm::DenseMap<llvm::StringRef, FPOProgramNode *> dependent_programs;
486 
487   size_t cur = 0;
488   while (true) {
489     size_t assign_index = program.find('=', cur);
490     if (assign_index == llvm::StringRef::npos) {
491       llvm::StringRef tail = program.slice(cur, llvm::StringRef::npos);
492       if (!tail.trim().empty()) {
493         // missing assign operator
494         return nullptr;
495       }
496       break;
497     }
498     llvm::StringRef assignment_program = program.slice(cur, assign_index);
499 
500     llvm::StringRef lvalue_name;
501     FPOProgramNode *rvalue_ast = nullptr;
502     if (!ParseFPOSingleAssignmentProgram(assignment_program, alloc, lvalue_name,
503                                          rvalue_ast)) {
504       return nullptr;
505     }
506 
507     lldbassert(rvalue_ast);
508 
509     // check & resolve assignment program
510     FPOProgramASTVisitorResolveRegisterRefs resolver(dependent_programs,
511                                                      arch_type, alloc);
512     if (!resolver.Resolve(rvalue_ast)) {
513       return nullptr;
514     }
515 
516     if (lvalue_name == register_name) {
517       // found target assignment program - no need to parse further
518 
519       // emplace valid dependent subtrees to make target assignment independent
520       // from predecessors
521       FPOProgramASTVisitorMergeDependent merger(dependent_programs);
522       merger.Merge(rvalue_ast);
523 
524       return rvalue_ast;
525     }
526 
527     dependent_programs[lvalue_name] = rvalue_ast;
528     cur = assign_index + 1;
529   }
530 
531   return nullptr;
532 }
533 
534 bool lldb_private::npdb::TranslateFPOProgramToDWARFExpression(
535     llvm::StringRef program, llvm::StringRef register_name,
536     llvm::Triple::ArchType arch_type, Stream &stream) {
537   NodeAllocator node_alloc;
538   FPOProgramNode *target_program =
539       ParseFPOProgram(program, register_name, arch_type, node_alloc);
540   if (target_program == nullptr) {
541     return false;
542   }
543 
544   FPOProgramASTVisitorDWARFCodegen codegen(stream);
545   codegen.Emit(target_program);
546   return true;
547 }
548