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 ResultT Visit(FPOProgramNodeBinaryOp &binary,
164                         FPOProgramNode *&ref) = 0;
165   virtual ResultT Visit(FPOProgramNodeUnaryOp &unary, FPOProgramNode *&ref) = 0;
166   virtual ResultT Visit(FPOProgramNodeRegisterRef &reg, FPOProgramNode *&) = 0;
167   virtual ResultT Visit(FPOProgramNodeIntegerLiteral &integer,
168                         FPOProgramNode *&) = 0;
169   virtual ResultT Visit(FPOProgramNodeSymbol &symbol, FPOProgramNode *&ref) = 0;
170 
171   ResultT Dispatch(FPOProgramNode *&node) {
172     switch (node->GetKind()) {
173     case FPOProgramNode::Register:
174       return Visit(llvm::cast<FPOProgramNodeRegisterRef>(*node), node);
175     case FPOProgramNode::Symbol:
176       return Visit(llvm::cast<FPOProgramNodeSymbol>(*node), node);
177 
178     case FPOProgramNode::IntegerLiteral:
179       return Visit(llvm::cast<FPOProgramNodeIntegerLiteral>(*node), node);
180     case FPOProgramNode::UnaryOp:
181       return Visit(llvm::cast<FPOProgramNodeUnaryOp>(*node), node);
182     case FPOProgramNode::BinaryOp:
183       return Visit(llvm::cast<FPOProgramNodeBinaryOp>(*node), node);
184     }
185     llvm_unreachable("Fully covered switch!");
186   }
187 
188 };
189 
190 class FPOProgramASTVisitorMergeDependent : public FPOProgramASTVisitor<> {
191 public:
192   void Visit(FPOProgramNodeBinaryOp &binary, FPOProgramNode *&) override {
193     Dispatch(binary.Left());
194     Dispatch(binary.Right());
195   }
196 
197   void Visit(FPOProgramNodeUnaryOp &unary, FPOProgramNode *&) override {
198     Dispatch(unary.Operand());
199   }
200 
201   void Visit(FPOProgramNodeRegisterRef &, FPOProgramNode *&) override {}
202   void Visit(FPOProgramNodeIntegerLiteral &, FPOProgramNode *&) override {}
203   void Visit(FPOProgramNodeSymbol &symbol, FPOProgramNode *&ref) override;
204 
205   static void Merge(const llvm::DenseMap<llvm::StringRef, FPOProgramNode *>
206                         &dependent_programs,
207                     FPOProgramNode *&ast) {
208     FPOProgramASTVisitorMergeDependent(dependent_programs).Dispatch(ast);
209   }
210 
211 private:
212   FPOProgramASTVisitorMergeDependent(
213       const llvm::DenseMap<llvm::StringRef, FPOProgramNode *>
214           &dependent_programs)
215       : m_dependent_programs(dependent_programs) {}
216 
217   const llvm::DenseMap<llvm::StringRef, FPOProgramNode *> &m_dependent_programs;
218 };
219 
220 void FPOProgramASTVisitorMergeDependent::Visit(FPOProgramNodeSymbol &symbol,
221                                                FPOProgramNode *&ref) {
222 
223   auto it = m_dependent_programs.find(symbol.GetName());
224   if (it == m_dependent_programs.end())
225     return;
226 
227   ref = it->second;
228   Dispatch(ref);
229 }
230 
231 class FPOProgramASTVisitorResolveRegisterRefs
232     : public FPOProgramASTVisitor<bool> {
233 public:
234   static bool Resolve(const llvm::DenseMap<llvm::StringRef, FPOProgramNode *>
235                           &dependent_programs,
236                       llvm::Triple::ArchType arch_type, NodeAllocator &alloc,
237                       FPOProgramNode *&ast) {
238     return FPOProgramASTVisitorResolveRegisterRefs(dependent_programs,
239                                                    arch_type, alloc)
240         .Dispatch(ast);
241   }
242 
243   bool Visit(FPOProgramNodeBinaryOp &binary, FPOProgramNode *&) override {
244     return Dispatch(binary.Left()) && Dispatch(binary.Right());
245   }
246 
247   bool Visit(FPOProgramNodeUnaryOp &unary, FPOProgramNode *&) override {
248     return Dispatch(unary.Operand());
249   }
250 
251   bool Visit(FPOProgramNodeRegisterRef &, FPOProgramNode *&) override {
252     return true;
253   }
254 
255   bool Visit(FPOProgramNodeIntegerLiteral &, FPOProgramNode *&) override {
256     return true;
257   }
258 
259   bool Visit(FPOProgramNodeSymbol &symbol, FPOProgramNode *&ref) override;
260 
261 private:
262   FPOProgramASTVisitorResolveRegisterRefs(
263       const llvm::DenseMap<llvm::StringRef, FPOProgramNode *>
264           &dependent_programs,
265       llvm::Triple::ArchType arch_type, NodeAllocator &alloc)
266       : m_dependent_programs(dependent_programs), m_arch_type(arch_type),
267         m_alloc(alloc) {}
268 
269   const llvm::DenseMap<llvm::StringRef, FPOProgramNode *> &m_dependent_programs;
270   llvm::Triple::ArchType m_arch_type;
271   NodeAllocator &m_alloc;
272 };
273 
274 static uint32_t ResolveLLDBRegisterNum(llvm::StringRef reg_name, llvm::Triple::ArchType arch_type) {
275   // lookup register name to get lldb register number
276   llvm::ArrayRef<llvm::EnumEntry<uint16_t>> register_names =
277       llvm::codeview::getRegisterNames();
278   auto it = llvm::find_if(
279       register_names,
280       [&reg_name](const llvm::EnumEntry<uint16_t> &register_entry) {
281         return reg_name.compare_lower(register_entry.Name) == 0;
282       });
283 
284   if (it == register_names.end())
285     return LLDB_INVALID_REGNUM;
286 
287   auto reg_id = static_cast<llvm::codeview::RegisterId>(it->Value);
288   return npdb::GetLLDBRegisterNumber(arch_type, reg_id);
289 }
290 
291 bool FPOProgramASTVisitorResolveRegisterRefs::Visit(
292     FPOProgramNodeSymbol &symbol, FPOProgramNode *&ref) {
293   // Look up register reference as lvalue in preceding assignments.
294   auto it = m_dependent_programs.find(symbol.GetName());
295   if (it != m_dependent_programs.end()) {
296     // Dependent programs are handled elsewhere.
297     return true;
298   }
299 
300   uint32_t reg_num =
301       ResolveLLDBRegisterNum(symbol.GetName().drop_front(1), m_arch_type);
302 
303   if (reg_num == LLDB_INVALID_REGNUM)
304     return false;
305 
306   ref = m_alloc.makeNode<FPOProgramNodeRegisterRef>(reg_num);
307   return true;
308 }
309 
310 class FPOProgramASTVisitorDWARFCodegen : public FPOProgramASTVisitor<> {
311 public:
312   static void Emit(Stream &stream, FPOProgramNode *&ast) {
313     FPOProgramASTVisitorDWARFCodegen(stream).Dispatch(ast);
314   }
315 
316   void Visit(FPOProgramNodeRegisterRef &reg, FPOProgramNode *&);
317   void Visit(FPOProgramNodeBinaryOp &binary, FPOProgramNode *&);
318   void Visit(FPOProgramNodeUnaryOp &unary, FPOProgramNode *&);
319   void Visit(FPOProgramNodeSymbol &symbol, FPOProgramNode *&) {
320     llvm_unreachable("Symbols should have been resolved by now!");
321   }
322   void Visit(FPOProgramNodeIntegerLiteral &integer, FPOProgramNode *&);
323 
324 private:
325   FPOProgramASTVisitorDWARFCodegen(Stream &stream) : m_out_stream(stream) {}
326 
327   Stream &m_out_stream;
328 };
329 
330 void FPOProgramASTVisitorDWARFCodegen::Visit(FPOProgramNodeRegisterRef &reg,
331                                              FPOProgramNode *&) {
332 
333   uint32_t reg_num = reg.GetLLDBRegNum();
334   lldbassert(reg_num != LLDB_INVALID_REGNUM);
335 
336   if (reg_num > 31) {
337     m_out_stream.PutHex8(DW_OP_bregx);
338     m_out_stream.PutULEB128(reg_num);
339   } else
340     m_out_stream.PutHex8(DW_OP_breg0 + reg_num);
341 
342   m_out_stream.PutSLEB128(0);
343 }
344 
345 void FPOProgramASTVisitorDWARFCodegen::Visit(
346     FPOProgramNodeIntegerLiteral &integer, FPOProgramNode *&) {
347   uint32_t value = integer.GetValue();
348   m_out_stream.PutHex8(DW_OP_constu);
349   m_out_stream.PutULEB128(value);
350 }
351 
352 void FPOProgramASTVisitorDWARFCodegen::Visit(FPOProgramNodeBinaryOp &binary,
353                                              FPOProgramNode *&) {
354   Dispatch(binary.Left());
355   Dispatch(binary.Right());
356 
357   switch (binary.GetOpType()) {
358   case FPOProgramNodeBinaryOp::Plus:
359     m_out_stream.PutHex8(DW_OP_plus);
360     // NOTE: can be optimized by using DW_OP_plus_uconst opcpode
361     //       if right child node is constant value
362     break;
363   case FPOProgramNodeBinaryOp::Minus:
364     m_out_stream.PutHex8(DW_OP_minus);
365     break;
366   case FPOProgramNodeBinaryOp::Align:
367     // emit align operator a @ b as
368     // a & ~(b - 1)
369     // NOTE: implicitly assuming that b is power of 2
370     m_out_stream.PutHex8(DW_OP_lit1);
371     m_out_stream.PutHex8(DW_OP_minus);
372     m_out_stream.PutHex8(DW_OP_not);
373 
374     m_out_stream.PutHex8(DW_OP_and);
375     break;
376   }
377 }
378 
379 void FPOProgramASTVisitorDWARFCodegen::Visit(FPOProgramNodeUnaryOp &unary,
380                                              FPOProgramNode *&) {
381   Dispatch(unary.Operand());
382 
383   switch (unary.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     if (!FPOProgramASTVisitorResolveRegisterRefs::Resolve(
509             dependent_programs, arch_type, alloc, rvalue_ast))
510       return nullptr;
511 
512     if (lvalue_name == register_name) {
513       // found target assignment program - no need to parse further
514 
515       // emplace valid dependent subtrees to make target assignment independent
516       // from predecessors
517       FPOProgramASTVisitorMergeDependent::Merge(dependent_programs, rvalue_ast);
518 
519       return rvalue_ast;
520     }
521 
522     dependent_programs[lvalue_name] = rvalue_ast;
523     cur = assign_index + 1;
524   }
525 
526   return nullptr;
527 }
528 
529 bool lldb_private::npdb::TranslateFPOProgramToDWARFExpression(
530     llvm::StringRef program, llvm::StringRef register_name,
531     llvm::Triple::ArchType arch_type, Stream &stream) {
532   NodeAllocator node_alloc;
533   FPOProgramNode *target_program =
534       ParseFPOProgram(program, register_name, arch_type, node_alloc);
535   if (target_program == nullptr) {
536     return false;
537   }
538 
539   FPOProgramASTVisitorDWARFCodegen::Emit(stream, target_program);
540   return true;
541 }
542