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