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