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