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 NodeAllocator {
29 public:
30   template <typename T, typename... Args> T *makeNode(Args &&... args) {
31     static_assert(std::is_trivially_destructible<T>::value,
32                   "This object will not be destroyed!");
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   Kind GetKind() const { return m_token_kind; }
56 
57 private:
58   Kind m_token_kind;
59 };
60 
61 class FPOProgramNodeSymbol: public FPOProgramNode {
62 public:
63   FPOProgramNodeSymbol(llvm::StringRef name)
64       : FPOProgramNode(Symbol), m_name(name) {}
65 
66   llvm::StringRef GetName() const { return m_name; }
67 
68   static bool classof(const FPOProgramNode *node) {
69     return node->GetKind() == Symbol;
70   }
71 
72 private:
73   llvm::StringRef m_name;
74 };
75 
76 class FPOProgramNodeRegisterRef : public FPOProgramNode {
77 public:
78   FPOProgramNodeRegisterRef(uint32_t lldb_reg_num)
79       : FPOProgramNode(Register), m_lldb_reg_num(lldb_reg_num) {}
80 
81   uint32_t GetLLDBRegNum() const { return m_lldb_reg_num; }
82 
83   static bool classof(const FPOProgramNode *node) {
84     return node->GetKind() == Register;
85   }
86 
87 private:
88   uint32_t m_lldb_reg_num;
89 };
90 
91 class FPOProgramNodeIntegerLiteral : public FPOProgramNode {
92 public:
93   FPOProgramNodeIntegerLiteral(uint32_t value)
94       : FPOProgramNode(IntegerLiteral), m_value(value) {}
95 
96   uint32_t GetValue() const { return m_value; }
97 
98   static bool classof(const FPOProgramNode *node) {
99     return node->GetKind() == IntegerLiteral;
100   }
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   OpType GetOpType() const { return m_op_type; }
120 
121   const FPOProgramNode *Left() const { return m_left; }
122   FPOProgramNode *&Left() { return m_left; }
123 
124   const FPOProgramNode *Right() const { return m_right; }
125   FPOProgramNode *&Right() { return m_right; }
126 
127   static bool classof(const FPOProgramNode *node) {
128     return node->GetKind() == BinaryOp;
129   }
130 
131 private:
132   OpType m_op_type;
133   FPOProgramNode *m_left;
134   FPOProgramNode *m_right;
135 };
136 
137 class FPOProgramNodeUnaryOp : public FPOProgramNode {
138 public:
139   enum OpType {
140     Deref,
141   };
142 
143   FPOProgramNodeUnaryOp(OpType op_type, FPOProgramNode &operand)
144       : FPOProgramNode(UnaryOp), m_op_type(op_type), m_operand(&operand) {}
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   static bool classof(const FPOProgramNode *node) {
152     return node->GetKind() == UnaryOp;
153   }
154 
155 private:
156   OpType m_op_type;
157   FPOProgramNode *m_operand;
158 };
159 
160 template <typename ResultT = void>
161 class FPOProgramASTVisitor {
162 protected:
163   virtual ~FPOProgramASTVisitor() = default;
164 
165   virtual ResultT Visit(FPOProgramNodeBinaryOp &binary,
166                         FPOProgramNode *&ref) = 0;
167   virtual ResultT Visit(FPOProgramNodeUnaryOp &unary, FPOProgramNode *&ref) = 0;
168   virtual ResultT Visit(FPOProgramNodeRegisterRef &reg, FPOProgramNode *&) = 0;
169   virtual ResultT Visit(FPOProgramNodeIntegerLiteral &integer,
170                         FPOProgramNode *&) = 0;
171   virtual ResultT Visit(FPOProgramNodeSymbol &symbol, FPOProgramNode *&ref) = 0;
172 
173   ResultT Dispatch(FPOProgramNode *&node) {
174     switch (node->GetKind()) {
175     case FPOProgramNode::Register:
176       return Visit(llvm::cast<FPOProgramNodeRegisterRef>(*node), node);
177     case FPOProgramNode::Symbol:
178       return Visit(llvm::cast<FPOProgramNodeSymbol>(*node), node);
179 
180     case FPOProgramNode::IntegerLiteral:
181       return Visit(llvm::cast<FPOProgramNodeIntegerLiteral>(*node), node);
182     case FPOProgramNode::UnaryOp:
183       return Visit(llvm::cast<FPOProgramNodeUnaryOp>(*node), node);
184     case FPOProgramNode::BinaryOp:
185       return Visit(llvm::cast<FPOProgramNodeBinaryOp>(*node), node);
186     }
187     llvm_unreachable("Fully covered switch!");
188   }
189 
190 };
191 
192 class FPOProgramASTVisitorMergeDependent : public FPOProgramASTVisitor<> {
193 public:
194   void Visit(FPOProgramNodeBinaryOp &binary, FPOProgramNode *&) override {
195     Dispatch(binary.Left());
196     Dispatch(binary.Right());
197   }
198 
199   void Visit(FPOProgramNodeUnaryOp &unary, FPOProgramNode *&) override {
200     Dispatch(unary.Operand());
201   }
202 
203   void Visit(FPOProgramNodeRegisterRef &, FPOProgramNode *&) override {}
204   void Visit(FPOProgramNodeIntegerLiteral &, FPOProgramNode *&) override {}
205   void Visit(FPOProgramNodeSymbol &symbol, FPOProgramNode *&ref) override;
206 
207   static void Merge(const llvm::DenseMap<llvm::StringRef, FPOProgramNode *>
208                         &dependent_programs,
209                     FPOProgramNode *&ast) {
210     FPOProgramASTVisitorMergeDependent(dependent_programs).Dispatch(ast);
211   }
212 
213 private:
214   FPOProgramASTVisitorMergeDependent(
215       const llvm::DenseMap<llvm::StringRef, FPOProgramNode *>
216           &dependent_programs)
217       : m_dependent_programs(dependent_programs) {}
218 
219   const llvm::DenseMap<llvm::StringRef, FPOProgramNode *> &m_dependent_programs;
220 };
221 
222 void FPOProgramASTVisitorMergeDependent::Visit(FPOProgramNodeSymbol &symbol,
223                                                FPOProgramNode *&ref) {
224 
225   auto it = m_dependent_programs.find(symbol.GetName());
226   if (it == m_dependent_programs.end())
227     return;
228 
229   ref = it->second;
230   Dispatch(ref);
231 }
232 
233 class FPOProgramASTVisitorResolveRegisterRefs
234     : public FPOProgramASTVisitor<bool> {
235 public:
236   static bool Resolve(const llvm::DenseMap<llvm::StringRef, FPOProgramNode *>
237                           &dependent_programs,
238                       llvm::Triple::ArchType arch_type, NodeAllocator &alloc,
239                       FPOProgramNode *&ast) {
240     return FPOProgramASTVisitorResolveRegisterRefs(dependent_programs,
241                                                    arch_type, alloc)
242         .Dispatch(ast);
243   }
244 
245   bool Visit(FPOProgramNodeBinaryOp &binary, FPOProgramNode *&) override {
246     return Dispatch(binary.Left()) && Dispatch(binary.Right());
247   }
248 
249   bool Visit(FPOProgramNodeUnaryOp &unary, FPOProgramNode *&) override {
250     return Dispatch(unary.Operand());
251   }
252 
253   bool Visit(FPOProgramNodeRegisterRef &, FPOProgramNode *&) override {
254     return true;
255   }
256 
257   bool Visit(FPOProgramNodeIntegerLiteral &, FPOProgramNode *&) override {
258     return true;
259   }
260 
261   bool Visit(FPOProgramNodeSymbol &symbol, FPOProgramNode *&ref) override;
262 
263 private:
264   FPOProgramASTVisitorResolveRegisterRefs(
265       const llvm::DenseMap<llvm::StringRef, FPOProgramNode *>
266           &dependent_programs,
267       llvm::Triple::ArchType arch_type, NodeAllocator &alloc)
268       : m_dependent_programs(dependent_programs), m_arch_type(arch_type),
269         m_alloc(alloc) {}
270 
271   const llvm::DenseMap<llvm::StringRef, FPOProgramNode *> &m_dependent_programs;
272   llvm::Triple::ArchType m_arch_type;
273   NodeAllocator &m_alloc;
274 };
275 
276 static uint32_t ResolveLLDBRegisterNum(llvm::StringRef reg_name, llvm::Triple::ArchType arch_type) {
277   // lookup register name to get lldb register number
278   llvm::ArrayRef<llvm::EnumEntry<uint16_t>> register_names =
279       llvm::codeview::getRegisterNames();
280   auto it = llvm::find_if(
281       register_names,
282       [&reg_name](const llvm::EnumEntry<uint16_t> &register_entry) {
283         return reg_name.compare_lower(register_entry.Name) == 0;
284       });
285 
286   if (it == register_names.end())
287     return LLDB_INVALID_REGNUM;
288 
289   auto reg_id = static_cast<llvm::codeview::RegisterId>(it->Value);
290   return npdb::GetLLDBRegisterNumber(arch_type, reg_id);
291 }
292 
293 bool FPOProgramASTVisitorResolveRegisterRefs::Visit(
294     FPOProgramNodeSymbol &symbol, FPOProgramNode *&ref) {
295   // Look up register reference as lvalue in preceding assignments.
296   auto it = m_dependent_programs.find(symbol.GetName());
297   if (it != m_dependent_programs.end()) {
298     // Dependent programs are handled elsewhere.
299     return true;
300   }
301 
302   uint32_t reg_num =
303       ResolveLLDBRegisterNum(symbol.GetName().drop_front(1), m_arch_type);
304 
305   if (reg_num == LLDB_INVALID_REGNUM)
306     return false;
307 
308   ref = m_alloc.makeNode<FPOProgramNodeRegisterRef>(reg_num);
309   return true;
310 }
311 
312 class FPOProgramASTVisitorDWARFCodegen : public FPOProgramASTVisitor<> {
313 public:
314   static void Emit(Stream &stream, FPOProgramNode *&ast) {
315     FPOProgramASTVisitorDWARFCodegen(stream).Dispatch(ast);
316   }
317 
318   void Visit(FPOProgramNodeRegisterRef &reg, FPOProgramNode *&);
319   void Visit(FPOProgramNodeBinaryOp &binary, FPOProgramNode *&);
320   void Visit(FPOProgramNodeUnaryOp &unary, FPOProgramNode *&);
321   void Visit(FPOProgramNodeSymbol &symbol, FPOProgramNode *&) {
322     llvm_unreachable("Symbols should have been resolved by now!");
323   }
324   void Visit(FPOProgramNodeIntegerLiteral &integer, FPOProgramNode *&);
325 
326 private:
327   FPOProgramASTVisitorDWARFCodegen(Stream &stream) : m_out_stream(stream) {}
328 
329   Stream &m_out_stream;
330 };
331 
332 void FPOProgramASTVisitorDWARFCodegen::Visit(FPOProgramNodeRegisterRef &reg,
333                                              FPOProgramNode *&) {
334 
335   uint32_t reg_num = reg.GetLLDBRegNum();
336   lldbassert(reg_num != LLDB_INVALID_REGNUM);
337 
338   if (reg_num > 31) {
339     m_out_stream.PutHex8(DW_OP_bregx);
340     m_out_stream.PutULEB128(reg_num);
341   } else
342     m_out_stream.PutHex8(DW_OP_breg0 + reg_num);
343 
344   m_out_stream.PutSLEB128(0);
345 }
346 
347 void FPOProgramASTVisitorDWARFCodegen::Visit(
348     FPOProgramNodeIntegerLiteral &integer, FPOProgramNode *&) {
349   uint32_t value = integer.GetValue();
350   m_out_stream.PutHex8(DW_OP_constu);
351   m_out_stream.PutULEB128(value);
352 }
353 
354 void FPOProgramASTVisitorDWARFCodegen::Visit(FPOProgramNodeBinaryOp &binary,
355                                              FPOProgramNode *&) {
356   Dispatch(binary.Left());
357   Dispatch(binary.Right());
358 
359   switch (binary.GetOpType()) {
360   case FPOProgramNodeBinaryOp::Plus:
361     m_out_stream.PutHex8(DW_OP_plus);
362     // NOTE: can be optimized by using DW_OP_plus_uconst opcpode
363     //       if right child node is constant value
364     break;
365   case FPOProgramNodeBinaryOp::Minus:
366     m_out_stream.PutHex8(DW_OP_minus);
367     break;
368   case FPOProgramNodeBinaryOp::Align:
369     // emit align operator a @ b as
370     // a & ~(b - 1)
371     // NOTE: implicitly assuming that b is power of 2
372     m_out_stream.PutHex8(DW_OP_lit1);
373     m_out_stream.PutHex8(DW_OP_minus);
374     m_out_stream.PutHex8(DW_OP_not);
375 
376     m_out_stream.PutHex8(DW_OP_and);
377     break;
378   }
379 }
380 
381 void FPOProgramASTVisitorDWARFCodegen::Visit(FPOProgramNodeUnaryOp &unary,
382                                              FPOProgramNode *&) {
383   Dispatch(unary.Operand());
384 
385   switch (unary.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     if (!FPOProgramASTVisitorResolveRegisterRefs::Resolve(
511             dependent_programs, arch_type, alloc, rvalue_ast))
512       return nullptr;
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::Merge(dependent_programs, rvalue_ast);
520 
521       return rvalue_ast;
522     }
523 
524     dependent_programs[lvalue_name] = rvalue_ast;
525     cur = assign_index + 1;
526   }
527 
528   return nullptr;
529 }
530 
531 bool lldb_private::npdb::TranslateFPOProgramToDWARFExpression(
532     llvm::StringRef program, llvm::StringRef register_name,
533     llvm::Triple::ArchType arch_type, Stream &stream) {
534   NodeAllocator node_alloc;
535   FPOProgramNode *target_program =
536       ParseFPOProgram(program, register_name, arch_type, node_alloc);
537   if (target_program == nullptr) {
538     return false;
539   }
540 
541   FPOProgramASTVisitorDWARFCodegen::Emit(stream, target_program);
542   return true;
543 }
544