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(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::Symbol) {
220     auto *node_symbol_ref = static_cast<FPOProgramNodeSymbol *>(node_ref);
221 
222     auto it = m_dependent_programs.find(node_symbol_ref->GetName());
223     if (it == m_dependent_programs.end()) {
224       break;
225     }
226 
227     node_ref = it->second;
228   }
229 }
230 
231 class FPOProgramASTVisitorResolveRegisterRefs : public FPOProgramASTVisitor {
232 public:
233   FPOProgramASTVisitorResolveRegisterRefs(
234       const llvm::DenseMap<llvm::StringRef, FPOProgramNode *>
235           &dependent_programs,
236       llvm::Triple::ArchType arch_type, NodeAllocator &alloc)
237       : m_dependent_programs(dependent_programs), m_arch_type(arch_type),
238         m_alloc(alloc) {}
239 
240   bool Resolve(FPOProgramNode *&program);
241 
242 private:
243   void Visit(FPOProgramNodeBinaryOp &node) override;
244   void Visit(FPOProgramNodeUnaryOp &node) override;
245 
246   bool TryReplace(FPOProgramNode *&node_ref);
247 
248   const llvm::DenseMap<llvm::StringRef, FPOProgramNode *> &m_dependent_programs;
249   llvm::Triple::ArchType m_arch_type;
250   NodeAllocator &m_alloc;
251   bool m_no_error_flag = true;
252 };
253 
254 bool FPOProgramASTVisitorResolveRegisterRefs::Resolve(FPOProgramNode *&program) {
255   if (!TryReplace(program))
256     return false;
257   program->Accept(*this);
258   return m_no_error_flag;
259 }
260 
261 static uint32_t ResolveLLDBRegisterNum(llvm::StringRef reg_name, llvm::Triple::ArchType arch_type) {
262   // lookup register name to get lldb register number
263   llvm::ArrayRef<llvm::EnumEntry<uint16_t>> register_names =
264       llvm::codeview::getRegisterNames();
265   auto it = llvm::find_if(
266       register_names,
267       [&reg_name](const llvm::EnumEntry<uint16_t> &register_entry) {
268         return reg_name.compare_lower(register_entry.Name) == 0;
269       });
270 
271   if (it == register_names.end())
272     return LLDB_INVALID_REGNUM;
273 
274   auto reg_id = static_cast<llvm::codeview::RegisterId>(it->Value);
275   return npdb::GetLLDBRegisterNumber(arch_type, reg_id);
276 }
277 
278 bool FPOProgramASTVisitorResolveRegisterRefs::TryReplace(
279     FPOProgramNode *&node_ref) {
280   if (node_ref->GetKind() != FPOProgramNode::Symbol)
281     return true;
282 
283   auto *symbol = static_cast<FPOProgramNodeSymbol *>(node_ref);
284 
285   // Look up register reference as lvalue in preceding assignments.
286   auto it = m_dependent_programs.find(symbol->GetName());
287   if (it != m_dependent_programs.end()) {
288     // Dependent programs are handled elsewhere.
289     return true;
290   }
291 
292   uint32_t reg_num =
293       ResolveLLDBRegisterNum(symbol->GetName().drop_front(1), m_arch_type);
294 
295   if (reg_num == LLDB_INVALID_REGNUM)
296     return false;
297 
298   node_ref = m_alloc.makeNode<FPOProgramNodeRegisterRef>(reg_num);
299   return true;
300 }
301 
302 void FPOProgramASTVisitorResolveRegisterRefs::Visit(
303     FPOProgramNodeBinaryOp &node) {
304   m_no_error_flag = Resolve(node.Left()) && Resolve(node.Right());
305 }
306 
307 void FPOProgramASTVisitorResolveRegisterRefs::Visit(
308     FPOProgramNodeUnaryOp &node) {
309   m_no_error_flag = Resolve(node.Operand());
310 }
311 
312 class FPOProgramASTVisitorDWARFCodegen : public FPOProgramASTVisitor {
313 public:
314   FPOProgramASTVisitorDWARFCodegen(Stream &stream) : m_out_stream(stream) {}
315 
316   void Emit(FPOProgramNode &program);
317 
318 private:
319   void Visit(FPOProgramNodeRegisterRef &node) override;
320   void Visit(FPOProgramNodeIntegerLiteral &node) override;
321   void Visit(FPOProgramNodeBinaryOp &node) override;
322   void Visit(FPOProgramNodeUnaryOp &node) override;
323 
324 private:
325   Stream &m_out_stream;
326 };
327 
328 void FPOProgramASTVisitorDWARFCodegen::Emit(FPOProgramNode &program) {
329   program.Accept(*this);
330 }
331 
332 void FPOProgramASTVisitorDWARFCodegen::Visit(FPOProgramNodeRegisterRef &node) {
333 
334   uint32_t reg_num = node.GetLLDBRegNum();
335   lldbassert(reg_num != LLDB_INVALID_REGNUM);
336 
337   if (reg_num > 31) {
338     m_out_stream.PutHex8(DW_OP_bregx);
339     m_out_stream.PutULEB128(reg_num);
340   } else
341     m_out_stream.PutHex8(DW_OP_breg0 + reg_num);
342 
343   m_out_stream.PutSLEB128(0);
344 }
345 
346 void FPOProgramASTVisitorDWARFCodegen::Visit(
347     FPOProgramNodeIntegerLiteral &node) {
348   uint32_t value = node.GetValue();
349   m_out_stream.PutHex8(DW_OP_constu);
350   m_out_stream.PutULEB128(value);
351 }
352 
353 void FPOProgramASTVisitorDWARFCodegen::Visit(FPOProgramNodeBinaryOp &node) {
354 
355   Emit(*node.Left());
356   Emit(*node.Right());
357 
358   switch (node.GetOpType()) {
359   case FPOProgramNodeBinaryOp::Plus:
360     m_out_stream.PutHex8(DW_OP_plus);
361     // NOTE: can be optimized by using DW_OP_plus_uconst opcpode
362     //       if right child node is constant value
363     break;
364   case FPOProgramNodeBinaryOp::Minus:
365     m_out_stream.PutHex8(DW_OP_minus);
366     break;
367   case FPOProgramNodeBinaryOp::Align:
368     // emit align operator a @ b as
369     // a & ~(b - 1)
370     // NOTE: implicitly assuming that b is power of 2
371     m_out_stream.PutHex8(DW_OP_lit1);
372     m_out_stream.PutHex8(DW_OP_minus);
373     m_out_stream.PutHex8(DW_OP_not);
374 
375     m_out_stream.PutHex8(DW_OP_and);
376     break;
377   }
378 }
379 
380 void FPOProgramASTVisitorDWARFCodegen::Visit(FPOProgramNodeUnaryOp &node) {
381   Emit(*node.Operand());
382 
383   switch (node.GetOpType()) {
384   case FPOProgramNodeUnaryOp::Deref:
385     m_out_stream.PutHex8(DW_OP_deref);
386     break;
387   }
388 }
389 
390 } // namespace
391 
392 static bool ParseFPOSingleAssignmentProgram(llvm::StringRef program,
393                                             NodeAllocator &alloc,
394                                             llvm::StringRef &register_name,
395                                             FPOProgramNode *&ast) {
396   llvm::SmallVector<llvm::StringRef, 16> tokens;
397   llvm::SplitString(program, tokens, " ");
398 
399   if (tokens.empty())
400     return false;
401 
402   llvm::SmallVector<FPOProgramNode *, 4> eval_stack;
403 
404   llvm::DenseMap<llvm::StringRef, FPOProgramNodeBinaryOp::OpType> ops_binary = {
405       {"+", FPOProgramNodeBinaryOp::Plus},
406       {"-", FPOProgramNodeBinaryOp::Minus},
407       {"@", FPOProgramNodeBinaryOp::Align},
408   };
409 
410   llvm::DenseMap<llvm::StringRef, FPOProgramNodeUnaryOp::OpType> ops_unary = {
411       {"^", FPOProgramNodeUnaryOp::Deref},
412   };
413 
414   constexpr llvm::StringLiteral ra_search_keyword = ".raSearch";
415 
416   // lvalue of assignment is always first token
417   // rvalue program goes next
418   for (size_t i = 1; i < tokens.size(); ++i) {
419     llvm::StringRef cur = tokens[i];
420 
421     auto ops_binary_it = ops_binary.find(cur);
422     if (ops_binary_it != ops_binary.end()) {
423       // token is binary operator
424       if (eval_stack.size() < 2) {
425         return false;
426       }
427       FPOProgramNode *right = eval_stack.pop_back_val();
428       FPOProgramNode *left = eval_stack.pop_back_val();
429       FPOProgramNode *node = alloc.makeNode<FPOProgramNodeBinaryOp>(
430           ops_binary_it->second, *left, *right);
431       eval_stack.push_back(node);
432       continue;
433     }
434 
435     auto ops_unary_it = ops_unary.find(cur);
436     if (ops_unary_it != ops_unary.end()) {
437       // token is unary operator
438       if (eval_stack.empty()) {
439         return false;
440       }
441       FPOProgramNode *operand = eval_stack.pop_back_val();
442       FPOProgramNode *node =
443           alloc.makeNode<FPOProgramNodeUnaryOp>(ops_unary_it->second, *operand);
444       eval_stack.push_back(node);
445       continue;
446     }
447 
448     if (cur.startswith("$")) {
449       eval_stack.push_back(alloc.makeNode<FPOProgramNodeSymbol>(cur));
450       continue;
451     }
452 
453     if (cur == ra_search_keyword) {
454       // TODO: .raSearch is unsupported
455       return false;
456     }
457 
458     uint32_t value;
459     if (!cur.getAsInteger(10, value)) {
460       // token is integer literal
461       eval_stack.push_back(alloc.makeNode<FPOProgramNodeIntegerLiteral>(value));
462       continue;
463     }
464 
465     // unexpected token
466     return false;
467   }
468 
469   if (eval_stack.size() != 1) {
470     return false;
471   }
472 
473   register_name = tokens[0];
474   ast = eval_stack.pop_back_val();
475 
476   return true;
477 }
478 
479 static FPOProgramNode *ParseFPOProgram(llvm::StringRef program,
480                                        llvm::StringRef register_name,
481                                        llvm::Triple::ArchType arch_type,
482                                        NodeAllocator &alloc) {
483   llvm::DenseMap<llvm::StringRef, FPOProgramNode *> dependent_programs;
484 
485   size_t cur = 0;
486   while (true) {
487     size_t assign_index = program.find('=', cur);
488     if (assign_index == llvm::StringRef::npos) {
489       llvm::StringRef tail = program.slice(cur, llvm::StringRef::npos);
490       if (!tail.trim().empty()) {
491         // missing assign operator
492         return nullptr;
493       }
494       break;
495     }
496     llvm::StringRef assignment_program = program.slice(cur, assign_index);
497 
498     llvm::StringRef lvalue_name;
499     FPOProgramNode *rvalue_ast = nullptr;
500     if (!ParseFPOSingleAssignmentProgram(assignment_program, alloc, lvalue_name,
501                                          rvalue_ast)) {
502       return nullptr;
503     }
504 
505     lldbassert(rvalue_ast);
506 
507     // check & resolve assignment program
508     FPOProgramASTVisitorResolveRegisterRefs resolver(dependent_programs,
509                                                      arch_type, alloc);
510     if (!resolver.Resolve(rvalue_ast)) {
511       return nullptr;
512     }
513 
514     if (lvalue_name == register_name) {
515       // found target assignment program - no need to parse further
516 
517       // emplace valid dependent subtrees to make target assignment independent
518       // from predecessors
519       FPOProgramASTVisitorMergeDependent merger(dependent_programs);
520       merger.Merge(rvalue_ast);
521 
522       return rvalue_ast;
523     }
524 
525     dependent_programs[lvalue_name] = rvalue_ast;
526     cur = assign_index + 1;
527   }
528 
529   return nullptr;
530 }
531 
532 bool lldb_private::npdb::TranslateFPOProgramToDWARFExpression(
533     llvm::StringRef program, llvm::StringRef register_name,
534     llvm::Triple::ArchType arch_type, Stream &stream) {
535   NodeAllocator node_alloc;
536   FPOProgramNode *target_program =
537       ParseFPOProgram(program, register_name, arch_type, node_alloc);
538   if (target_program == nullptr) {
539     return false;
540   }
541 
542   FPOProgramASTVisitorDWARFCodegen codegen(stream);
543   codegen.Emit(*target_program);
544   return true;
545 }
546